博弈论一

简单博弈论

B Euclid’s game

这道题目的表我好像打错了emmmm
怪不得一直在wa,
注意对称状态的记录,以及打表的时候输出前面的状态是否是未定义的!
附上正确的打表姿势:

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
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
int num[maxn][maxn];
int n, m;
void dfs(int x, int y){
if(x>y) swap(x, y);
if(y%x==0){
num[y][x] = num[x][y] = 1;
return;
}
if(x == 0){
num[y][x] = num[x][y] = 1;
}
for(int i=1; i<=int(y/x); i++){
if(num[x][y-i*x]==-1){
cout<<"haha "<<x<<" "<<y-i*x<<endl;
return ;
}
if(num[x][y-i*x]==0){
num[y][x] = num[x][y] = 1;
return;
}
}
num[y][x] = num[x][y] = 0;
return;
}
int main(){
memset(num, -1, sizeof(num));
for(int i=1; i<=100; i++)num[i][1] = num[1][i] = 1;
for(int i=2; i<=100; i++){
for(int j=i; j<=100; j++){
dfs(i ,j);
}
}
for(int i=1; i<=100; i++){
for(int j=i+1; j<=100; j++){
if(num[i][j] == 0){
cout<<i<<" "<<j<<endl;
}
}
}
return 0;
}
//通过观察表的数据,(i, j)当i+1<=j<=2*i-1时是必败态

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m;
int main(){
ios::sync_with_stdio(false);
while(cin>>n>>m&&n+m){
bool flag = true;
while(true){
if(n>m) swap(n, m);
if(m%n==0) break;
if(m/n>=2) break;
m -= n;
flag = !flag;
}
if(flag){
cout<<"Stan wins"<<endl;
}
else{
cout<<"Ollie wins"<<endl;
}
}
}

cutting paper

当一个玩家可以切出1*1的格子的时候,那么这个玩家赢
使用sg函数

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
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <algorithm>
using namespace std;
const int maxn = 205;
int win[maxn][maxn];
int w, h;
int dfs(int w, int h){
if(win[w][h] != -1) return win[w][h];
set<int> s;
s.clear();
for(int i=2; w-i>=2; i++){
s.insert(dfs(i, h)^dfs(w-i, h));
}
for(int i=2; h-i>=2; i++){
s.insert(dfs(w, i)^dfs(w, h-i));
}
int mex = 0;
while(s.count(mex)!=0) mex++;
return win[w][h] = mex;
}
void solve(int w, int h){
if(!dfs(w, h)) cout<<"LOSE"<<endl;
else cout<<"WIN"<<endl;
}
int main(){
memset(win ,-1, sizeof(win));
ios::sync_with_stdio(false);
while(cin>>w>>h){
solve(w, h);
}
return 0;
}

C

n·n的棋盘上面的博弈,可以横着或者是竖着的移动到之前没有访问过的格子;
看了题解,要有超强的找规律的感觉
看能否用1·2的格子覆盖就行了
将n分奇偶讨论就行了
题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
int n;
while(scanf("%d",&n)==1 &&n)
{
if(n%2==0)printf("8600\n");
else printf("ailyanlu\n");
}
return 0;
}

m堆石子的博弈

每一堆石子可以取至少一个石子,或者全部全部取走
注意卡空间

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
int n;
const int maxn = 200000+10;
int num[maxn];
int tot[maxn];
bool bin[maxn][64];
int number[maxn];
int main()
{
ios::sync_with_stdio(false);
while(cin>>n&&n){
int ans = 0;
memset(bin, 0, sizeof(bin));
memset(tot, 0, sizeof(tot));
memset(number, 0, sizeof(number));
int max_wei = -1;
for(int i=0; i<n; i++){
cin>>num[i];
int temp = num[i];
int wei = 1;
while(temp){
bin[i][wei] = (temp%2);
if(temp%2==1){
tot[wei]++;
}
wei++;
temp/=2;
}
max_wei = max(max_wei, wei-1);
number[i] = wei-1;
ans ^= num[i];
}
if(ans == 0){
cout<<"No"<<endl;
continue;
}
else{
cout<<"Yes"<<endl;
for(int i=0; i<n; i++){
int change = 0;
bool flag = true;
for(int j=max_wei; j>number[i]; j--){
if(tot[j]%2) {
flag = false;
break;
}
}
if(!flag) continue;
if(bin[i][number[i]] == 0&&tot[max_wei]%2 == 1) continue;
{
int ans = 0;
for(int j=max_wei; j>=1; j--){
if(tot[j]%2&&bin[i][j] == 0){
ans -= (1<<(j-1));
}
else if(tot[j]%2&&bin[i][j] == 1){
ans += (1<<(j-1));
}
}
cout<<num[i]<<" "<<num[i]-ans<<endl;
}
}
}
}
return 0;
}

E找规律

先打表就行了

AC代码

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
37
38
39
40
41
42
43
44
45
//#include <bits/stdc++.h>
//using namespace std;
//const int maxn = 1e3+10;
//int num[maxn];
//void dfs(int x){
// for(int i=0; (1<<i)<=x; i++){
// if(num[x-(1<<i)] == 0){
// num[x] = 1;
// return;
// }
// }
// num[x] = 0;
// return ;
//}
//
//int main(){
// ios::sync_with_stdio(false);
// memset(num, -1, sizeof(num));
// num[0] = 0;
// num[1] = num[2] = 1;
// for(int i=3; i<=100; i++){
// dfs(i);
// }
// for(int i=1; i<=100; i++){
// cout<<i<<" "<<num[i]<<endl;
// }
//
// return 0;
//}
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
while(cin>>n){
if(n%3){
cout<<"Kiki"<<endl;
}
else{
cout<<"Cici"<<endl;
}
}
return 0;
}

M

利用环形博弈的对称性,注意讨论的充分性

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
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, k;
int t;
cin>>t;
int kase = 1;
while(t--){
cin>>n>>k;
if(k == 1&&n%2){
printf("Case %d: first\n", kase++);
continue;
}
if(n<=k){
printf("Case %d: first\n", kase++);
}
else{
printf("Case %d: second\n", kase++);
}
}
return 0;
}

一道相似的原型的题目

A funny Game

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <cstdio>
using namespace std;
int main(){
int n;
while(cin>>n&&n){
if(n<=2){
printf("Alice\n");
}
else{
printf("Bob\n");
}
}
return 0;
}

威佐夫博弈

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
//#include <iostream>
//#include <cstdio>
//#include <cstring>
//#include <cmath>
//#include <algorithm>
//
//using namespace std;
//const int maxn = 1e3+10;
//int mp[maxn][maxn];
//void dfs(int x, int y){
// for(int i=1; i<=x; i++){
// if(mp[x-i][y] == 0){
// mp[x][y] = 1;
// return ;
// }
// }
// for(int i=1; i<=y; i++){
// if(mp[x][y-i] == 0){
// mp[x][y] = 1;
// return ;
// }
// }
// for(int i=1; i<=min(x, y); i++){
// if(mp[x-i][y-i] == 0){
// mp[x][y] = 1;
// return ;
// }
// }
// mp[x][y] = 0;
// return ;
//}
//
//int main(){
// int a, b;
// while(cin>>a>>b){
// mp[0][0] = 0;
// for(int i=1; i<=100; i++) mp[i][0] = mp[0][i] = 1;
// for(int i=1; i<=100; i++){
// for(int j=1; j<=100; j++){
// dfs(i, j);
// }
// }
// for(int i=1; i<=30; i++){
// for(int j=1; j<=30; j++){
// printf("(%d, %d): %d\n", i, j, mp[i][j]);
// }
// }
// }
// return 0;
//}
#include <bits/stdc++.h>
using namespace std;
int main(){
int a, b;
while(cin>>a>>b){
if(a>b) swap(a, b);
int k = b-a;
int l = int(((sqrt(5.0)+1)/2.0)*k);
if(l == a&&l+k == b){
cout<<0<<endl;
}
else{
cout<<1<<endl;
}
}
return 0;
}

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
//#include <bits/stdc++.h>
//using namespace std;
//const int maxn = 1e3+10;
//int mp[maxn][maxn];
//
//void dfs(int x, int y){
// if(mp[x][y]!=-1) return;
// for(int i=1; i<=y; i++){
// for(int j=i*2; j>=1; j--){
// if(mp[x-i][i*2] == 0){
// //cout<<x-i<<" "<<j<<endl;
// //cout<<x<<" "<<y<<endl<<endl;
// mp[x][y] = 1;
// return;
// }
// }
// }
// mp[x][y] = 0;
// return;
//}
//
//int main()
//{
// memset(mp, -1, sizeof(mp));
// mp[1][1] = 1;
// mp[2][1] = 0;
// mp[3][2] = 0;
// mp[4][3] = 1;
// for(int i=1; i<=20; i++){
// for(int j=i-1; j>=1; j--){
// dfs(i, j);
// }
// }
// for(int i=1; i<=20; i++){
// cout<<i<<" "<<mp[i][i-1]<<endl;
// }
// return 0;
//}
#include <bits/stdc++.h>
using namespace std;
int biao[100];
set<int> s;
void init(){
biao[0] = 2;
biao[1] = 3;
s.clear();
s.insert(2);
s.insert(3);
for(int i=2; i<=45; i++){
biao[i] = biao[i-1]+biao[i-2];
s.insert(biao[i]);
}
}
int main(){
int n;
init();
while(cin>>n&&n){
if(s.count(n) != 0){
cout<<"Second win"<<endl;
}
else cout<<"First win"<<endl;
}
}

未解决的问题

Contents
  1. 1. B Euclid’s game
    1. 1.1. ac code
  2. 2. cutting paper
    1. 2.1. AC code
  3. 3. C
  4. 4. m堆石子的博弈
  5. 5. E找规律
    1. 5.1. AC代码
  6. 6. M
    1. 6.1. AC code
    2. 6.2. 一道相似的原型的题目
    3. 6.3. AC code
  7. 7. 威佐夫博弈
  8. 8. F取石子游戏
  9. 9. 未解决的问题
{{ live2d() }}