8月15号的练习：HDU 1042&&HDU 1050&&HDU 1181&&HDU 3501&&HDU 2601

一道大数阶乘题目：

知道方法还是好实现的。。。

对于求大整数的阶乘，可以采用分段相乘的方法，其理论基础是加法的分配律，乘法的分配律。

例如 :123456789*123=123*（123*10^5+56789）=123*123*10^5+123*56789；（把他们分段来存储，就不会乘不了了）

如果我们用一个数组result[0]=56789,result[1]=123,那么123456789*123就是123*result[0]%10^6和result[1]*123+result[0]/10^6构成的一个数，另result[0]=123*result[0]%10^6,result[1]=result[1]*123+result[0]/10^6,则这个数就是result[1]result[0];

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<algorithm>
 4 using namespace std;
 5 int a[16000];
 6 int main()
 7 {
 8     int n,t,p,i,j;
 9     while(scanf("%d",&n)!=EOF)
10     {
11         a[1]=1;t=1;p=0;
12         for(i=1;i<=n;i++)
13         {
14             for(j=1;j<=t;j++)
15             {
16                     a[j]=a[j]*i+p;
17                     p=0;
18                 if(a[j]>99999)
19                 {
20                     p=a[j]/100000;
21                     a[j]=a[j]%100000;
22                     if(j==t)
23                     {
24                         a[j+1]=p;
25                         t++;
26                         p=0;
27                         break;
28                     }
29                 }
30             }
31         }
32         printf("%d",a[t]);
33         for(i=t-1;i>0;i--)
34             printf("%05d",a[i]);//注意要保存零
35         printf("
");
36     }
37     return 0;
38 }

Moving Tables HDU 1050

贪心加排序：看懂题意很好做。。。

注意：输入的点不一定左边小于右边！

走廊的存在看清楚！

最简单的方法就是开个数组记录每一对房间需要占用的次数，取最大值就行了！

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<algorithm>
 4 #include<string.h>
 5 using namespace std;
 6 int main()
 7 {
 8     int a[205],t,n,a1,a2,max,i;
 9     scanf("%d",&t);
10     while(t--)
11     {
12         scanf("%d",&n);
13         memset(a,0,sizeof(a));
14         while(n--)
15         {
16             scanf("%d%d",&a1,&a2);
17             if(a1>a2)
18                 swap(a1,a2);
19             for(i=(a1+1)/2;i<=(a2+1)/2;i++)
20                 a[i]++;
21         }
22         max=a[1];
23         for(i=1;i<=200;i++)
24             if(a[i]>max)
25                 max=a[i];
26         printf("%d
",max*10);
27     }
28     return 0;
29 }

变形课 HDU 1181

这个题目水了一笔！直接用Dfs（）。。。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<stdio.h>
 4 #include<string.h>
 5 using namespace std;
 6 int d=0,vis[1005];
 7 char b1[1005],c1[1005],flag;
 8 void dfs(int x)
 9 {
10     int i;
11     if(c1[x]=='m')
12     {
13         flag=1;
14         return ;
15     }
16     for(i=0;i<d;i++)
17         if(c1[x]==b1[i]&&!vis[i])
18         {
19             vis[i]=1;
20             dfs(i);
21             vis[i]=0;
22         }
23 }
24 int main()
25 {
26     int i,n;
27     char a[1005];
28     while(scanf("%s",a)!=EOF)
29     {
30         if(a[0]=='0')
31         {
32             flag=0;
33             for(i=0;i<d;i++)
34             {
35                 if(b1[i]=='b')
36                 {
37                     memset(vis,0,sizeof(vis));
38                     vis[i]=1;
39                     dfs(i);
40                     vis[i]=0;
41                 }
42                 if(flag)
43                     break;
44             }
45             if(flag)
46                 printf("Yes.
");
47             else
48                 printf("No.
");
49             d=0;
50         }
51         else
52         {
53             n=strlen(a);
54             b1[d]=a[0];
55             c1[d]=a[n-1];
56             d++;
57         }
58     }
59 }

Calculation 2 HDU 3501

一道用欧拉函数求解的数学题：（表示很蛋疼）

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int mod=1000000007;
 5 int main()
 6 {
 7     __int64 ans,n,m,i;
 8     while(scanf("%I64d",&n)!=EOF)
 9     {
10         if(n==0) 
11             break;
12         ans=m=n;
13         for(i=2;i*i<=n;i++)
14         {
15             if(n%i==0)
16             {
17                 ans-=ans/i;
18                 while(n%i==0) 
19                     n/=i;
20                 if(n==1) 
21                     break;
22             }
23         }
24         if(n!=1) 
25             ans-=ans/n;   
26         ans=(m*(m-1)/2-m*ans/2)%mod;
27         printf("%I64d
",ans);
28     }
29  return 0;
30 }

摘自：http://blog.sina.com.cn/s/blog_79b832820100s1md.html

An easy problem HDU 2601

表示又是一道数学题：（看到关键点就好说）

i*j+i+j==N可以变成(i+1)*(j+1)==N+1又因为（0<i<=j）取根号

 1 #include<stdio.h>
 2 #include<math.h>
 3 int main()
 4 {
 5     __int64 n;
 6     int d,s,i,t;
 7     scanf("%d",&t);
 8     while(t--)
 9     {
10         scanf("%I64d",&n);
11         n++;
12         d=sqrt(n);
13         s=0;
14         for(i=2;i<=d;i++)
15             if(n%i==0)
16                 s++;
17         printf("%d
",s);
18     }
19     return 0;
20 }