CF798C Mike and gcd problem

思路：

首先如果数列的最大公约数大于1，直接输出即可。

奇数 + 奇数 = 偶数，奇数 + 偶数 = 奇数，偶数 + 偶数 = 偶数。把奇偶性不同的相邻的两个数都变成偶数需要2次操作，而把相邻的两个奇数都变成偶数需要1次操作，所以首先优先把相邻的奇数处理掉，再处理奇数和偶数相邻的情况。

实现：

 #include <iostream>

 using namespace std;

 int gcd(int a, int b)

 {

     return !b ? a : gcd(b, a % b);

 }

 int n, a[];

 int main()

 {

     cin >> n;

     int g = ;

     for (int i = ; i < n; i++)

     {

         cin >> a[i];

         if (!i) g = a[i];

         else g = gcd(g, a[i]);

     }

     if (g > )

     {

         puts("YES\n0\n"); return ;

     }

     int cnt = ;

     for (int i = ; i < n; i++)

     {

         if (!(a[i] & )) continue;

         else if (i +  < n)

         {

             if (a[i + ] & ) cnt++;

             else cnt += ;

             i++;

         }

         else cnt += ;

     }

     cout << "YES" << endl << cnt << endl;

     return ;

 }

标程：

 # include <bits/stdc++.h>

 using namespace std;

 # define fi cin

 # define fo cout

 int main(void)

 {

     int n;

     fi>>n;

     int g = ,v,cnt = ,ans = ;

     while (n --)

     {

         int v;

         fi>>v;

         g = __gcd(g,v);

         if (v & ) ++cnt;

         else ans += (cnt / ) +  * (cnt & ),cnt = ;

     }

     ans += (cnt / ) +  * (cnt & );

     fo << "YES\n";

     if (g == )

         fo << ans << '\n';

     else

         fo << "0\n";

     cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';

     return ;

 }

巴特西

CF798C Mike and gcd problem

最新文章

热门文章