博弈论初探 【BZOJ1022 SHOI2008 小约翰的游戏John】

tonyfang posted @ 2016年3月14日 21:14 in BZOJ with tags c++ OI , 435 阅读

题目1:有n堆石子,每堆有$a_i$个石子,规定每个人一次只能从一堆中选出若干个拿走,不可不取,最后取完石子的人胜利,假设每个人都很聪明,求先手必胜还是后手必胜。

我们令$t = a_1 \quad xor \quad a_2 \quad xor \quad a_3 \quad xor ... a_n$,则若$t=0$,则为利他态(用T表示),若$t>0$,为利己态(用S表示)。

定理1: 对于一个S态,在按照题目要求取了某些石子之后,一定能转变成T态。

目前状态是S态,那么t>0。

找出t的二进制表达下最高位是1的是第p位,那么从$a_1, a_2, a_3, ..., a_n$中肯定能够找到一个第p位是1的

那么设找到的数是$a_k$,那么令$a_k = a_k \quad xor \quad t$,显然,$a_k \quad xor \quad t < t$,那么就满足了命题要求,而且操作完成后$t' = 0$

定理2: 对于一个T态,在按照题目要求取了某些石子之后,一定能转变成S态。

定理2的正确性则是显然的。

 

结论1:任意一个S态,都能通过一次转移到T态;反之亦然。那么如果先手是S态那么就一定能通过定理1的移动获胜。

 

题目2:有n堆石子,每堆有$a_i$个石子,规定每个人一次只能从一堆中选出若干个拿走,不可不取,最后取完石子的人失败,假设每个人都很聪明,求先手必胜还是后手必胜。

定义状态:当一堆石子中只有一个石子,称为孤单堆;否则称为充裕堆。

在S,T态中,如果充裕堆的个数大于等于2;那么分别记为S2,T2;如果充裕堆的个数等于1,分别记为S1,T1;否则,分别记为S0,T0。

 

定理3: 对于一个S0态,由于孤单堆个数为奇数,那么必输;对于一个T0态,必赢。

很简单就能证明。

 

定理4: S1态是必胜态。

前提是方法正确。

如果孤单堆个数是奇数,那么就把充裕堆取完。

如果是偶数,那么把充裕堆取到只有1个石子。

 

定理5: S2态不能一次转化到T0态,但是只能一次转化到T2态。

显然由定理1,S态一次不会取完整堆,然后变为T态。

所以只能变成T2态。

 

定理6: T2态只能一次转化到S1,S2态。

很明显,不能一次取两堆。

 

定理7: S2态是必胜态。

先转化到T2态,T2可以转化到S1,S2态;

如果转化到S2态,继续转化到T2态。

如果转化到S1态,那么必赢。

 

结论2:必胜态:S1,S2,T0;必败态:T1,T2,S0。

例题:BZOJ 1022

题目摘要:小约翰经常和他的哥哥玩一个非常有趣的游戏:桌子上有n堆石子,小约翰和他的哥哥轮流取石子,每个人取的时候,可以随意选择一堆石子,在这堆石子中取走任意多的石子,但不能一粒石子也不取,我们规定取到最后一粒石子的人算输。小约翰相当固执,他坚持认为先取的人有很大的优势,所以他总是先取石子,而他的哥哥就聪明多了,他从来没有在游戏中犯过错误。小约翰一怒之前请你来做他的参谋。自然,你应该先写一个程序,预测一下谁将获得游戏的胜利。

【题解】就是题目2,参照结论2即可。

 

# include <stdio.h>
using namespace std;
int T, n, a[510];
int main() {
	scanf("%d", &T);
	while(T--) {
		int ans = 0;
		scanf("%d", &n);
		for (int i=1; i<=n; ++i) {
			scanf("%d", &a[i]);
			ans = ans ^ a[i];
		}
		bool flag;
		if (ans == 0) {
			flag = 0;
			for (int i=1; i<=n; ++i) 
				if(a[i] != 1) {
					flag = 1;
					break;
				}
		} else {
			flag = 1;
			for (int i=1; i<=n; ++i)
				if(a[i] > 1) {
					flag = 0;
					break;
				}
		}
		if (flag) puts("Brother");
		else puts("John");
	}
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter