Nim 游戏
(n) 堆石子,每堆有(a_i)个,两个玩家每次取走任意一堆的任意个,不能不取,询问先手有无必胜策略
结论是
如果石子异或和为(0),则先手必败,否则先手必胜
证明:
首先终态异或和为(0),如果任意一个异或和不为(0)的状态均可以一步转化为异或和为(0),那么结论得证
-
如果异或和最高位(第(i)位)为(1),那么一定有一堆石子第(i)位为(1)
-
设(A_1)就为那堆石子,其他堆石子异或和设为(x),总异或和设为(k),则 (A_1 xor x=k),把(A_1)变成(A_1 xor k),那么后手面对的则是((A_1 xor k) xor x=0)
-
如果先手异或和不为(0),可以一步让后手的情况为异或和为(0);如果先手异或和为(0),那么后手异或和就不为(0)
例题
P4301 [CQOI2013] 新Nim游戏
也就是要前两轮操作之后异或和不为(0)
首先先手肯定必胜,因为可以只剩一堆,后手第二回合不动。然后我们需要找到最小花费。
多个数异或和为(0),也就是其中一个可以被另一些线性表示出来
考虑线性基,线性基中没有有异或和为 (0) 的子集。我们让线性基里的元素和最大即可。贪心的从最大的到最小的依次插入,如果插入成功,则不能被线性表示,不会使异或和为(0),否则必须删去
阶梯尼姆博弈(Staircase Nim)
(n)阶台阶,(0)为地面,每阶上有(a_i)个石子,每次只能把(1sim n)中一堆石子上的一些往下移一格,求有无先手必胜策略
把奇数阶梯往偶数阶梯移动看做普通Nim游戏里的移除棋子,如果有一方将偶数阶梯里的棋子移到奇数阶梯,那么下一方可以把同样数量的再往下移一格,奇数阶梯石子状态不变,先后手顺序也不变
结论就是:
如果奇数阶梯的异或和为(0),则先手必败,否则先手必胜
例题
P3480 [POI2009]KAM-Pebbles
差分(c_i=a_i-a_{i-1}),将丢掉一些看做与左边的差变小,即(c_i)减小,与后面的差增大,即(c_{i+1})变大
问题转化成从(c_i)移动石子到(c_{i+1}),reverse做阶梯尼姆博弈即可
尼姆K博弈(Nim k Game)
在普通Nim游戏的基础上,我们每次可以从(k)堆中任意取
将普通Nim的二进制下异或和改为 每一堆石子的(2)进制数在(k+1)进制下异或和(不进位求和)
异或和为(0)先手必败,否则先手必胜
也就是对当前异或和造成贡献的可能最多有(k)堆,这(k)堆的最高位都要变成(0),并使剩下的变成(0)
Nim 游戏,取完者输
特判全是(1):奇数先手必败,偶数先手必胜
否则判断异或和:异或和为(0)先手必败,否则先手必胜
SG 函数
设(S)是(x)的后继状态(执行完一步操作之后的状态)的集合
定义(mex{T}),其中(T)为正整数集合。(mex{T}=)最小的,没有在(T)中出现的自然数。例如(mex{0,1,2,4}=3,mex{1,2,4}=0,mex{}=0)
SG定理
定理:
游戏和的
SG函数
等于各个游戏SG函数的Nim和
,其中Nim和
就是异或和
不会证,告辞
简单应用
- 普通Nim游戏
(x)的后继状态为({0,1,2cdots,x-1}),也就是(SG(x)=mex{SG(0),SG(1),SG(2),cdots,SG(x-1)}=x)
而整个Nim游戏是每一堆的游戏和,游戏和的(SG=) (a_i)的异或和
例题
HDU1848 Fibonacci again and again
(x)的后继状态是({x-fib_i}(1le fib_ile x))
模拟(mex)的过程即可
void init(int n){
for(int i=1;i<=n;++i){
memset(app,0,sizeof(app));
for(int j=1;fib[j]<=i;++j)
app[sg[i-fib[j]]]=1;
for(int j=0;;++j)
if(!app[j]){sg[i]=j;break;}
}
}
巴什博弈(Bash’s Game)
只有一堆(n)个物品,两个人轮流从这堆物品中取物,规定每次至少取一个,最多取(m)个,最后取光者得胜
后手总能使本回合减少的数量为(m+1)
所以如果(nmod (m+1)=0)则先手必败,否则先手必胜
威佐夫博弈(Wythoff’s Game)
有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法:
- 可以在任意的一堆中取走任意多的石子
- 可以在两堆中同时取走相同数量的石子
最后把石子全部取完者为胜者。
称后手必胜态被称为奇异局势
爆搜出前几个奇异局势分别是((0,0),(1,2),(3,5),(4,7),(6,10),(8,13))
结论(我依然证不来),((a,b))是奇异局势当且仅当:
判断的时候(k=b-a),判断(a)是否等于(leftlfloorfrac{k imes (1+sqrt{5})}{2} ight floor)
其他各种game
Chomp Game
有一个(n imes m)的棋盘,每次可以取走一个方格并拿掉它右边和上面的所有方格,拿到左下角的格子((1,1))者输,问先手必胜还是必败。
结论:除了(n=m=1)的情况,先手都必胜
证明:如果先手取((n,m))之后,后手有必胜策略,先手可以第一步就按照后手的必胜策略选
Ferguson Game
两堆石子各(n,m)个,两人轮流操作,每次清空一堆石子并将另一堆石子分成两堆(每堆至少一个),无法操作者输,问先手输还是赢。
结论:若(n,m)均为奇数,先手必败,否则先手必胜
证明:
对于((1,1))显然是先手必败,((1,2),(2,2),(2,1))都是先手必胜
考虑归纳证明,假设(max(x,y)<k)时成立,现证明(max(x,y)=k)时也成立
- 如果有一个是偶数,将奇数的那个清空,将偶数的拆成两个奇数,后手必败,先手必胜
- 两个都是奇数,一定会被拆出来一奇一偶,后手必胜,先手必败
杂题
P1288 取数游戏II
性质:每次走一条路必须走完,两个方向第一次走到(0)的边或走完一遍了就结束
证明:反证法:要是不走完,后手就可以再走回去
for(int i=1;i<=n;i++){
if(a[i])len1++;
else break;
}
for(int i=n;i>=1;i--){
if(a[i])len2++;
else break;
}
if((len1&1)||(len2&1)) puts("YES");
else puts("NO");
P1290 欧几里德的游戏
设当前的两个数为((a,b),ale b)
- (a=b) 先手必胜
- (b<2a),则((a,b))只能转换成((b,b-a)),此时的胜者为((b,b-a))的反方
- (bge 2a),经过若干次变化后必定变成((b,b\%a))
- ((b,b\%a))必败,那么直接一次变为((b,b\%a)),把必败情况留给后手
- ((b,b\%a))必胜,那么一次变为((b,b\%a+a)),后手下一步只能一步转化为((b,b\%a)),必胜情况回到自己
bool dfs(int a,int b){
if(a==b) return 1;
else if(a<b) swap(a,b);
if(a/b>1) return 1;
else return 1^dfs(b,a%b);
}
POJ 2484 A Funny Game
(nle 2)时先手必胜,否则:
- 如果(n)为偶数,后手可以中心对称地模仿先手的操作
- 如果(n)为奇数,第一步将环断成两个相同的链,继续模仿
POJ 1740 A New Stone Game
如果所有的堆都有一堆个数相等的与之配对,那么先手必败,因为后手可以模仿先手操作。否则先手必胜,因为大小相邻的两个数之差 之和小于等于最大的一堆(画一个条形图方便理解),把最大的那堆分给没有凑成对的,多余的扔掉,一定可以构造出一一配对的情况
POJ 2505 A multiplication game
打表找规律
([1,9] [10,18] [19,162] [163,324] [325,2916])的胜负关系依次是:先/后/先/后/先
也就是一直除以(18)之后与(9)比大小
#define db double
db n;
int main(){
while(scanf("%lf",&n)!=EOF){
while(n>18.0)n/=18.0;
puts((n<=9.0)?"Stan wins.":"Ollie wins.");
}
return 0;
}
POJ 2068 Nim
DP(记搜)即可