自动搬运

查看原文

来自洛谷，原作者为

	yinpeichu2021 ypc

搬运于2025-08-24 22:31:54，当前版本为作者最后更新于2025-02-21 17:38:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

有两个整数 $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 我一下。