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

· · 题解

题意

有两个整数 n 和 m，A、B两人轮流操作（A先），每次选择一个正整数 k 满足 k\le\min(n,m) 且两人之前均没有选择过 k，然后将 n 减少 k。当某人无法操作时，游戏结束，最后操作的人获胜。假设两人都足够聪明。

输出格式：

首先输出一行表示 A 是否有必胜策略。接下来，设 A 第一次选择的数为 d，则对于每一个 d\in[1,\min(n,m)]，输出：若 A 此时可以必胜，输出单词 “winning”；否则，输出 B 为了保证必胜，下一步应选择的数的最大值。并且，除了 d\ge 10 的行的每行前均有空格，包括第一行。

具体的还是见代码吧。。。

Sol

由于 m\le 20，每次选的数互不相同，考虑状压 dp，设 f_S 表示当前操作者操作前选数状态为 S 时，当前操作者是否有必胜策略，这个容易记忆化搜索进行转移。

具体地，设 T 是 S 在加入一个新数后得到的新状态，若所有的 f_T 均为 1 即所有后继状态都是对方必胜，则我方必败，否则我方必胜。

输出详情见代码。

Code

#include<bits/stdc++.h>
#define eps 1e-6
#define MOD 998244353
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef pair<int,int> pii;
typedef pair<pii,int> piii;
#define fi first
#define se second
#define MAXN 300005
int n,m;
int f[1<<21];
int dfs(int sta){
    int x=n;// x 表示操作后得到的 n'
    for(int i=0;i<m;i++)
        if((sta>>i)&1)x-=i+1;
    if(!x)return f[sta]=0;// 边界，若无法操作则必败
    if(f[sta]!=-1)return f[sta];// 记忆化
    f[sta]=0;
    for(int i=0;i<m&&i<x;i++)
        if(!((sta>>i)&1)){
            int now=sta+(1<<i);
            if(!dfs(now))f[sta]=1;
        }
    return f[sta];
}
signed main(){
    cin>>n>>m,m=min(n,m);
    for(int i=0;i<(1<<m);i++)f[i]=-1;
    if(dfs(0))puts(" A wins");
    else puts(" B wins");
    for(int k=1;k<=m;k++){
        if(k<10)cout<<' '<<k<<' ';
        else cout<<k<<' ';
        // 毒瘤输出
        if(f[1<<(k-1)]==0){puts("winning");continue;}
        else{
            int x=n-k,mx=0;
            for(int i=0;i<m&&i<x;i++)
                if(i!=k-1)
                    if(f[(1<<(k-1))+(1<<i)]==0)
                        mx=i+1;
            cout<<mx<<'\n';
        }
    }

    return 0;
}

后记

题意错了，输出格式不对，下了数据才知道那个输出格式。当然也有可能是数据本身就有误。建议评绿。

如果数据改了，at 我一下。