宇宙企画网站,无锡品牌网站建设网站,东莞网站设,免费的国外云服务器目录 1 基础知识2 模板3 工程化 1 基础知识
#xff08;一#xff09; Nim游戏#xff1a; n n n堆物品#xff0c;每堆有 a i a_i ai个#xff0c;两个玩家轮流取走任意一堆的任意个物品#xff0c;但不能不取。取走最后一个物品的人获胜。
结论#xff1a;如果这n… 目录 1 基础知识2 模板3 工程化 1 基础知识
一 Nim游戏 n n n堆物品每堆有 a i a_i ai个两个玩家轮流取走任意一堆的任意个物品但不能不取。取走最后一个物品的人获胜。
结论如果这n个数异或之和为0则先手必败否则先手必胜。 代码表示为
#include iostreamusing namespace std;int main() {int n;cin n;int res 0;while (n--) {int x;cin x;res res ^ x;}if (res) puts(Yes);else puts(No);return 0;
}二 集合Nim游戏在Nim游戏的基础上对每次取走的石子做了限制每次取走的石子数必须在集合 S S S内。判断是否先手必胜。
抽象建模为 有向图游戏和SG函数在一个有向无环图中只有一个起点上面有一个棋子两个玩家轮流沿有向边推动棋子不能走的玩家判负。
定义mex函数的值为不属于集合S中的最小非负整数即 m e x ( S ) m i n { x } ( x ∉ S , x ∈ N ) mex(S)min\{x\} \ (x\notin S, x\in N) mex(S)min{x} (x∈/S,x∈N) 例如mex({0,2,3}) 1, mex({1,2}) 0。
对于状态 x x x和它的所有 k k k个后继状态 y 1 , y 2 , ⋯ , y k y_1,y_2,\cdots,y_k y1,y2,⋯,yk定义SG函数 S G ( x ) m e x { S G ( y 1 ) , S G ( y 2 ) , ⋯ , S G ( y k ) } SG(x)mex\{SG(y_1), SG(y_2), \cdots, SG(y_k)\} SG(x)mex{SG(y1),SG(y2),⋯,SG(yk)}
而对于由n个有向图组成的组合游戏设它们的起点分别为 s 1 , s 2 , ⋯ , s n s_1,s_2,\cdots,s_n s1,s2,⋯,sn则有定理当且仅当这 n n n个数 S G ( s 1 ) , S G ( s 2 ) , ⋯ , S G ( s n ) SG(s_1),SG(s_2),\cdots,SG(s_n) SG(s1),SG(s2),⋯,SG(sn)的异或和不为0时这个游戏是先手必胜的否则是先手必败的。
C代码如下
#include iostream
#include unordered_set
#include cstringusing namespace std;const int N 110, M 1e4 10;
int n, m;
int s[N]; //每次可以取的石子数目
int f[M]; //这堆有x个石子求sg[x]的值int sg(int x) {if (f[x] ! -1) return f[x];unordered_setint S;//x能走到的结点的sg函数值for (int i 0; i n; i) {if (x - s[i] 0) S.insert(sg(x-s[i]));}for (int i 0; ; i) {if (S.count(i) 0) {f[x] i;break;}}return f[x];
}int main() {cin n;for (int i 0; i n; i) cin s[i];int res 0;memset(f, -1, sizeof f);cin m;while (m--) {int x;cin x;res ^ sg(x);}if (res) puts(Yes);else puts(No);return 0;
}2 模板
暂无。。。
3 工程化
题目1拆分Nim游戏取走一堆放回两堆规模更小的石子。
解题思路重点在于如何确认某一堆的sg值这样考虑遍历两堆规模更小的石子就是它的下一步状态求得它们的sg值进行mex操作即可得到这堆石子的sg值。
C代码如下
#include iostream
#include unordered_set
#include cstringusing namespace std;const int N 110;int n;
int f[N]; //sg值int sg(int x) {if (f[x] ! -1) return f[x];//x可以走到的状态的sg值unordered_setint S;for (int i 0; i x; i) {for (int j 0; j i; j) {S.insert(sg(i) ^ sg(j));}}//mex操作for (int i 0; ; i) {if (!S.count(i)) {return f[x] i;}}
}int main() {memset(f, -1, sizeof f);cin n;int res 0;for (int i 0; i n; i) {int x;cin x;res ^ sg(x);}if (res) puts(Yes);else puts(No);return 0;
}
