Play a game
题目:从一个n*n的角落出发,每次移动到相邻的,而且没有经过的格子上。谁不能操作了谁输。结论就是n为偶数,先手赢,奇数,后手赢。大佬思路
Brave Game
巴什博弈: 有一堆n个物品,两个人轮流从这堆物品中取物,规定每次可以任意取1至m个,取到最后一个的人获胜。 如果n=m+1,那么由于一次最多只能取m个,所以,无论先取者拿走多少个,后取者都能够一次拿走剩余的物品,那么后者必胜。 如果n=(m+1)r+s,(r为任意自然数,s<=m),那么先取者只要拿走s个物品,如果后取者拿走k(k<=m)个,那么先取者再拿走m+1-k个,结果剩下(m+1)*(r-1)个,始终保持这样的取法,那么先取者必定获胜。#include<bits/stdc++.h> using namespace std; int main() { int T; cin >> T; while(T --) { int n, m; cin >> n >> m; if(n % (m + 1)) cout << "first\n"; else cout << "second\n"; } return 0; }
同类题目:HDU - 2188 参考博客
Public Sale
巴什博弈翻版#include<bits/stdc++.h> using namespace std; int main() { int n, m; while (~scanf("%d%d", &m, &n)) { if (m % (n + 1) == 0) { cout << "none"; } else { if (n >= m) { for (int i = m; i <= n; i ++) { cout << i; if (i != n) cout << " "; } } else cout << m % (n + 1); } cout << "\n"; } return 0; }
kiki's game
自己推出来的状态, 太厉害了吧#include<bits/stdc++.h> using namespace std; int main() { int n, m; while (cin >> n >> m && n && m) { if(m & 1 && n & 1) { cout << "What a pity!" << "\n"; } else cout << "Wonderful!" << "\n"; } return 0; }
取石子游戏
威佐夫博弈: 有两堆各若干个物品,两个人轮流从任一堆取至少一个或同时从两堆中取同样多的物品,规定每次至少取一个,多者不限,最后取光者得胜。 用二维数组理解:推导过程类似上一道题 讲解视频 结论:假设两堆石子为(x,y)(其中x<y)那么先手必败,当且仅当$\left (y - x \right )\ast \frac{\left (\sqrt 5 + 1 \right )}{2}= x$。 其中的$\frac{\left (\sqrt 5 + 1 \right )}{2}$实际就是1.618,黄金分割数! 参考博客#include<bits/stdc++.h> using namespace std; int main() { int n, m; while(~scanf("%d%d", &n, &m)) { if(n > m) swap(n, m); int ans = (m - n) * (sqrt(5) + 1) / 2.0; if(ans == n) cout << 0 << "\n"; else cout << 1 << "\n"; } return 0; }
标签:main,cout,int,博弈论,namespace,35,kuangbin,using,include From: https://www.cnblogs.com/coding-inspirations/p/16739463.html