8月21日小练

网站： 8月21日小练

A HDU2554 N对数的排列问题

题解来自：http://blog.csdn.net/ilovexiaohao/article/details/8717846

这题可以这样来抽象：

n对数，大小为1、2、3、...、n。现要求两个1之间有1个数，两个2之间有2个数，以此类推，两个n之间有n个数。

并且，数的次序可以随意的。

准备知识：

①n对数，共2*n个数。所以要有2*n个位置来放置这2*n个数。②sum()表示求和运算。

正式解决：

①设k（k=1,2,..,n)放置的第一个位置为ak，第二个位置为bk。显然有bk-ak=k+1（假定下一个位置在上一个位置之前）。

那么会有sum(bk-ak)=2+3+4+...+(n+1)=(1+2+3+...+n)+(1+1+...+1)=n*(n+1)/2+n。

②又因为要有2*n个位置来放置这2*n个数。则sum(ak+bk)=1+2+3+...+2*n=(1+2*n)*(2*n)/2=(1+2*n)*n。

③sum(ak+bk)=sum(ak+ak+k+1)=sum(2*ak+bk-ak)=2*sum(ak)+sum(bk-ak)=2*sum(ak)+n*(n+1)/2+n。

④比较②③可得：(1+2*n)*n=2*sum(ak)+n*(n+1)/2+n。可得sum(ak)=n*(3*n-1)/4。

⑤就像前面已经说过的一样，ak表示数k第一次出现的位置。ak不易确定。当可以肯定的是sum(ak)一定为正整数。

那么就会有n=4*p或者3*n-1=4*p（p为正整数）。

代码： 31ms

 1 #include <stdio.h>
 2 #include <iostream>
 3 using namespace std;
 4 int main()
 5 {
 6     int n;
 7     while(~scanf("%d",&n)&&n)
 8     {
 9         if(n%4==0 || (3*n-1)%4==0)
10             printf("Y
");
11         else
12             printf("N
");
13     }
14     return 0;
15 }

B Big Number HDU 1018

a的长度=log10(a)+1；

a=1*2*3*4*......*n；

log10(1*2*3*4......*n)=log10(1)+log10(2)+log10(3)+.....+log10(n);

代码： 968ms

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <math.h>
 4 using namespace std;
 5 int main()
 6 {
 7     int n,i,T;
 8     double sum;
 9     scanf("%d",&T);
10     while(T--)
11     {
12         scanf("%d",&n);
13         sum=0;
14         for(i=1;i<=n;i++)
15           sum=sum+log10((double)i);    //要注意i要转化为double 
16         printf("%d
",(int)sum+1);   //转化为int 
17     }
18     return 0;
19 }

C Going Home HDU 1533 KM算法

D Invitation Cards POJ 1511 最短路（spfa算法）

E 命运 HDU 2571 要从左上角到达右下角，每个格子都有个数值，求最大的和为多少，只能向右走或者向下走，向右走有两种可能，一种是走一步，也可以走到当前坐标的倍数去。

DP思想：每走一步，找到可能的上一步的最大值，再加上自己这个格子的值。

代码： 46ms

 1 #include <stdio.h>
 2 #include <iostream>
 3 using namespace std;
 4 int dp[22][1005];
 5 int main()
 6 {
 7     int T,m,n,i,j,maxx,k;
 8     scanf("%d",&T);
 9     while(T--)
10     {
11         scanf("%d%d",&m,&n);
12         for(i=1;i<=m;i++)
13             for(j=1;j<=n;j++)
14             {
15                 scanf("%d",&dp[i][j]);
16                 maxx=-9999990;    //初始化
17                 for(k=1;k<j;k++)
18                     if(j%k==0)    //倍数的最大值
19                         maxx=max(maxx,dp[i][k]);
20                 if(j!=1)   //往上找
21                     maxx=max(maxx,dp[i][j-1]);
22                 if(i!=1)   
23                     maxx=max(maxx,dp[i-1][j]);
24                 if(i==1&&j==1)
25                     maxx=0;
26                 dp[i][j]+=maxx;
27             }
28         printf("%d
",dp[m][n]);    //最后一个格子的值
29     }
30     return 0;
31 }