codeforces 798C.Mike and gcd problem 解题报告

题目意思：给出一个n个数的序列：a1,a2,...,an （n的范围[2,100000]，ax的范围[1,1e9] ）

现在需要对序列a进行若干变换，来构造一个beautiful的序列： b1,b2, ..., bn，使得最大公约数 gcd(b1,b2,...,bn) > 1。

变换：  任意ai，ai+1 进行一次操作时，可以用 ai-ai+1, ai+ai+1 来替换。

问序列 a 构造成 序列 b ，使得gcd（b序列） > 1 的最小操作次数

题目解析：

　　首先，这个题目是肯定有解的，也就是恒输出yes

     试想一下，相邻两个数之间无非就是四种情况：

     （1）对于同偶情况，不需要做转换，公约数直接为2；

     （2）对于同奇情况，只需要变换一次，两奇数进行加减操作，最终结果是偶数，公约数此时为2

　　（3）一奇一偶，变换两次： ai, ai+1 ——》 ai-ai+1, ai+ai+1  ——》2（ai+1，ai） ——》 公约数为2

　　此时问题就转化成： 构造一个序列所有数的公约数为2的最少操作次数。

      当然，在处理序列之前，要先判断整个序列是否已经有公约数了（注意，并不一定为2）； 如果有，代表已经符合条件：gcd(b1,b2,...,bn) > 1，直接输出0即可。（不需要对序列a进行任何操作。

两种方法

方法一 ：贪心+数论

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

const int maxn = 1e5 + 5;
int a[maxn];

int GCD(int b1, int b2)
{
    if (b2 == 0)
        return b1;
    return GCD(b2, b1%b2);
}

int main()
{
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
    #endif // ONLINE_JUDGE

    int n;
    while (scanf("%d", &n) !=EOF) {
       scanf("%d", &a[0]);
       int t=a[0], cnt = 0;
       for (int i = 1; i < n; i++) {
        scanf("%d", &a[i]);
        t = GCD(t, a[i]);
        if (t > 1) { cnt++; }
       }
       printf("YES
");
       if ( cnt == n-1 ) { printf("0
"); }  // all is even
       else {
            // scan two times;
            int ans = 0;
            for (int i = 0; i < n; i++) {
                if (a[i]%2 && a[i+1]%2 && i+1 < n) {  // two odd
                    ans += 1;
                    a[i] = 2;
                    a[i+1] = 2;
                }
            }

            for (int i = 0; i < n; i++) {
                if (i+1 < n && (a[i]%2 && a[i+1]%2 == 0)|| (a[i]%2 == 0 && a[i+1]%2) ) {   // one odd one even
                    ans += 2;
                    a[i+1] = 2;
                }
            }
            printf("%d
", ans);
       }
    }
    return 0;
}

方法二：动态规划（参考网上的，dp是我的痛~  = =）

设：

dp[i][0]： 前i-1个数为偶数，第i个数为偶数的最少操作次数
dp[i][1]:  前i-1个数为偶数，第i个数为奇数的最少操作次数

如果第 i 个数是奇数，
dp[i][0] = min(dp[i-1][0]+2, dp[i-1][1]+1);

dp[i][1] = min(dp[i-1][0], inf);

如果第 i 个数是偶数，

dp[i][0] = min(dp[i-1][0], dp[i-1][1]+2);
dp[i][1] = inf;

还有一个初始化的问题需要注意下：

dp[0][!(a[0]%2)] = inf;      ——》 这个要细心体会下
假设序列中第一个数就是偶数，dp[0][0]= 0     dp[0][1]= inf

假设序列中第一个数就是奇数，dp[0][0]= inf   dp[0][1]= 0

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

const int inf = 10000000;
const int maxn = 1e5 + 5;
int a[maxn];
// dp[i][0]： 前i-1个数为偶数，第i个数为偶数的最少操作次数
// dp[i][1]:  前i-1个数为偶数，第i个数为奇数的最少操作次数
int dp[maxn][2];

int GCD(int b1, int b2)
{
    if (b2 == 0)
        return b1;
    return GCD(b2, b1%b2);
}

int main()
{
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
    #endif // ONLINE_JUDGE

    int n;
    while (scanf("%d", &n) !=EOF) {
       scanf("%d", &a[0]);
       int t=a[0], cnt = 0;

       for (int i = 1; i < n; i++) {
            scanf("%d", &a[i]);
            t = GCD(t, a[i]);
            if (t > 1) { cnt++; }
       }
       printf("YES
");
       if ( cnt == n-1 ) { printf("0
"); }  // all 有公约数

       else {
            memset(dp, 0, sizeof(dp));
            dp[0][!(a[0]%2)] = inf;

            for (int i = 1; i < n; i++) {
                if (a[i]%2) {     // odd
                    dp[i][0] = min(dp[i-1][0]+2, dp[i-1][1]+1);
                    dp[i][1] = min(dp[i-1][0], inf);
                }
                else {
                    dp[i][0] = min(dp[i-1][0], dp[i-1][1]+2);
                    dp[i][1] = inf;

                }
            }
            printf("%d
", dp[n-1][0]);
       }
    }
    return 0;
}