Solution.

Fall_Dream · 2026-01-26 08:31:43 · 题解

:::info[题解引用声明] 本题解思路大部分来自 Crazyouth 的题解，已获得原作者授权。 :::

感觉比原作者讲的清晰点。

因为只关心奇偶性，我们可以在模 2 意义下分析。

设当前数字 x \in \{0,1\}。

我们可以根据将卡牌对初始值的效果把牌分成三份：

为表述方便，令 a 为一类卡牌数量，b 为二类卡牌数量，c 为三类卡牌数量。

定义 vis_{i,j,k,u} 为游戏进行到有 i 个一类卡牌，j 个二类卡牌，k 个三类卡牌，当前数为 u 时当前回合的玩家能否有必胜策略。

初始状态：vis_{0,0,0,0}=n\bmod 2,vis_{0,0,0,1}=\lnot(n\bmod 2)。

:::info[原因。] 若 n 为奇数，则结束回合轮次一定是先手操作。\ 显然若最终数为 0 则先手必败，反之亦然。

若 n 为偶数，则结束回合轮次一定是后手操作。\ 显然若最终数为 0 则后手必胜，反之亦然。

可以发现这个其满足 vis_{0,0,0,0}=n\bmod 2,vis_{0,0,0,1}=\lnot(n\bmod 2)。 :::

然后记忆化搜索，只要有一个后继状态能让对手不存在必胜策略（即必败）那这个状态就有必胜策略了。反之，若所有后继状态都能让对手可以必胜，那这个状态就必败。

代码：

bool dfs(int x,int y,int z,int u){
    if(x<0||y<0||z<0) return 1;
    if(~vis[x][y][z][u]) return vis[x][y][z][u];
    return vis[x][y][z][u]=!dfs(x-1,y,z,u)||!dfs(x,y-1,z,u^1)||!dfs(x,y,z-1,0);
}

然后思路就很明确了。搜出 vis_{a,b,c,x} 是否为 1，即初始局面先手是否必胜。如果必胜我们就抢先手，否则我们就拿后手。

然后与交互库交互时就一直让交互库必败就行了。

复杂度 O(n^3)，显然能通过。

实现可能有点复杂，但是其实可以比较简单。

:::info[简单实现（比较丑）]

#include<bits/stdc++.h>
#define sz(x) st[x].size()
#define x first
#define y second
using namespace std;
typedef pair<char,int> pci;
int vis[305][305][305][2],x;
set<pci> st[4];
bool dfs(int x,int y,int z,int u){
    if(x<0||y<0||z<0) return 1;
    if(~vis[x][y][z][u]) return vis[x][y][z][u];
    return vis[x][y][z][u]=!dfs(x-1,y,z,u)||!dfs(x,y-1,z,u^1)||!dfs(x,y,z-1,0);
}
void Del(char Op,int X){
    if(st[1].count({Op,X})) st[1].erase(st[1].find({Op,X}));
    if(st[2].count({Op,X})) st[2].erase(st[2].find({Op,X})),x^=1;
    if(st[3].count({Op,X})) st[3].erase(st[3].find({Op,X})),x=0;
}
#define solve(u) \
auto it=st[u].begin();\
auto [u1,u2]=*it;\
cout<<u1<<" "<<u2<<endl;\
st[u].erase(it);
void runner(){
    while(1){
        int a=sz(1),b=sz(2),c=sz(3),X;char Op;
        if(a&&!vis[a-1][b][c][x]){solve(1);a--;}
        else if(b&&!vis[a][b-1][c][!x]){solve(2);b--;x^=1;}
        else if(c&&!vis[a][b][c-1][0]){solve(3);c--;x=0;}
        if(!a&&!b&&!c) exit(0);
        cin>>Op>>X;
        Del(Op,X);
    }
}
signed main(){
    memset(vis,-1,sizeof vis);
    int n;//c1= 滚木,c2=~x,c3=1
    cin>>n;
    char op;
    for(int i=1;i<=n;i++) cin>>op>>x,st[(((op=='+'&&(~x&1))||(op=='*'&&(x&1)))?1:(op=='+'&&(x&1)?2:3))].insert({op,x});
    cin>>x,x&=1;
    vis[0][0][0][0]=(n%2);
    vis[0][0][0][1]=!(n%2);
    if(dfs(sz(1),sz(2),sz(3),x)){
        cout<<"me"<<endl;runner();
    }else{
        cout<<"you"<<endl;
        char Op;int X;cin>>Op>>X;
        Del(Op,X);

        runner();
    }
}

:::

:::info[AI 重构的代码（更具有可读性）]

#include <bits/stdc++.h>
using namespace std;

typedef pair<char, int> pci;
int dp[305][305][305][2];  // dp[a][b][c][p]: 剩余卡牌状态(a,b,c)和当前奇偶性p时的胜负
set<pci> s[4];  // s[1],s[2],s[3]分别存三类卡牌
int cur;  // 当前数字的奇偶性

// 获取卡牌类型
int type(char op, int x) {
    if (op == '+') {
        return (x % 2) ? 2 : 1;  // +奇数:2, +偶数:1
    } else { // op == '*'
        return (x % 2) ? 1 : 3;  // *奇数:1, *偶数:3
    }
}

// 记忆化搜索
bool dfs(int a, int b, int c, int p) {
    if (a < 0 || b < 0 || c < 0) return true;  // 非法状态
    if (dp[a][b][c][p] != -1) return dp[a][b][c][p];

    // 尝试三种出牌方式，如果有一种能让对手必败，则当前玩家必胜
    bool win = false;
    if (a) win |= !dfs(a - 1, b, c, p);            // 出类型1
    if (b) win |= !dfs(a, b - 1, c, p ^ 1);        // 出类型2
    if (c) win |= !dfs(a, b, c - 1, 0);            // 出类型3

    return dp[a][b][c][p] = win;
}

// 移除卡牌
void remove(char op, int x) {
    int t = type(op, x);
    s[t].erase({op, x});
    if (t == 2) cur ^= 1;    // 类型2翻转奇偶性
    else if (t == 3) cur = 0; // 类型3结果必为偶数
}

// 玩家出牌
void play(int t) {
    auto [op, x] = *s[t].begin();
    cout << op << " " << x << endl;
    s[t].erase({op, x});
    if (t == 2) cur ^= 1;
    else if (t == 3) cur = 0;
}

// 游戏主循环
void run() {
    while (true) {
        int a = s[1].size(), b = s[2].size(), c = s[3].size();

        if (a + b + c == 0) break;  // 没有牌了，游戏结束

        bool played = false;

        // 选择必胜的出牌方式
        if (a && !dfs(a - 1, b, c, cur)) {
            play(1);
            played = true;
        } else if (b && !dfs(a, b - 1, c, cur ^ 1)) {
            play(2);
            played = true;
        } else if (c && !dfs(a, b, c - 1, 0)) {
            play(3);
            played = true;
        }

        if (s[1].size() + s[2].size() + s[3].size() == 0) break;
        // 读取对手出牌
        char op; int x;
        cin >> op >> x;
        remove(op, x);
    }
    exit(0);
}

int main() {
    memset(dp, -1, sizeof dp);

    int n;
    cin >> n;

    // 读入卡牌
    for (int i = 0; i < n; i++) {
        char op; int x;
        cin >> op >> x;
        int t = type(op, x);
        s[t].insert({op, x});
    }

    // 读入初始值
    int start;
    cin >> start;
    cur = start % 2;

    int a = s[1].size(), b = s[2].size(), c = s[3].size();

    // 初始化终点状态：当所有牌都出完时的胜负
    dp[0][0][0][0] = n % 2;      // 最终为偶数，轮到n%2玩家赢
    dp[0][0][0][1] = 1 - (n % 2); // 最终为奇数，轮到1-(n%2)玩家赢

    // 计算当前状态胜负
    bool canWin = dfs(a, b, c, cur);

    if (canWin) {  // 先手能赢
        cout << "me" << endl;
        run();
    } else {       // 先手不能赢，选择后手
        cout << "you" << endl;
        char op; int x;
        cin >> op >> x;
        remove(op, x);
        run();
    }

    return 0;
}

:::