Codeforces Global Round 22 C

https://codeforces.com/contest/1738/problem/C

题意
给你 n 堆石子，alice 和 bob 轮流拿其中的一堆，alice 先手，如果 alice 拿到石子数量之和为偶数就赢， 否则 bob 赢 ，二人都采取最优策略

思路
如果 alice 拿了一堆奇数个数的石子，如果无论 bob 接下来拿奇数或者偶数，alice 都能从剩下的石子堆中拿到奇数，alice win
如果 alice 拿了一堆偶数个数的石子，如果无论 bob 接下来拿奇数或者偶数，alice 都能从剩下的石子堆中拿到偶数，alice win

所以就把问题转化成了dp，维护 \(ji[n][cnt_1]\), \(ou[n][cnt_1]\) 即可

// #pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pb push_back
using namespace std;
int t, n, m, k;
int a[105];
bool f[105][105], ji[105][105];

void init() {
    f[1][1] = 0; f[1][0] = 1;
    f[2][0] = 1; f[2][1] = 1; f[2][2] = 0;

    ji[1][1] = 1; ji[1][0] = 0;
    ji[2][0] = 0; ji[2][1] = 1; ji[2][2] = 1;
    for(int i = 3; i <= 100; i++) {
        for(int cnt1 = 0; cnt1 <= i; cnt1++) {
            bool f1 = 0, f2 = 0;
            bool flag = cnt1;
            //拿1 f[i - 1][cnt1 - 1]
            // B: f[i - 2][cnt1 - 2] || f[i - 2][cnt1 - 1]
            if(cnt1 >= 2 && i >= cnt1) {
                flag &= ji[i - 2][cnt1 - 2];
            }
            if(cnt1 >= 1 && i >= cnt1 + 1) {
                flag &= ji[i - 2][cnt1 - 1];
            }
            f1 = flag;

            flag = (cnt1 < i);
            //拿0 f[i - 1][cnt1]
            //B: f[i - 2][cnt1 - 1] || f[i - 2][cnt1]
            if(cnt1 >= 1 && i >= cnt1 + 1) {
                flag &= f[i - 2][cnt1 - 1];
            }
            if(i >= cnt1 + 2) flag &= f[i - 2][cnt1];
            f2 = flag;

            f[i][cnt1] = (f1 || f2);
            // cout << f1 <<' '<<f2<<endl;
            // cout << i << ' ' << cnt1 << ' ' << f[i][cnt1] << endl; ///


            // ji
            f1 = 0; f2 = 0;
            //拿1
            // i-2 cnt1-1  i-2 cnt1-2
            flag = cnt1;
            if(cnt1 >= 1 && i >= cnt1 + 1) flag &= f[i - 2][cnt1 - 1];
            if(cnt1 >= 2) flag &= f[i - 2][cnt1 - 2];
            f1 = flag;

            //拿0
            // i-2 cnt1-1  i-2 cnt1
            flag = (cnt1 < i);
            if(cnt1 >= 1 && i >= cnt1 + 1) flag &= ji[i - 2][cnt1 - 1];
            if(i >= cnt1 + 2) flag &= ji[i - 2][cnt1];
            f2 = flag;

            ji[i][cnt1] = (f1 || f2);
        }
    }
}


int main(){
    init();
    int t; cin >> t;
    while (t--) {
        cin >> n;
        int cnt1 = 0;
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            if(a[i] % 2) cnt1++;
        }
        if(f[n][cnt1]) puts("Alice");
        else puts("Bob");
    }
    system("pause");
    return 0;
}