博弈论入门一

关于博弈论(简单的),SG下次学了写吧
强推B站这个教学视频,贴个链接:博弈论
还有kuangbin巨巨在博客园转的一个博弈知识汇总
再贴个鄙校在vj挂的博弈论入门练习
然后,放个图:

哈哈哈哈哈哈哈哈卢姥爷同款壁纸

首先先把VJ的ABCDF一起放出来:
不放题目了,题目链接自取,而且这里题目基本也都重合了
A:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*Sample Input
2
8 10
11 10
Sample Output
Grass
Rabbit*/
//八神博弈
#include <iostream>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
int t,n,m;
cin>>t;
while(t--)
{
cin>>n>>m;
if(n%(m+1)==0)cout<<"Rabbit"<<endl;
else cout<<"Grass"<<endl;
}
return 0;
}

B:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/*Sample Input
4 2
3 2
3 5
Sample Output
1
none
3 4 5*/
//八神博弈
#include <iostream>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
int n,m;
while(cin>>n>>m)
{
if(n%(m+1)==0)cout<<"none"<<endl;
else {
if(n>m)
{
cout<<n%(m+1)<<endl;
}
else {
for(int i=n;i<=m;i++)
{
if(i!=m)
cout<<i<<" ";
else cout<<i<<endl;
}
}
}
}
return 0;
}

C:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
int n;
cin>>n;
while(n--)
{
int a,b;
cin>>a>>b;
int t=a%(b+1);
if(t>=1)
{
cout<<"first"<<endl;
}
else
{
cout<<"second"<<endl;
}
}
return 0;
}

D:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//魏作福博弈
#include <iostream>
#include <cmath>
#define long long int int
using namespace std;
int main()
{
ios::sync_with_stdio(false);
int n,m;
while(cin>>n>>m)
{
if(n<0||m<0)break;
int temp;
if(n>m){
temp=n;
n=m;
m=temp;
}
int c=floor((m-n)*((sqrt(5.0)+1)/2));
if(n==c)cout<<"0"<<endl;
else cout<<"1"<<endl;
}
}

F:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*Sample Input
3
5 7 9
0
Sample Output
1*/
//尼姆博弈
#include <iostream>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
int n;
while(cin>>n&&n)
{
int a[101];
int ans=0;
for(int i=0;i<n;i++)
{
cin>>a[i];
ans^=a[i];
}
if(ans==0)cout<<"0"<<endl;
else
{
int sum=0;
for(int i=0;i<n;i++)
{
int k=ans^a[i];
if(k<a[i])sum++;
}
cout<<sum<<endl;
}
}
return 0;
}

关于E就是wythoff+高精度 具体代码还未写出

接下来具体讲讲博弈论中除SG函数的博弈类型
1-bash博弈
hdu1846
各位勇敢者要玩的第一个游戏是什么呢?很简单,它是这样定义的:
1、 本游戏是一个二人游戏;
2、 有一堆石子一共有n个;
3、 两人轮流进行;
4、 每走一步可以取走1…m个石子;
5、 最先取光石子的一方为胜;

如果游戏的双方使用的都是最优策略,请输出哪个人能赢。

Input
输入数据首先包含一个正整数C(C<=100),表示有C组测试数据。
每组测试数据占一行,包含两个整数n和m(1<=n,m<=1000),n和m的含义见题目描述。

Output
如果先走的人能赢,请输出“first”,否则请输出“second”,每个实例的输出占一行。

Sample Input

2
23 2
4 3

Sample Output

first
second

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
using namespace std;
int main(){
ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
if(n%(m+1)==0)cout<<"second"<<endl;
else cout<<"first"<<endl;
}
return 0;
}

hdu2147
虽然她很无聊,但他脑子里出现了一个想法,她只是玩棋盘游戏。主板的大小是n * m。
首先,硬币放在右上角(1,m)。 每次一个人可以将硬币移动到左侧,下方或左下方的空白区域。
无法移动的人将失去游戏。 kiki与ZZ一起玩。游戏总是以kiki开头。 如果两者都能完美发挥,谁将赢得比赛?

输入
输入包含多个测试用例。 每行包含两个整数n,m(0 <n,m <= 2000)。 当n = 0且m = 0时,输入终止。
Sample Input
5 3
5 4
6 6
0 0
Sample Output
What a pity!
Wonderful!
Wonderful!

本题PN分析:
1-所有终结点都是必败点P(无牌可取)
2-一步走到P点的就是N点
3-一步操作只能走到N点的就是P点

打表出一部分PN图,便知道大概的规律

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
using namespace std;
int main(){
ios::sync_with_stdio(false);
int n,m;
while(cin>>n>>m&&(n&&m)){
if(n%2!=0&&m%2!=0)cout<<"What a pity!"<<endl;
else cout<<"Wonderful!"<<endl;
}
return 0;
}

hdu2149
通过打听,Lele知道这场拍卖的规则是这样的:刚开始底价为0,两个人轮流开始加价,不过每次加价的幅度要在1~N之间,当价格大于或等于田地的成本价 M 时,主办方就把这块田地卖给这次叫价的人。

Lele和Yueyue虽然考试不行,但是对拍卖却十分精通,而且他们两个人都十分想得到这块田地。所以他们每次都是选对自己最有利的方式进行加价。

由于Lele字典序比Yueyue靠前,所以每次都是由Lele先开始加价,请问,第一次加价的时候,
Lele要出多少才能保证自己买得到这块地呢?

Input
本题目包含多组测试,请处理到文件结束(EOF)。每组测试占一行。
每组测试包含两个整数M和N(含义见题目描述,0<N,M<1100)

Output
对于每组数据,在一行里按递增的顺序输出Lele第一次可以加的价。两个数据之间用空格隔开。
如果Lele在第一次无论如何出价都无法买到这块土地,就输出”none”。

Sample Input
4 2
3 2
3 5

Sample Output
1
none
3 4 5

Author
Linle

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
int main(){
ios::sync_with_stdio(false);
int m,n;
while(cin>>m>>n){
if(m%(n+1)==0)cout<<"none"<<endl;
else{
if(m>=n){
cout<<m%(n+1)<<endl;
}
else {
for(int i=m;i<=n;i++){
if(i!=n)cout<<i<<" ";
else cout<<i<<endl;
}
}
}
}
return 0;
}

hdu2188
选拔规则如下:
1、最初的捐款箱是空的;
2、两人轮流捐款,每次捐款额必须为正整数,并且每人每次捐款最多不超过m元(1<=m<=10)。
3、最先使得总捐款额达到或者超过n元(0<n<10000)的一方为胜者,则其可以亲赴灾区服务。
我们知道,两人都很想入选志愿者名单,并且都是非常聪明的人,假设林队先捐,请你判断谁能入选最后的名单?

Input
输入数据首先包含一个正整数C,表示包含C组测试用例,然后是C行数据,每行包含两个正整数n,m,n和m的含义参见上面提到的规则。

Output
对于每组测试数据,如果林队能入选,请输出字符串”Grass”, 如果徐队能入选,请输出字符串”Rabbit”,每个实例的输出占一行。

Sample Input
2
8 10
11 10

Sample Output
Grass
Rabbit

同vj上的题,只不过最近新鲜做了一遍
先达到n-m必输
也就是
林让徐达到n-m然后轮到他拿就行,然后林一次拿m个,如果徐没达到n-m个,那就补到n-m-1个,再让徐拿就必胜了
也就是说 谁面临着k
(m+1)的局面 谁必输(死活一次拿不完)*

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
using namespace std;
int main(){
ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
if(n%(m+1)==0)cout<<"Rabbit"<<endl;
else cout<<"Grass"<<endl;
}
return 0;
}

2-fib博弈–斐波拉契博弈
说实话我也没听说过斐波拉契博弈,但是学了之后觉得还是听隐晦的
这里只提一点:任何一个数都可以由n个斐波拉契数相加和表示
hdu2516
Problem Description
1堆石子有n个,两人轮流取.先取者第1次可以取任意多个,但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍。取完者胜.先取者负输出”Second win”.先取者胜输出”First win”.

Input
输入有多组.每组第1行是2<=n<2^31. n=0退出.

Output
先取者负输出”Second win”. 先取者胜输出”First win”.
参看Sample Output.

Sample Input
2
13
10000
0

Sample Output
Second win
Second win
First win


1 2 3 5 8 13 21 34 55
关于斐波拉契博弈
只能拿斐波拉契数,任何一个数都可以写成几个斐波拉契数的和 谁先拿完数谁胜利
当起始数n为斐波拉契数时,则先手必胜:
1-如果可以不限制拿的数量,一次拿完,先手胜利
2-如果限制,则先手拿一个斐波拉契数,且这个数可以使得剩下的数不被一次拿完,这显然是可行的。那么最后还是先手胜利

当起始数n不为斐波拉契数时,则后手必胜:
因为只能拿斐波拉契数,所以先手不可能一次拿完,剩下的数:
1-斐波拉契数,这时变为情况一,后手变成先手,必胜
2-非斐波拉契数,那么后手必然可以拿一个斐波拉契数,剩的剩下的数仍是非斐波拉契数,那么先手面对的情况回到了起点
如此循环,后手最终还是会赢


ac code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
using namespace std;
int fib[55];
void init(){
fib[0]=1;fib[1]=2;
for(int i=2;i<55;i++){
fib[i]=fib[i-2]+fib[i-1];
}
}
int main(){
ios::sync_with_stdio(false);
int n;
while(cin>>n,n){
bool wyh=true;
init();
for(int i=0;i<55;i++){
if(fib[i]==n){
wyh=false;
break;
}
}
if(wyh)cout<<"First win"<<endl;
else cout<<"Second win"<<endl;
}
return 0;
}

3-wythoff game
poj1067
Description
有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目,如果轮到你先取,假设双方都采取最好的策略,问最后你是胜者还是败者。
Input
输入包含若干行,表示若干种石子的初始情况,其中每一行包含两个非负整数a和b,表示两堆石子的数目,a和b都不大于1,000,000,000。
Output
输出对应也有若干行,每行包含一个数字1或0,如果最后你是胜者,则为1,反之,则为0。
Sample Input
2 1
8 4
4 7
Sample Output
0
1
0
关于 wythoff game
关于威佐夫博弈:
题目:两堆物品,两个人轮流拿,每次至少拿一个,两种拿法:
1-在某一堆中取走若干
2-在两堆中取走相同多的物品
谁先取完获胜
奇异局势(必输):(0,0)、(1,2)、(3,5)、(4,7)、(6,10)……
奇异局势以下性质:
1-每个自然数都在一个奇异局势中,且仅有一个
2-任何操作都可以把奇异局势非奇异化:
i—进行1操作,改变其中一个数,但是改变后的数已经在一个奇异局势中,所以奇异局势非奇异化
ii—进行2操作,同时拿去同数量物品,那么原奇异局势的差值不变,但是很明显差值是由0、1、2、3、4……递增的,所以差值不变
但数变了就变成了非奇异局势

所以:面对非奇异局势,先手必胜,反之先手必败
(b-a)*(根号5+1)/2==a,那么此为奇异局势

上述不大理解的话:
可以参照bin巨转的博客中提到的公式:
ak =[k(1+√5)/2],bk= ak + k (k=0,1,2,…,n 方括号表示取整函数)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <cmath>
using namespace std;
const int maxn=1e9+9;
int main(){
ios::sync_with_stdio(false);
int a,b;
while(cin>>a>>b){
if(a>b)swap(a,b);
int wyh=(((1+sqrt(5))/2)*(b-a));
// cout<<"wyh:"<<wyh<<endl;
if(a==wyh)cout<<"0"<<endl;
else cout<<"1"<<endl;
}
return 0;
}

4-nim game尼姆博弈
尼姆博弈相关于二进制位运算(异或)
hdu1850
下面是一个二人小游戏:桌子上有M堆扑克牌;每堆牌的数量分别为Ni(i=1…M);两人轮流进行;每走一步可以任意选择一堆并取走其中的任意张牌;桌子上的扑克全部取光,则游戏结束;最后一次取牌的人为胜者。
现在我们不想研究到底先手为胜还是为负,我只想问大家:
——“先手的人如果想赢,第一步有几种选择呢?”

Input
输入数据包含多个测试用例,每个测试用例占2行,首先一行包含一个整数M(1<M<=100),表示扑克牌的堆数,紧接着一行包含M个整数Ni(1<=Ni<=1000000,i=1…M),分别表示M堆扑克的数量。M为0则表示输入数据的结束。

Output
如果先手的人能赢,请输出他第一步可行的方案数,否则请输出0,每个实例的输出占一行。

Sample Input
3
5 7 9
0
每个奇异局势的a1^a2^a3…^an==0
那么:
当a1^a2^…^an!=0时,则将其中某个ai改变后满足a1^a2^…^an=0,也就是使对方面对奇异局势
则ai的二进制表示的最高位是1,这样才会a1^a2^…^an!=0
此时ai^k<ai一定成立,我们将ai变为ai^k,使得新的a1^a2^…^an变为a1^a2^…^ai^k..^an=0;
然后满足条件,cnt++;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <cstring>
using namespace std;
int main(){
ios::sync_with_stdio(false);
int n;
int a[105];
while(cin>>n,n){
int ans=0;
memset(a,0,sizeof(a));
for(int i=0;i<n;i++){
cin>>a[i];
ans^=a[i];
}
if(ans==0)cout<<"0"<<endl;
else {
int cnt=0;
for(int i=0;i<n;i++){
int k=1^a[i];
if(k<a[i])cnt++;
}
cout<<cnt<<endl;
}
}
return 0;
}

此题code中的for循环我也不甚理解,看题解看懂了,知道可以这样做,但是不知道为什么这样做
有待进一步商榷

到此
博弈论一的博客就写这么多,想发发最近生活中的近况
因为之前一直对刷题很没有积极性,决心改观,于是前几天深夜刷题,奈何两天之后凌晨室友发空间撕我,弄得很是尴尬。其实我真的真的感到很抱歉,因为之前一直是四人寝,大一有时候我熬得晚,当时的室友都无所谓,不影响他们休息,来到本部之后,寝室变为六人寝,加了两个人,还是我没有好好考虑到他,尽管我已经很小心很小心,可能对他还是有所影响,所以真的感到十分抱歉
所以我觉得我还是尽量把学习的时间压在合理的时间吧…但是说实话现在感觉真的避开和他的交流,不是说因为这个事我讨厌他,就是从心底的开始避开他,以前其实关系还是很不错的。
我觉得这件事他可以在QQ上私聊我认真的谈一谈,一定要发到空间这样所有熟人都知道,弄得人家看笑话一样。他如果在qq上私聊我很认真的谈一谈我还这样的话,那我就真是没有教养没有人品,可是你毫无防备突然就把那样一段话望qq空间一发,虽说没有什么难听的话,但是语气里那种冷嘲热讽我还是听得出的吧?什么“现在真的认真了。课不去上,晚上四点写作业,早上不去上课”,我知道这件事错在我,但是我能做的也就只是给你道歉,以后不在宿舍熬夜。你受不了我的各种毛病,其实我也不太喜欢你解决问题的方式

唉…我这么说是不不大好…算了 我也很累,做到不给添麻烦就行了…算了。。。烦死了

最近还有两个讲座,周末还得去陪那个高中生去参加初赛

不提了
继续加油

纵有疾风起,人生不言弃
coswindy

-------------本文结束感谢您的阅读-------------