博弈论题单
题单介绍
[博弈论 SG函数](https://blog.csdn.net/strangedbly/article/details/51137432)、[SG函数](https://59388.blog.luogu.org/game-theory-3)
[Nim 游戏及其变形](https://blog.csdn.net/clover_hxy/article/details/53818624?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522162555732616780262533456%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=162555732616780262533456&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~baidu_landing_v2~default-5-53818624.first_rank_v2_pc_rank_v29&utm_term=Moore%E2%80%99s+Nimk&spm=1018.2226.3001.4187)
[浅谈算法——博弈论（从零开始的博弈论）](https://www.luogu.com.cn/blog/Wolfycz/qian-tan-suan-fa-bo-yi-lun-zong-ling-kai-shi-di-bo-yi-lun-post)
[博弈论 日报](https://www.luogu.com.cn/blog/FrozaFerrari/bo-yi-lun#)
[贾志豪《组合游戏略述——浅谈SG游戏的若干拓展及变形》](https://wenku.baidu.com/view/25540742a8956bec0975e3a8.html)
[同学的博弈论题单（含常见博弈的结论及证明）](https://www.luogu.com.cn/training/81690#information)
1. [P3150 pb的游戏（1）](https://www.luogu.com.cn/problem/P3150) 看样例都能猜出：奇数zs wins，偶数pb wins。原因：当目前只能分1时必败，能分2必胜,以此类推，能分4时将4分成3+1则必胜，能分偶数时必胜，只能分奇数时必败，因为奇数不管怎么分都会分出偶数，而偶数可以分成两个奇数，如此下去，能分偶数的就必胜。
2. [P1488 肥猫的游戏](https://www.luogu.com.cn/problem/P1488) [我的题解](https://blog.csdn.net/Robin2321/article/details/118436945)
3. [P1199 [NOIP2010 普及组] 三国游戏](https://www.luogu.com.cn/problem/P1199) 经过分析发现答案即为每一行次大数的最大值。
4. [P1288 取数游戏II](https://www.luogu.com.cn/problem/P1288) 显然每个人走过的路都会被清零，否则另一个人可以返回并取完，那么这个人就败了。所以我们只需要知道包括1在内的最长非零路径长度s即可，s为奇数则必胜。
5. [P1290 欧几里德的游戏](https://www.luogu.com.cn/problem/P1290) 经过分析后发现，胜负只与每次可分的次数有关，若在某个人分时第一次出现可分的次数大于一的情况，那么这个人就掌控者游戏的胜负，即必胜。若每次都只能减一次，要另外考虑。
6. [P2197 【模板】nim 游戏](https://www.luogu.com.cn/problem/P2197) 模板
7. [P4101 [HEOI2014]人人尽说江南好](https://www.luogu.com.cn/problem/P4101) 分析后发现规律。注意当
8. [P4279 [SHOI2008]小约翰的游戏](https://www.luogu.com.cn/problem/P4279) anti-Nim
9. [P2252 [SHOI2002]取石子游戏|【模板】威佐夫博弈](https://www.luogu.com.cn/problem/P2252) 结论：当第一个数是差值的1.618倍时，先手必败。
Beatty 定理：
10. [CF15C Industrial Nim](https://www.luogu.com.cn/problem/CF15C) 这道题暴力就是一个简单的nim博弈。注意开long long。
```cpp
由(0^1^2^...^(l-1))^(0^1^2^...^r)=(r^(r+1)^(r+2)^...^(l-1))
我们只需要知道0^1^2^...^x 为多少即可。
由a^(a+1)=1//a为偶数
我们可以两两分成一组计算。
int solve(int x){//返回值为0^1^2^...^x
if(x%4==0) return x;
if(x%4==1) return 1;
if(x%4==2) return x+1;
if(x%4==3) return 0;
}
```
11. [P3480 [POI2009]KAM-Pebbles](https://www.luogu.com.cn/problem/P3480) 实质上是阶梯nim
12. [P2734 [USACO3.3]游戏 A Game](https://www.luogu.com.cn/problem/P2734) 博弈+区间DP，设dp[l][r]为先手在区间l~r取到的最大值，那么后手在区间l~r取到的最大值为是s[r]-s[l-1]-dp[l][r]，其中s是前缀和，那么状态转移方程就有了：
```cpp
dp[l][r]=max(dp[l][r],s[r]-s[l]-dp[l+1][r]+a[l],s[r-1]-s[l-1]-dp[l][r-1]+a[r]);
```
13. [P2964 [USACO09NOV]A Coin Game S](https://www.luogu.com.cn/problem/P2964) 博弈+DP，设dp[i][j]为还剩下i枚硬币且上一次取了j枚，将硬币倒序输入并计算前缀和，则状态转移方程为：
```cpp
dp[i][j]=dp[i][j-1];
int k=j<<1;
if(k<=i) dp[i][j]=max(dp[i][j],s[i]-dp[i-k][k]);
k--;
if(k<=i) dp[i][j]=max(dp[i][j],s[i]-dp[i-k][k]);
```
14. [P2575 高手过招](https://www.luogu.com.cn/problem/P2575) 棋子不好考虑，可以考虑空格，空格将棋盘划分成多个部分，然后就是个简单的阶梯nim了。
15. [P2148 [SDOI2009]E&D](https://www.luogu.com.cn/problem/P2148) 诡异的结论及证明（没看懂）。
16. [P2599 [ZJOI2009]取石子游戏](https://www.luogu.com.cn/problem/P2599) 按照[sqk3_cab](https://www.luogu.com.cn/blog/4ghy-cab/p2599-qu-dan-zi-you-hu-ti-xie)的思路做的，但是貌似是错的？正解那诡异的DP我看不懂qwq。
17. [P7589 黑白棋（2021 CoE-II B）](https://www.luogu.com.cn/problem/P7589) 几乎就是nim模板。
18. [P6487 [COCI2010-2011#4] HRPA](https://www.luogu.com.cn/problem/P6487) 简单的斐波那契博弈。