一、前言
本篇记录博弈论一些常见原理、做题技巧。
之前没有了解学习过博弈论，这篇文章可以当作记录学习笔记了。
二、初识博弈论
博弈论题目在竞赛中我感觉其实并不少见，只是需要技巧性很强，找到规律打代码很简单，而找不到基本上做不出来。所以认识一些经典规律题型还是很有必要的。
博弈嘛，它的题型基本上一眼就看出来是博弈论的题目了，题目基本上都是双人对弈。
从思路上来看，两个大点就是奇偶和对称。
从题型上来看，就有很多了，主要的有Nim博弈，SG函数，后面会以标题的形式出现。
先看几个题体会一下：
1.智乃的数字手串
思路：考虑最后状态——必定为相邻两数之和皆为奇数（包括首尾项之和），如232323。再分析一下它的特征：一定奇偶奇偶或偶奇偶奇这类一对一对的组合，也就是一定是偶数个。所以输家最后一定是面对偶数个数字的状态的。所以当清楚姐姐面对偶数个个数时，必输，因为她无论如何操作留给对手的都是必胜局；而面对奇数个数时，必赢，因为她总可以使其变成奇数而始对方处于必败状态。
代码：
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int kn[n+5];
for(int i=1;i<=n;i++)cin>>kn[i];
if(n%2==0)cout<<"zn"<<endl;
else cout<<"qcjj"<<endl;
}
return 0;
}2.抄作业
第一次听说这种叫法还挺新奇。
题目： N个小球 围成一圈 每次可取不超过k个的连续的若干个 取完了之后产生了空位 空位两侧的就不连续了 先手必胜还是后手必胜。
思路：要画个圈，假设4个，最多不超取2个，无论先手取几个，我都可以对着去取（抄作业），所以一定是我最后取完。故，若奇数，先手必胜；偶数，先手必败。（当然，k>=n除外）
可以看出这些题目都是针对奇偶的最终状态，想观看视频讲解的可以b站搜索牛客寒假集训营3，其中还有两个类似简单题目。
经过两个简单例子热身后，可以进一步分类学习了。
三、Nim游戏(^)
1.经典
给定 n 堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。
题目很简短，思想却不尽然。直接给出思想：将n堆石子的数量进行异或，为0则先手输，非0则先手胜。
思路：为什么？还是先分析最后状态，面对0、0、0、也就是石子都被取完情况的玩家必输，而在取石子过程中只要面对异或值为0的情况，无论如何操作，留给对手的一定是异或值非0情况；反之，如果异或值为1情况，总存在一种办法，使异或值为0。这叫留给对手的永远都是必败状态——故必胜。至于为什么要异或，为什么会这样，欢迎大家搜索讲解自行观看证明。
代码：
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
int ans,x;
cin>>ans;
for(int i=2;i<=n;i++){
cin>>x;
ans^=x;
}
if(ans==0)cout<<"No"<<endl;
else cout<<"Yes"<<endl;
return 0;
}
