题链
tips:
1. 对于简单的 Nim 游戏, a1^...an;ai 就是 sg 函数值.
2. 一堆石子就是一个有向图; 可以按条件转移局面.
3.sg 函数的定义有递归的味道, 所以用记忆化搜索来写.
5.sg(x)=k, 则局面 x 可以转移到 0~k-1.
4.puts 输出字符串会自动换行
- //sg 函数的定义本身就有递归的感觉, 一直到递归基
- #include<bits/stdc++.h>
- #include<iostream>
- #include<set>
- using namespace std;
- int n,m;
- const int N=110,M=10010;
- int s[N],F[M];
- int sg(int x){
- if(F[x]!=-1) return F[x];
- // 用哈希表存所有可以到的局面
- unordered_set<int> S;
- for(int i=0; i<n; i++){
- if(x>= s[i]) S.insert(sg(x-s[i]));
- }
- for(int i=0;;i++){
- if(!S.count(i)) return F[x]=i;
- }
- }
- int main(){
- cin>>n;
- for(int i=0; i<n; i++){
- cin>>s[i];
- }
- cin>>m;
- memset(F , -1, sizeof(F));
- int res=0;
- for(int i=0; i<m; i++){
- int x;
- cin>>x;
- res^=sg(x);
- }
- if(res) cout<<"Yes"<<endl;
- else cout<<"No"<<endl;
- return 0;
- }
- View Code
NIM 游戏
给定 N 堆物品, 第 i 堆物品有 Ai 个. 两名玩家轮流行动, 每次可以任选一堆, 取走任意多个物品, 可把一堆取光, 但不能不取. 取走最后一件物品者获胜. 两人都采取最优策略, 问先手是否必胜.
我们把这种游戏称为 NIM 博弈. 把游戏过程中面临的状态称为局面. 整局游戏第一个行动的称为先手, 第二个行动的称为后手. 若在某一局面下无论采取何种行动, 都会输掉游戏, 则称该局面必败.
所谓采取最优策略是指, 若在某一局面下存在某种行动, 使得行动后对面面临必败局面, 则优先采取该行动. 同时, 这样的局面被称为必胜. 我们讨论的博弈问题一般都只考虑理想情况, 即两人均无失误, 都采取最优策略行动时游戏的结果.
NIM 博弈不存在平局, 只有先手必胜和先手必败两种情况.
定理: NIM 博弈先手必胜, 当且仅当 A1 ^ A2 ^ ... ^ An != 0
公平组合游戏 ICG
若一个游戏满足:
1. 由两名玩家交替行动;
2. 在游戏进程的任意时刻, 可以执行的合法行动与轮到哪名玩家无关;
3. 不能行动的玩家判负;
则称该游戏为一个公平组合游戏.
NIM 博弈属于公平组合游戏, 但城建的棋类游戏, 比如围棋, 就不是公平组合游戏. 因为围棋交战双方分别只能落黑子和白子, 胜负判定也比较复杂, 不满足条件 2 和条件 3.
有向图游戏
给定一个有向无环图, 图中有一个唯一的起点, 在起点上放有一枚棋子. 两名玩家交替地把这枚棋子沿有向边进行移动, 每次可以移动一步, 无法移动者判负. 该游戏被称为有向图游戏.
任何一个公平组合游戏都可以转化为有向图游戏. 具体方法是, 把每个局面看成图中的一个节点, 并且从每个局面向沿着合法行动能够到达的下一个局面连有向边.
Mex 运算
设 S 表示一个非负整数集合. 定义 mex(S) 为求出不属于集合 S 的最小非负整数的运算, 即:
mex(S) = min{x}, x 属于自然数, 且 x 不属于 S
SG 函数
在有向图游戏中, 对于每个节点 x, 设从 x 出发共有 k 条有向边, 分别到达节点 y1, y2, ..., yk, 定义 SG(x) 为 x 的后继节点 y1, y2, ..., yk 的 SG 函数值构成的集合再执行 mex(S) 运算的结果, 即:
SG(x) = mex({SG(y1), SG(y2), ..., SG(yk)})
特别地, 整个有向图游戏 G 的 SG 函数值被定义为有向图游戏起点 s 的 SG 函数值, 即 SG(G) = SG(s).
有向图游戏的和
设 G1, G2, ..., Gm 是 m 个有向图游戏. 定义有向图游戏 G, 它的行动规则是任选某个有向图游戏 Gi, 并在 Gi 上行动一步. G 被称为有向图游戏 G1, G2, ..., Gm 的和.
有向图游戏的和的 SG 函数值等于它包含的各个子游戏 SG 函数值的异或和, 即:
SG(G) = SG(G1) ^ SG(G2) ^ ... ^ SG(Gm)
定理
有向图游戏的某个局面必胜, 当且仅当该局面对应节点的 SG 函数值大于 0.
有向图游戏的某个局面必败, 当且仅当该局面对应节点的 SG 函数值等于 0.
概念讲解
sum:
1. 在 c++ 官网上查语法.
[ACW]893 集合 - Nim 游戏
来源: http://www.bubuko.com/infodetail-3395817.html