Codeforces Round #651 (Div. 2)（补题ing)

B. GCD Compression【思维】
题意：给出一个2n数组a，从a数组选出2（n-1），每次取两个数，其和加入b数组，使b数组构成一个n-1长且gcd(b1,b2,...,bn)>1，输出n-1对数在a数组的下标。
思路：奇数两两配对，偶数两两配对， gcd至少是2.

void solve(){
    cin >> n;
    vector<int> odd, even;
    for(int i = 1; i <= 2 * n; ++ i){
        cin >> mp[i];
        if(mp[i] & 1)    odd.push_back(i);
        else    even.push_back(i); 
    }
    int cnt = 0; 
    if(odd.size() & 1)    odd.pop_back();
    for(int i = 0; i < odd.size(); i += 2){
        printf("%d %d\n", odd[i], odd[i + 1]);
        cnt ++;
        if(cnt == n - 1)    break;
    }    
    for(int i = 0; i < even.size() && cnt < n - 1; i += 2){
        printf("%d %d\n", even[i], even[i + 1]);
        cnt ++;
        if(cnt == n - 1)    break;
    }    
}

C. Number Game 【思维数学博弈】
题意：给出一个n，两个轮流进行以下两个操作中的一个最后不能操作的一方为败方，问谁为胜方。
1、n除以一个奇数因子【可以是自己】
2、n（n>1）减去1
思路：先把这个数质因数分解。以下状态先手必胜：

这个数是奇数或者是2；
这个数中只含有一个2，且有多于一个其他质因子【奇数的积一定是奇数，一下除到只剩一个2和一个奇数因子，对手只能除这个奇数因子，给自己留下2，必胜】；
这个数中含有多个2，且有至少一个其他质因子【直接把其他的除掉，留下一个质因子只剩2的偶数，只能选择-1而留下一个奇数】

void Awin(){ puts("Ashishgup");}
void Fwin(){ puts("FastestFinger");}

void solve(){
    cin >> n;
    if(n == 1)    Fwin();
    else if(n & 1 || (n == 2))    Awin();
    else{
        ll even = 1, odd = 0;
        int rec = n;
        for(int i = 2; i <= rec / i; ++ i){
            if(rec % i == 0){
                while(rec % i == 0){
                    rec /= i;
                    if(i & 1)    odd ++;
                    else    even *= i;
                }
            }
        }
        if(rec > 1){
            if(rec & 1)    odd ++;
            else    even *= rec;
        }
        //printf("odd = %d even = %d\n", odd, even);
        if((odd && even > 2) || (even == 2 && odd > 1))    Awin();
        else    Fwin();
    }
}

D - Odd-Even Subsequence【思维二分贪心】
题意：给出一个n个数的数组，从中挑选k个数，形成一个新的数组，定义该数组的值为min(max(s1,s3,s5...,s2,s4,s6...)),问该数组值最小为多少。

思路：考虑二分。【如果某个值凑不出来，那比他小的也一定凑不出来。】
二分的时候传入一个flag表示这次判断的是奇数位置凑还是偶数位置凑。
以奇数为例：如果找到一个比mid小的数，就把他加入奇数组中，然后下一个立即加入偶数组【这样可以保证有尽可能多的选择给下一个奇数组】。反之亦然。

bool check(int mid, bool save){
    int cnt = 0, idx = 1;
    bool f = save;
    for(; idx <= n; ++ idx){
        if(!f)    cnt ++, f = !f;
        else{
            if(a[idx] <= mid)    cnt ++, f = !f;
        }
    }    
    return cnt >= k;
}

void solve(){
    cin >> n >> k;
    int maxx = 0;
    for(int i = 1; i <= n; ++ i)    scanf("%d", &a[i]), maxx = max(maxx, a[i]);
    int l = 0, r = maxx;
    while(l < r){
        int mid = l + r >> 1;
        if(check(mid, 0) || check(mid, 1))    r = mid;
        else    l = mid + 1;
    }
    cout << r;
}

E - Binary Subsequence Rotation【思维】
题意：给出n长两个字符数组a、b，可以取a数组的任意子序列进行顺时针旋转，sn->s1,s1->s2...。问a字符数组能否转变为b字符数组。
思路：首先判断01是否相等。
然后把两个字符串中不等的位置单独提取出来做进一步判断。
考虑相连的1和0一定没有作用【连续重复的1还会被再转到一次，对答案没有贡献】（因为如果是1100要转成0011，取这4个转成0110,0011要两步，取两个10转也是2步）
所以答案就是判断有多少个101010...或者010101...

void solve(){
    cin >> n >> s1 + 1 >> s2 + 1;
    for(int i = 1; i <= n; ++ i)    if(s1[i] == '1')    a1 ++;
    for(int i = 1; i <= n; ++ i)    if(s2[i] == '1')    a2 ++;
    if(a1 != a2)    puts("-1");
    else{
        int ans1 = 0, ans2 = 0, one = 0, zero = 0;
        for(int i = 1; i <= n; ++ i) {
            if(s1[i] == s2[i])    continue ;
            tmp[++ idx] = s1[i];
        }
        for(int i = 1; i <= idx; ++ i){
            if(tmp[i] == '1'){
                if(zero > 0)    zero --;
                else    one ++;
            }else{
                if(one > 0)    one --;
                else    zero ++;
            }
            ans1 = max(ans1, one);
            ans2 = max(ans2, zero);
        }
        cout << ans1 + ans2;
    }
}

注意最后答案是10的数量和01的数量相加而不是取最大。
考虑1001这个序列，10是一个，01是一个，one > 0的时候表示这个序列以1打头， zero > 0的时候表示这个序列以0打头。