博弈论题单

题单介绍

[博弈论 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 ![](https://img-blog.csdnimg.cn/20210706155300296.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1JvYmluMjMyMQ==,size_16,color_FFFFFF,t_70#pic_center) 9. [P2252 [SHOI2002]取石子游戏|【模板】威佐夫博弈](https://www.luogu.com.cn/problem/P2252) 结论:当第一个数是差值的1.618倍时,先手必败。 Beatty 定理: ![Beatty定理](https://img-blog.csdnimg.cn/20210706152255785.jpg#pic_center) 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) 简单的斐波那契博弈。

题目列表

  • pb的游戏(1)
  • 肥猫的游戏
  • [NOIP2010 普及组] 三国游戏
  • 取数游戏II
  • 欧几里德的游戏
  • 【模板】nim 游戏
  • [HEOI2014]人人尽说江南好
  • [SBCOI2020] 时光的流逝
  • 黑白棋(2021 CoE-II B)
  • [SHOI2008]小约翰的游戏
  • [COCI2010-2011#4] HRPA
  • [SHOI2002]取石子游戏|【模板】威佐夫博弈
  • [POI2009]KAM-Pebbles
  • Industrial Nim
  • 高手过招
  • [ZJOI2009]染色游戏
  • [HNOI2007]分裂游戏
  • [CQOI2013]棋盘游戏
  • [Cnoi2019]人形演舞
  • [SNOI2020] 取石子
  • [yLOI2020] 牵丝戏
  • [USACO3.3]游戏 A Game
  • [USACO09NOV]A Coin Game S
  • [GZOI2017]取石子游戏
  • [SDOI2011]黑白棋
  • [HAOI2015]数组游戏
  • [SDOI2009]E&D
  • [ZJOI2009]取石子游戏
  • 「EVOI-RD1」摘叶子