博弈论 Nim游戏

之前从来没有系统学过博弈论的相关定理，遇到的基本都是从题面中找到相关的规律。在刷牛客tracker的时候遇到了这个问题，总结一下。

经典模型

地上有n堆石子，甲乙两人交替取石子。每人每次可以从任意一堆里面取，但不能不取。最后没有石子可取的人就输了。假如甲先手，且已知每堆石子的数量是a i a_iai​，问谁会取得获胜？

• 结论

如果( S = a 1 ⊕ a 2 ⊕ ⋯ ⊕ a n ≠ 0 ) (S = a_1 \oplus a_2 \oplus \dots \oplus a_n≠0)(S=a1​⊕a2​⊕⋯⊕an​=0)，则先手必胜

如果( S = a 1 ⊕ a 2 ⊕ ⋯ ⊕ a n = 0 ) (S = a_1 \oplus a_2 \oplus \dots \oplus a_n=0)(S=a1​⊕a2​⊕⋯⊕an​=0)，则后手必胜

洛谷有一道板子题，可以直接用结论解决：P2197 【模板】Nim 游戏 - 洛谷

结论的变种

大多数情况都不会直接使用结论，下面说两种简单的变种。

小A取石子

小A取石子_牛客题霸_牛客网

这个题的变化之处在于先手在游戏开始之前可以选择先在某一堆取k kk个石子。

通过结论我们可以知道：必败态之后一定有必胜态

• 如果此时的状态本来就是先手胜，可以不进行这个操作
• 如果此时的状态是后手胜，就需要考虑进行操作
  • 如果k=0，无法进行操作，那么会失败
  • 如果k>max_element，即k比最大的那一堆都大，也无法操作，失败
  • 其他通过操作都能找到必胜态

voidsolve(){intk;cin>>n>>k;vector<int>a(n);for(auto&i:a)cin>>i;intx_or=0;for(autoi:a)x_or^=i;if(x_or){cout<<"YES"<<endl;return;}intsum=*max_element(all(a));if(!k||k>sum)cout<<"NO";elsecout<<"YES";}

取火柴游戏

P1247 取火柴游戏 - 洛谷

本题不同的是，不仅要判断是否先手必胜，还要给出如果先手必胜的话第一次要取哪一堆的多少个石子

从结论中我们可以得到必胜态之后必为必败态，即达到X = a 1 ⊕ a 2 ⊕ ⋯ ⊕ a n = 0 X = a_1 \oplus a_2 \oplus \dots \oplus a_n=0X=a1​⊕a2​⊕⋯⊕an​=0

此时的状态是：
a 1 ⊕ a 2 ⊕ ⋯ ⊕ a n = X a_1 \oplus a_2 \oplus \dots \oplus a_n=Xa1​⊕a2​⊕⋯⊕an​=X
我们此时想让它变成必败态，根据异或的交换律：
a 1 ⊕ ( a 2 ⊕ X ) ⊕ ⋯ ⊕ a n = 0 a_1 \oplus (a_2\oplus X) \oplus \dots \oplus a_n=0a1​⊕(a2​⊕X)⊕⋯⊕an​=0
由于是取走一堆石子之后变成的这样，所以需要a 2 > a 2 ⊕ X a_2>a_2 \oplus Xa2​>a2​⊕X

题中要求输出的< b , a > <b,a><b,a>的字典序尽可能小，其中b bb是堆数，a aa是取走的石子数。也就是说要选择尽可能靠左的石子堆进行操作。那么我们从前往后遍历，找到符合条件的直接操作就行了。

// Problem: P1247 取火柴游戏// Contest: Luogu// URL: https://www.luogu.com.cn/problem/P1247// Memory Limit: 125 MB// Time Limit: 1000 msvoidsolve(){cin>>n;vector<int>a(n);intx_or=0;for(auto&i:a)cin>>i,x_or^=i;if(x_or){for(inti=0;i<n;i++){if((a[i]^x_or)<a[i]){cout<<a[i]-(a[i]^x_or)<<' '<<i+1<<endl;a[i]=a[i]^x_or;break;}}for(inti:a)cout<<i<<' ';}elsecout<<"lose";}