BZOJ 1022 Luogu P4279 [SHOI2008]小约翰的游戏 (博弈论)

题目链接: (bzoj) https://www.lydsy.com/JudgeOnline/problem.php?id=1022

(luogu) https://www.luogu.org/problemnew/show/P4279

题解:

大力出奇迹系列。。

我找了一小时规律，瞎猜了一个结论，看着都不靠谱，结果它居然过了。。。。

结论: 若所有\(a_i\)都等于\(1\), 则后手必胜当且仅当\(n\)是奇数；否则后手必胜当且仅当所有\(a_i\)异或和为\(0\).

既然对了那就口胡一个证明：

(1) 当所有\(a_i\)都为\(1\)时，后手必胜当且仅当\(n\)是奇数，显然。

(2) 否则，如果大于\(1\)的数恰好有\(1\)个，那么如果\(n\)是奇数，则把大于\(1\)这一堆拿成\(1\), 否则把大于\(1\)这一堆拿成\(0\)即可，因此先手必胜。

(3) 如果大于\(1\)的数多于\(1\)个呢？我们发现第(2)种情况的结论符合Nim游戏的一般结论(后手必胜当且仅当异或和为\(0\))，而对于任何一个大于\(1\)的数恰好有\(1\)个的状态，不可能一步变成所有数都等于\(1\), 因此情况(1)不会影响到情况(3)。故大于\(1\)的数多于一个时，依然符合Nim游戏的一般结论。

记住，博弈论千万不要死抓着SG函数不放！胜负分析才是最本质的，另外有时候需要转化模型(如AGC002E).

代码

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cassert>

#include<iostream>

using namespace std;

inline int read()

{

	int x=0; bool f=1; char c=getchar();

	for(;!isdigit(c);c=getchar()) if(c=='-') f=0;

	for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^'0');

	if(f) return x;

	return -x;

}

int n;

int main()

{

	int T; scanf("%d",&T);

	while(T--)

	{

		int n; scanf("%d",&n);

		int x=0,c=0;

		for(int i=1; i<=n; i++) {int a; scanf("%d",&a); x^=a; c+=(a==1)?1:0;}

		if(c==n)

		{

			if(n&1) printf("Brother\n"); else printf("John\n");

		}

		else

		{

			if(x==0) printf("Brother\n"); else printf("John\n");

		}

	}

	return 0;

}

巴特西

BZOJ 1022 Luogu P4279 [SHOI2008]小约翰的游戏 (博弈论)

代码

最新文章

热门文章