题解 P4279 【[SHOI2008]小约翰的游戏】

# 一道博弈论的入门题吧 首先说说博弈论是什么： 博弈论又被称为对策论（Game Theory），既是现代数学的一个新分支，也是运筹学的一个重要学科。 博弈论主要研究公式化了的激励结构间的相互作用，是研究具有斗争或竞争性质现象的数学理论和方法。 博弈论考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略。（以上摘自百度百科） 其中，博弈论最经典的题目就是取石子问题啦，而本题则又是一道基础的取石子题目 ## 题目大意 两个人在n堆石子中轮流取，每次最少一个，最多取完这堆，取走最后一颗石子的人为负，问谁会胜利 如果不知道博弈论的人，估计深搜啊什么神奇的东西弄一弄，也就弄不出来的（不排除某些大佬）。实际上我们判断胜负只需要判断能否达到必胜态（必败态），然后逐渐往这两个状态去靠近，直到达到某个状态，判定出胜负为止。 在本题，关于必胜态和必败态有两个结论 John必胜：a1^a2^......^an=1 John必败：a1^a2^.......^an!=0 一般只需要知道这两个公式再加上特判就可以轻松做出本题啦 ### 代码 ``` #include<bits/stdc++.h> using namespace std; inline int read() { int x=0; char c=getchar(); bool flag=0; while(c<'0'||c>'9') {if(c=='-')flag=1;c=getchar();} while(c>='0'&&c<='9'){x=(x+(x<<2)<<1)+ c-'0';c=getchar();} return flag?-x:x; } int t=read(),n,ans,flag; int main() { while(t--) { n=read(),flag=1,ans=0; for(int i=1;i<=n;++i) { int x=read(); if(x!=1) flag=0; ans^=x; } if(flag) if(n&1) printf("Brother\n");else printf("John\n"); else if(ans) printf("John\n");else printf("Brother\n"); } } ``` 但是我们学习不能只是为了切掉某一题，那么我下面给出证明： 对于某个局面(a1,a2,...,an)，若a1^a2^...^an!=0，一定存在某个合法的移动，将ai改变成aii后满足a1^a2^...^ai'^...^an=0。不妨设a1^a2^...^an=x，则一定存在某个ai使得ai^x<ai一定成立。则如果我们可以将ai改变成aii=ai^x，此时a1^a2^...^aii^...^an=a1^a2^...^an^x=0。 对于某个局面(a1,a2,...,an)，若a1^a2^...^an=0，一定不存在某个合法的移动，将ai改变成aii后满足a1^a2^...^ai'^...^an=0。因为异或运算性质，由a1^a2^...^an=a1^a2^...^aii^...^an可以得到ai=aii。所以将ai改变成aii不是一个合法的移动 所以在这道题中如果当前是必胜的话，那么就要下一个移动的人必败，所以就要改变一个ai变成aii使得原本的a1^...ai^...^an!=0变成a1^...aii...^an=0 证明完毕 呃我差不多讲完了，如果对于博弈论还想有更多了解的话，我推荐下面几个博客（不是我的） [斐波那契博弈（Fibonacci Nim）](https://blog.csdn.net/dgq8211/article/details/7602807) [威佐夫博弈](https://blog.csdn.net/qq_41311604/article/details/79980882) [稍微综合版博弈论](https://blog.csdn.net/qq_33765907/article/details/51174524) 以上的博客都是我随便找的，~~才不是因为我自己没写过博弈论的博客~~