8-13-Exercise

昨天的比赛好郁闷.......倒不是因为题目......在快要比赛的时候突然所有的网站都进不去了.......改了半天的DNS & IP......比赛都比了1个多小时才进去.....都不想做题了= =|||

这道题感觉似曾相识......貌似很久以前做过= =

其实仔细想一下，题目并不难~若n为偶数的话，那么"偶正+偶负"翻转的一定是偶数次;而"奇正+奇负"翻转的一定是奇数次~故没有确定的最少次数~

但是，若n为奇数的话，是"奇正+偶负"或"偶正+奇负"，翻转的都是偶数次~故存在确定的最少次数！

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     int n;
 8     while(scanf("%d",&n),n)
 9     {
10         if(n%2==0)
11             printf("No Solution!
");
12         else
13             printf("%d
",n-1);
14     }
15     return 0;
16 }

//memory：164KB time：16ms

B.HDU 4506 小明系列故事――师兄帮帮忙

此处求k^t时要采用反复平方法（快速幂）【该方法在另一篇博客里讲的有~链接】，否则会TLE~

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 #define M 1000000007
 7 int T,i;
 8 __int64 a[10100],b[10100];
 9 __int64 n,t,k;
10 
11 __int64 Pow(__int64 x,__int64 n)          //快速幂~
12 {
13     __int64 ret=1,s=x;
14     while(1)
15     {
16         if(n&1)
17             ret=(ret%M*s%M)%M;
18         if(n>>=1)
19             s=(s%M*s%M)%M;
20         else
21             break;
22     }
23     return ret;
24 }
25 
26 int main()
27 {
28     scanf("%d",&T);
29     while(T--)
30     {
31         scanf("%I64d%I64d%I64d",&n,&t,&k);
32         k=Pow(k,t);
33         t=t%n;                        //因为t很有可能会大于n，故这一步很重要!!!!
34         for(i=0;i<n;i++)
35             scanf("%I64d",&a[i]);
36         for(i=t;i<n;i++)
37             b[i]=(a[i-t]%M*k)%M;
38         for(i=0;i<t;i++)
39             b[i]=(a[i+n-t]%M*k)%M;
40         for(i=0;i<n-1;i++)
41             printf("%I64d ",b[i]);
42         printf("%I64d
",b[n-1]);
43     }
44     return 0;
45 }

//memory：428KB time：46ms

C.HDU 2546 饭卡

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 int main()
 8 {
 9     int n,a[1001],f[1001],m;
10     while(scanf("%d",&n),n)
11     {
12         for(int i=0;i<n;i++)
13             scanf("%d",&a[i]);
14         sort(a,a+n);
15         scanf("%d",&m);
16         if(m>=5)
17         {
18             memset(f,0,sizeof(f));
19             for(int i=0;i<n-1;i++)
20                 for(int j=m-5;j>=a[i];j--)
21                     if(f[j-a[i]]+a[i]>f[j] && f[j-a[i]]+a[i]<=m-5)
22                         f[j]=f[j-a[i]]+a[i];
23             printf("%d
",m-f[m-5]-a[n-1]);
24         }
25         else
26             printf("%d
",m);
27     }
28     return 0;
29 }

D.HDU 1026 Ignatius and the Princess I

......Loading......