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

约定不等于承诺〃 2021-12-03 07:51 255阅读 0赞

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

(luogu) [https://www.luogu.org/problemnew/show/P4279][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; }

转载于:https://www.cnblogs.com/suncongbo/p/11178899.html

[https_www.lydsy.com_JudgeOnline_problem.php_id_1022]: https://www.lydsy.com/JudgeOnline/problem.php?id=1022
[https_www.luogu.org_problemnew_show_P4279]: https://www.luogu.org/problemnew/show/P4279