·巴什博奕
HDU 2188 & HDU 1846
n个石子，每次取1~m个，最后一个取走的人获胜，问谁能获胜
只有当n是m+1的倍数（即n % (m + 1) == 0）的时候，后取者能够获胜
其他时候先取者第一次取完使得剩下的石子是m+1的倍数，每次后取者取i个，先取者就取（m+1-i）个，这样先取者一定自己能取最后一个
变形：条件不变，改为最后取光的人输。 结论：当（n-1）%（m+1）==0时后手胜利。
#include <iostream> #include <cstdio> using namespace std; int main() { int T; scanf("%d", &T); while(T--) { int n, m; scanf("%d %d", &n, &m); if(n % (m + 1) == 0) printf("Rabbit ");//后取者获胜 else printf("Grass "); } return 0; }
HDU 2149 博弈论 巴什博奕
除了谁赢还要输出如果先手想赢第一次应该取多少
先手第一次取完应使剩下的是m+1的倍数，因此取n % (m + 1)个
#include <iostream> #include <cstdio> using namespace std; int main() { int n, m; while(scanf("%d %d", &n, &m) != EOF) { if(n % (m + 1) == 0) printf("none "); else if(n < m) { for(int i = n; i < m; i++) printf("%d ", i); printf("%d ", m); } else { printf("%d ", n % (m + 1)); } } return 0; }
·威佐夫博弈
奇异局势即一方面对必输的局势，可以发现
前几个奇异局势是：（0，0）、（1，2）、（3，5）、（4，7）、（6，10）、（8，13）、（9，15）、（11，18）、（12，20）。
可以看出任何自然数都包含在一个且仅有一个奇异局势中
POJ 1067 威佐夫博弈
两堆石子分别有a，b个，每次可以从一堆中拿走任意个，或者从两堆中都拿走任意个，最后一个取光的获胜
*解法：a =[k（1+√5）/2]，b= a + k， 满足这两个式子的时候先取者会输
#include <iostream> #include <cstdio> #include <cmath> using namespace std; int main() { int a, b; while(scanf("%d %d", &a, &b) != EOF) { int k; if(a > b) swap(a, b); k = b - a; if(a == (int)((sqrt(5.0) + 1) * k / 2)) printf("0 "); else printf("1 "); } return 0; }
HDU 2177
威佐夫博弈，若能胜利，输出使得胜利的第一次取石子的结果
先预处理出所有的奇异局势，然后判断即可
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; const int SZ = 2000100; int sg[SZ], h[SZ], a[SZ], f[SZ]; int vis[SZ]; void getf() { int tmp = 0; memset(f, -1, sizeof(f)); for(int i = 0; i <= 1000000; i++) { if(!vis[i] && !vis[i+tmp]) { f[i] = i+tmp; f[i+tmp] = i; vis[i] = 1; vis[i+tmp] = 1; tmp++; } } } int main() { int a, b; getf(); while(1) { scanf("%d %d", &a, &b); if(a == 0 && b == 0) break; int ans = (int)((double)(b-a) * (1 + sqrt(5)) / 2 ); if(ans == a) printf("0 "); else { printf("1 "); if(ans < a && f[ans] < b && f[ans] - ans == b - a) printf("%d %d ", ans, f[ans]); if(f[a] != ans && f[a] < b) printf("%d %d ", min(f[a],a), max(f[a], a)); if(a != b && f[b] != ans && f[b] < a) printf("%d %d ", min(f[b],b), max(f[b],b)); } } return 0; }
·Nim博弈
P表示必败态，N表示必胜态
若一个状态是P，则它能转移到的所有状态都是N
若一个状态是N，则它能转移到的所有状态都是P
结论：当有n堆数量为a1 a2 a3...an的石子时i，它是P当且仅当a1^a2^a2^...^an==0
Nim博弈的变形：考虑到nim中石子数量其实就是最多能取石子的步数，最后的亦或和也就是最大步数的亦或和，我们可以去求下这个游戏中每堆石子最多能取的步数，这样就能转换为普通的nim了．求出每堆石子最多能取的步数即可
CodeForces 768E
nim博弈的变形，n堆石子中每堆中相同的石子数量只能取一次
每堆石子我们按１，２，３，４．．ｎ的顺序去取石子，当剩下的石子小于等于ｎ的时候，就不能再取了，所以ｎ就是最大步数，即sg函数的值
把每堆石子的最大步数^起来 变成nim博弈
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; int main() { int n; scanf("%d", &n); int flag = 0; while(n--) { int a; scanf("%d", &a); for(int j = 1; j <= 60; j++) { a -= j; if(a < 0) {flag ^= (j-1); break; } } } if(!flag) printf("YES "); else printf("NO "); return 0; }
HDU 1536 S-Nim
也是nim博弈的变形，给出k个数，每次取的石子数只能在这k个数里
求SG函数，每次能取的石子数是f[i]，f数组要排序哒
注意h函数值需要开到100。。因为开大了T到绝望T_T
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <set> using namespace std; const int SZ = 10020; int sg[SZ], f[110]; int h[101]; int n, k; void init(int m) { memset(sg, 0, sizeof(sg)); for(int i = 0; i <= m; i++) { memset(h,0,sizeof(h)); for(int j = 0; j < k; j++) { if(i < f[j]) break; h[sg[i-f[j]]] = 1; } for(int j = 0;; j++) if(!h[j]) { sg[i] = j; break; } } return; } char str[110]; int main() { while(scanf("%d", &k)) { if(!k) break; memset(f, 0, sizeof(f)); for(int i = 0; i < k; i++) scanf("%d", &f[i]); sort(f, f+k); init(10000); int T; scanf("%d", &T); int idx = 0; while(T--) { scanf("%d", &n); int flag = 0, tmp; while(n--) { scanf("%d", &tmp); flag ^= sg[tmp]; } if(flag) printf("W"); else printf("L"); } printf(" "); } return 0; }
·SG函数
https://www.cnblogs.com/ECJTUACM-873284962/p/6921829.html
模板：a记录的是每次取石子的方式
void init(int a[], int n) { memset(sg, 0, sizeof(sg)); for(int i = 0; i <= n; i++) { memset(h, 0, sizeof(h)); for(int j = 1; j <= a[0]; j++) { if(i < a[j]) break; h[sg[i-a[j]]] = 1; } for(int j = 0; j <= n; j++) if(h[j] == 0) { sg[i] = j; break; } } }
hdu 1848
三堆石子，每次能取的个数必须是斐波那契数，f数组就存斐波那契数
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; const int SZ = 1020; int sg[SZ], h[SZ], a[SZ], f[SZ]; void init(int n) { memset(sg, 0, sizeof(sg)); for(int i = 1; i <= n; i++) { memset(h, 0, sizeof(h)); for(int j = 1; j <= 20; j++) { if(i < f[j]) break; h[sg[i-f[j]]] = 1; } for(int j = 0;; j++) if(h[j] == 0) { sg[i] = j; break; } } } int main() { f[0] = f[1] = 1; for(int i = 2; i <= 20; i++) f[i] = f[i-1] + f[i-2]; init(1000); int n, m, k; while(1) { scanf("%d %d %d", &n, &m, &k); if(n == 0 && m == 0 && k == 0) break; if(sg[n] ^ sg[m] ^ sg[k]) printf("Fibo "); else printf("Nacci "); } return 0; }
Codeforces 603C
丢题解 https://blog.csdn.net/huanghongxun/article/details/50197327
丢上还没看懂的SG
Codeforces 603C