简单博弈论
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; }
|
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; 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 <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; 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; } }
|
未解决的问题
