首页 > > 程序设计 > C/C++ >

Mike and gcd problem CodeForces - 798C

2018-06-17 21:57:28来源：未知阅读 ()

题目

（智商题 or 糟心的贪心）

题意：

有一个数列a1,a2,...,an，每次操作可以将相邻的两个数x,y变为x-y,x+y，求最少的操作数使得gcd(a1,a2,...,an)>1。gcd(a1,...,an)表示最大的非负整数使得所有ai都能被gcd(a1,...,an)整除。

分析：

首先，如果原来gcd就不是1那么答案就是0。
如果gcd是1：
相邻两数x和y的变化方法为：x,y=>x-y,x+y
设新的gcd值为d，那么x-y和x+y能被d整除，因此2x和2y能被d整除，
因此d最大是x与y的gcd的2倍
因此只需要考虑如何使所有数变为偶数（这样次数一定是最小的）
x奇y偶
=>x奇y奇
x偶y奇
=>x奇y奇
x偶y偶
=>x偶y偶
x奇y奇
=>x偶y偶
将偶数标记为0，奇数标记为1，
那么就变成了xor运算
整题就变成了给定一个由0/1组成的数列，每次可以将相邻两个数都变为它们异或的结果，
最后要使所有数变成0
这样就很容易想出贪心做法。如果有k个连续的1：
如果k是偶数，那么需要k/2次操作变为全0.
如果k是奇数，那么需要[k/2]次操作将k-1个变为全0，然后剩下一个与旁边的0
（由于前面[k/2]次操作产生了0，那一个旁边一定有0）进行2次操作变为全0.

 1 #include<cstdio>
 2 int d,n,ans;
 3 int a[110000],b[110000],num_b;
 4 int gcd(int a,int b)
 5 {
 6     int t;
 7     while(b!=0)
 8     {
 9         t=a;
10         a=b;
11         b=t%b;
12     }
13     return a;
14 }
15 int main()
16 {
17     int i;
18     scanf("%d",&n);
19     for(i=1;i<=n;i++)
20     {
21         scanf("%d",&a[i]);
22         d=gcd(d,a[i]);
23         a[i]%=2;
24     }
25     printf("YES\n");
26     if(d!=1)
27     {
28         printf("0\n");
29         return 0;
30     }
31     if(a[1]==1)
32         b[++num_b]++;
33     for(i=2;i<=n;i++)
34     {
35         if(a[i]==1&&a[i-1]==0)
36             b[++num_b]++;
37         else if(a[i]==1)
38             b[num_b]++;
39     }
40     for(i=1;i<=num_b;i++)
41     {
42         if(b[i]%2==0)
43             ans+=b[i]/2;
44         else
45             ans+=b[i]/2+2;
46     }
47     printf("%d\n",ans);
48     return 0;
49 }