博弈论
Ezio_0420
2018-04-12 19:30:32
# ~~这个目前用不到，先放在这里，以后再学~~
## [nim游戏](https://www.luogu.org/problemnew/show/P2197)
甲，乙两个人玩Nim取石子游戏。
nim游戏的规则是这样的：地上有n堆石子（每堆石子数量小于10000），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手，且告诉你这n堆石子的数量，他想知道是否存在先手必胜的策略。
输入格式：
第一行一个整数T<=10,表示有T组数据
接下来每两行是一组数据，第一行一个整数n，表示有n堆石子，n<=10000;
第二行有n个数，表示每一堆石子的数量
输出格式：
共T行，如果对于这组数据存在先手必胜策略则输出"Yes",否则输出"No"，不包含引号，每个单词一行。
解法：
裸的NimmGame
```cpp
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int a[10001];
int Nimm_Game(int n){
int flag=0;
for(int i = 1;i<=n;i++){
flag^=a[i];
}
if(flag) return 1;
return 0;
}
int main(){
int t,n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i = 1;i<=n;i++){
scanf("%d",&a[i]);
}
if(Nimm_Game(n)) printf("Yes\n");
else printf("No\n");
memset(a,0,sizeof(a));
}
return 0;
}
```
------------
```cpp
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
const int N=1e8+3;
//巴什博奕：只有一堆n个物品，两人轮流从中取出(1~m)个
int Bash_Game(int n,int m){
if(n%(m+1)!=0) return 1;
return 0;
}
//尼姆博奕：有n堆，每堆有a[i]>0个物品，依旧是两人轮流取
int a[N];
int Nimm_Game(int n){
int flag=0;
for(int i = 1;i<=n;i++) flag^=a[i];
if(flag) return 1;
return 0;
}
//如果是n非常大，且每一堆物品的数量是连续的整数的情况
//需要考虑连续的整数的异或和
int xor_n(int n){
int t = n & 3;
if(t & 1) return t / 2 ^ 1;
return t / 2 ^ n;
}
int Special_Nimm_Game(int n){
// int flag=0;
// for(int i = 1;i<=n;i++){
// flag^=xor_n(a[i]);
// }
// if(flag) return 1;
if(xor_n(n)) return 1;
return 0;
}
int cnt;
int main(){
int n=1;
for(int i = 1;i<=1000001;i++) a[i]=i;
while(n<=1000000){
n++;
if(Nimm_Game(n)==Special_Nimm_Game(n)) continue;
cnt=1;
}
if(cnt){
puts("Wrong");
return 0;
}
puts("Yes");
return 0;
}
```