题解：P13720 [GCPC 2024] Even Odd Game

Xycxxx · 2026-01-26 18:38:00 · 题解

我们只关心每张牌对奇偶性的影响，故给每个牌重新分类一下。

• 加一个偶数或乘一个奇数，对奇偶性没影响。
• 加一个奇数会改变奇偶性。
• 乘一个偶数会变为偶数。

如此可以设计一个 \mathcal{O}(n^3) 的博弈 dp，设 f_{i,j,k,t} 表示还剩多少个类型一/二/三卡牌，当前数的奇偶性 t 为 0/1 表示偶/奇，当前进行的一方是必胜还是必败。

转移是简单的，考虑刷表法，枚举放了哪一个，如果能转移到的点全是必败点，那么当前点必胜，初始化根据题意即可。

此时我们直接将每种类型的卡牌存下来，从必胜点开始走，每次走到一个使下一方必败的点即可。

#include <bits/stdc++.h>
#define int long long
#define rd read()
using namespace std;
inline int read() {
    int x = 0; char ch = getchar();
    while (ch < '0' || ch > '9')ch = getchar();
    while (ch >= '0' && ch <= '9')x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return x;
}
const int N = 305; 
int n, x, t1, t2, t3, f[N][N][N][2];
multiset<pair<char, int>> s1, s2, s3;
signed main() {
    n = rd;
    for (int i = 1, k; i <= n; ++i) {
        char op; cin >> op; k = rd;
        if (op == '+') {
            if (k & 1)s2.insert({op, k}), ++t2;
            else s1.insert({op, k}), ++t1;
        } else {
            if (k & 1)s1.insert({op, k}), ++t1;
            else s3.insert({op, k}), ++t3;
        }
    }
    x = rd; f[0][0][0][0] = (n % 2), f[0][0][0][1] = 1 - n % 2; 
    for (int i = 0; i <= t1; ++i) for (int j = 0; j <= t2; ++j) for (int k = 0; k <= t3; ++k) for (int t = 0; t < 2; ++t) {
        f[i + 1][j][k][t] |= !f[i][j][k][t];
        f[i][j + 1][k][t] |= !f[i][j][k][!t];
        f[i][j][k + 1][t] |= !f[i][j][k][0];    
    }
    int t = x % 2;
    if (f[t1][t2][t3][t]) {
        cout << "me" << endl; 
        while (1) {
            if (!n)break;--n;
            if (t1 && !f[t1 - 1][t2][t3][t]) {--t1; cout << s1.begin() -> first << ' ' << s1.begin() -> second << endl; s1.erase(s1.begin());}
            else if (t2 && !f[t1][t2 - 1][t3][!t]) {--t2; cout << s2.begin() -> first << ' ' << s2.begin() -> second << endl; s2.erase(s2.begin()); t = !t;}
            else {--t3; cout << s3.begin() -> first << ' ' << s3.begin() -> second << endl; s3.erase(s3.begin()); t = 0;}
            if (!n)break;--n;   
            char op; cin >> op; int k = rd;  
            if (s1.count({op, k}))s1.erase(s1.find({op, k})), --t1;
            else if (s2.count({op, k}))s2.erase(s2.find({op, k})), --t2, t = !t;
            else s3.erase(s3.find({op, k})), --t3, t = 0;
        }
    } else {
        cout << "you" << endl;
        while (1) {
            if (!n)break;--n;
            char op; cin >> op; int k = rd;
            if (s1.count({op, k}))s1.erase(s1.find({op, k})), --t1;
            else if (s2.count({op, k}))s2.erase(s2.find({op, k})), --t2, t = !t;
            else s3.erase(s3.find({op, k})), --t3, t = 0;
            if (!n)break;--n;
            if (t1 && !f[t1 - 1][t2][t3][t]) {--t1; cout << s1.begin() -> first << ' ' << s1.begin() -> second << endl; s1.erase(s1.begin());}
            else if (t2 && !f[t1][t2 - 1][t3][!t]) {--t2; cout << s2.begin() -> first << ' ' << s2.begin() -> second << endl; s2.erase(s2.begin()); t = !t;}
            else {--t3; cout << s3.begin() -> first << ' ' << s3.begin() -> second << endl; s3.erase(s3.begin()); t = 0;}
        }
    }
    return 0;
}