题解：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

即可。

代码：

CPP

#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;
}

备注

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

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

文章操作

题意

题解

备注

相关推荐

评论

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