题解：P7656 [BalticOI 1996] A NUMBER GAME (Day 2)

· · 题解

题意

最开始有两个数 n 和 m，有两个人 A 和 B 轮流进行操作，A 先手。每次操作的人可以选择 1 \le k \le \min(n,m)，让 n 变成 n-k。但是选择的 k 不能是之前自己或其他人选过的。最先无法选数的人输掉。

给出 n 和 m，问：谁会赢；对于所有 A 第一步能选择的 k，给出 A 必胜或 B 接下来选的 k 是多少时必胜。有多个答案时输出最大的那个。

题解

尊重随机跳题。

看到数据范围 m \le 20 就大彻大悟了。这样我们可以用一个 20 位的二进制数来保存一局游戏的某一状态，一个 int 就能存下。

在本题中，我们认为 x 的二进制下第 i 位表示当前有没有选过 i。为了方便使用 x>>i&1 判断，这里的第 i 位实际上是二进制从低位向高位数第 i+1 位。

对于某一个状态 x，我们可以统计出当前的 n 是多少，即 n'=n-\sum_{i=1}^{m}[\lfloor\frac{x}{2^i}\rfloor \bmod 2=1]i。

不难想到记忆化搜索。枚举下一步选的数是 k，如果是对方必输，那当前状态就是必赢局面；如果不论怎么选都没有对方必输的局面，那当前状态就是必输局面。边界条件是走不了下一步，那当前状态就是必输局面，可以和“没有对方必输的局面”情况合并。

判断能不能赢的事情解决了，但题目还要问怎么选取 k 才能必赢这样的问题。我们的记忆化搜索还要额外维护一个信息：如果必赢，需要如何选取 k 才能保证必赢。对于那个取最大值的要求，从大到小枚举 k 即可。

代码：

#include<iostream>
using namespace std;
int n,m;
int mem[1<<21|1];//=0表示失败；非零数字表示需要选择mem[x]就会必赢
bool vis[1<<21|1];
int dfs(int x){
    if(vis[x])  return mem[x];
    int curn=n;
    for(int i=1;i<=m;i++){
        if(x>>i&1){
            curn-=i;
        }
    }
    for(int i=min(curn,m);i>=1;i--){
        if(x>>i&1)  continue;
        int res=dfs(x|(1<<i));
        if(res==0){
            vis[x]=true;
            return mem[x]=i;
        }
    }
    vis[x]=true;
    return mem[x]=0;
}
int main(){
    cin >> n >> m;
    if(dfs(0)){
        cout << " A wins\n";
    } else{
        cout << " B wins\n";
    }
    for(int i=1;i<=m && i<=n;i++){
        if(i<=9)    cout << " ";
        cout << i << " ";
        int res=dfs(1<<i);
        if(res==0){
            cout << "winning" << "\n";
        } else{
            cout << res << "\n";
        }
    }
    return 0;
}

备注

这题的输出格式要求输出的前十行都有空格，所以代码会有奇怪的判断和空格。来源。