SG 函数先不说, 给自己总结下三大博弈. 和二进制及黄金分割联系密切, 数学真奇妙, 如果不用考试就更好了.
1.Bash Game:n 个物品, 最少取 1 个, 最多取 m 个, 先取完者胜.
给对手留下 (m+1) 的倍数肯定获胜. 若 n%(m+1)==0, 先手必败.
51nod 裸题:
- #include <iostream>
- #include <cstdio>
- using namespace std;
- int main(){
- int t; cin>>t;
- int n,k;
- while(t--){
- cin>>n>>k;
- if(n%(k+1)==0) puts("B");
- else puts("A");
- }
- return 0;
- }
2.Nim Game:n 堆物品, 取某一堆的若干个, 至少取一个, 多者不限, 先取完者胜.
在这个博弈中, 对任何奇异局势 (a,b,c....n), 都有 a^b^...^n==0.
所以直接检测给的局势, 若是奇异局, 先手必败.
如何将 (a,b,c) 转化成奇异局: 将 c 变为 a^b, 即 c -= a^b(^ 是异或)
51nod 裸题:
- #include <iostream>
- #include <cstdio>
- using namespace std;
- int main(){
- int a[1005]={0};
- int ans=0;
- int n; cin>>n;
- for(int i=0;i<n;i++){
- cin>>a[i];
- ans^=a[i];
- }
- if(ans) puts("A");
- else puts("B");
- return 0;
- }
3.Wythoff's Game: 两堆若干个, 轮流从某一堆取任意个或同时从两堆取同样多任意个, 最少一个, 多者不限. 先取完者胜.
局势:(ak,bk)
前几个奇异局:(0,0) (1,2) (3,5) (4,7) (6,10) (8,13) (9,15) (11,18) (12,20)......
1. 发现差值递增, 且局面中第一个值为前面局面中没有出现过的数字的第一个数, 且所有自然数都会出现.
2. 再找规律: 第一个值 =(int) (差值 * 1.618) 而 1.618 = ( sqrt(5)+1 )/2
3. 所以, 只要 ak == (int) (bk - ak) * ( sqrt(5) + 1 ) / 2 先手必输, 否则先手必胜
51nod 裸题:
- #include <iostream>
- #include <cstdio>
- #include <cmath>
- using namespace std;
- double c=(sqrt(5)+1)/2;
- int main(){
- int t; cin>>t;
- int ak,bk;
- while(t--){
- cin>>ak>>bk;
- if(ak>bk) swap(ak,bk);
- int n=(bk-ak)*c;
- if(ak==n) puts("B");
- else puts("A");
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2930466.html