Mike and gcd problem CodeForces - 798C

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

新老客户大回馈,云服务器低至5折

题目

(智商题 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 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:P1850 换教室

下一篇:Bank Hacking CodeForces - 796C