博弈论上篇（巴什博奕，尼姆博弈，威佐夫博弈，裴波那契博弈）

大家好，欢迎来到IT知识分享网。

今天上午也是小小的复习了一下这个博弈论，这个博弈论说难也难，说不难也不难，模版很简单，记住就可以拿下，但是一般比赛的时候从来不会考模版，基本上还是需要自己思考，但是学了肯定比不学强，骄兵必败！！！加油

ICG博弈

今天所讨论的问题皆是ICG博弈

所讨论的博弈问题满足以下条件：

    玩家只有两个人，轮流做出决策。

    游戏的状态集有限，保证游戏在有限步后结束，这样必然会产生不能操作者，其输。

    对任何一种局面，胜负只决定于局面本身，而与轮到哪位选手无关。

巴什博奕

巴什博奕的问题类型一般为：给你n个石子，让你从中取，你每次最多取m个，最少取一个，谁能取完最后一个谁就获胜

因此，我们将这种问题分三种情况，来讨论

情况1：如果n=m+1，那么无论前者取多少个，后者都能获胜

情况2：如果n=（m+1）*k+c（k是任意自然数，c是一个常数，1<c<=m）那么我们只要第一个人先取c，将（m+1）的倍数留给后者，就可以保证前者是一定能够获胜的

情况3：如果n=（m+1）*k（k是任意自然数），那么可以确保后者是一定能够获胜的

因此巴什博奕的奇异局势为，看谁能够将n=(m+1)*k留给对方，谁能将这个留给对方，谁就能获胜

总之，要保持给对手留下（m+1）的倍数，就能最后获胜。 

例题：

Buttons

就是巴什博奕的逆运算，我们知道起始数量 ,我们想让第二个获胜，如果不存在这种情况就输出0，那么我们只需要让一开始n就是（m+1）*k即可，很轻松的写出代码

#include<bits/stdc++.h> using namespace std; #define int long long int k; signed main() { cin>>k; int flag=0; int i; for( i=2;i<k;i++) { if(k%(i+1)==0) { cout<<i<<"\n"; flag=1; break; } } if(i==k)//防止不存在i，使得第二个获胜 { cout<<0<<"\n"; } return 0; }

P4018 Roy&October之取石子

这题也可以叫做质数次方取石子游戏，因为每次取的都是质数的某个次方 ，那么我们就要开始思考了，这种博弈该怎么去取呢？我们先去列举一下每个质数的k次方，并且排序会发现

1=（任意质数的）0次方

2=2^1；

3=3^1；

4=2^2；

5=5^1；

但唯独6不可能用质数的次方取表示，因此我们想到了什么，用两个质数的平方去凑6，这个我们可以联想到巴什博奕，因为我们的巴什博奕也是两个人去凑一个(m+1)，因此我们只需要判断这个n是不是6的倍数，如果是6的倍数，则先手输，如果不是6的倍数，则后手输

#include<bits/stdc++.h> using namespace std; #define int long long int t; int n; signed main() { cin>>t; while(t--) { cin>>n; if(n%6==0) { cout<<"Roy wins!\n"; } else { cout<<"October wins!\n"; } } return 0; }

尼姆博弈

尼姆博弈说的是总共有n堆石子，每堆石子都有其自己个数，然后每次每人只能在一堆石子中选任意个石子拿出来

情况1:只有一堆石子， 先手全拿，先手必胜。

情况2：有两堆石子，两种情况，一种可能相同，一种情况一堆比另一堆少（多）

        (m,m) 按照“有一学一，照猫画猫”法，先手必输。

        (m,M)先手先从多的一堆中拿出(M-m)个，此时后手面对(m,m)的局面先手必胜。

因此也被成为(m,m)的奇异局势

情况3:(m,m,M)先手必胜局，先手可以先拿M,之后变成了(m,m,0)的局面

结合上面的情况再加上自己打表写数据可以发现，只要这n堆石子的异或结果为0，那么就是必输的，否则是能够获胜的

例题：

P2197 【模板】Nim 游戏

 纯模版，不多解释

#include<bits/stdc++.h> using namespace std; #define int long long int t; int n; int x; signed main() { cin>>t; while(t--) { cin>>n; int flag=0; while(n--) { cin>>x; flag^=x; } if(flag==0) cout<<"No\n"; else cout<<"Yes\n"; } return 0; }

 P4279 [SHOI2008] 小约翰的游戏

 我们这题有一个别名也叫做反尼姆博弈，因为这题是谁取到最后一个谁就输了

因此我们还是先分情况讨论：

情况1：假如说有n堆，都是1的数量，那么我们只需要判断奇偶性就可以，奇数哥哥赢，偶数john赢

情况2：假如说有n堆，只有一堆的数量大于1，别的都是1，那么我们的john就可以通过确保是否留1个从而让自己必胜

情况3：有n堆，所有堆的数量都不确定，那么我们就要想办法看能否变成情况2，谁能先变成情况2，谁就能获胜

情况2的异或是不为0的，因此我们也就是说，谁先能异或不为0，谁就能赢

所以我们只需要看一开始的初始情况即可

#include<bits/stdc++.h> using namespace std; #define int long long int t; int n; int x; signed main() { cin>>t; while(t--) { cin>>n; int bit=0; int flag=0;//判断是否出现过大于1的 while(n--) { cin>>x; if(x>1) { flag=1; } bit^=x; } if(flag==0) { if(n%2==0) { cout<<"John\n"; } else { cout<<"Brother\n"; } } else { if(bit!=0) { cout<<"John\n"; } else { cout<<"Brother\n"; } } } return 0; }

 裴波那契博弈

裴波那契博弈的一般形式就是说，给你n个石子，第一次可以拿任意个石子，但是往后，每个人最多拿前一个人拿的石子的二倍，问你第一个人一定要赢，第一次拿石子的最少数量

结论：如果石子数是裴波那契数，那么一定要第一次都拿完才能获胜，但是如果不是裴波那契数，则将其拆分成小的裴波那契数，然后最小的裴波那契数就是最终至少要拿的石子数

例题：P6487 [COCI2010-2011#4] HRPA 

思路：就是裴波那契博弈的模版，很简单，直接按照结论写代码即可

#include <bits/stdc++.h> using namespace std; #define int long long int a[80]; int n; signed main() { a[1] = 1; a[2] = 2; for (int i = 3; i <= 75; i++) { a[i] = a[i - 1] + a[i - 2]; } cin >> n; while(1) { int flag=lower_bound(a+1,a+76,n)-a; if(a[flag]==n) { cout<<n; break; } else { n-=a[flag-1]; } } return 0; }

 威佐夫博弈

有两堆各若干个物品，两个人轮流从任一堆取至少一个或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。

这题的奇异局势和上面那个裴波那契博弈一样，不用究其根本，如果非要去深究，比赛的时候真的很难做出来，只需要思维能够发散即可

我们先来找找必输局面的棋数

• 第一种（0，0）
• 第二种（1，2）
• 第三种（3，5）
• 第四种  (4 ，7）
• 第五种（6，10）
• 第六种  (8，13）              
• 第七种  (9 ，15）
• 第八种  (11 ，18）

这样就是奇异局势，但是我们还需要去找出一个通项式，这种东西，是个普通人都不好推出来

当a<b的时候，如果a==(b-a)*(sqrt(5.0) + 1) / 2   ,那么就是先手必输的局面，也称为奇异局势

例题：P2252 [SHOI2002] 取石子游戏|【模板】威佐夫博弈

#include <bits/stdc++.h> using namespace std; using ll = long long; ll a, b; int main() { cin >> a >> b; if(a==) { cout<<"1\n"; return 0; } if (a > b) swap(a, b); int z = b - a; int w = (int)(((sqrt(5.0) + 1) / 2) * z); if (w == a) cout << "0" << endl; else cout << "1" << endl; return 0; }

 这题有个特殊数值，也就是那个特判，如果按照这种写法是写不出来的，除非你把精度卡在第18位才能做出来