您的位置: 首页  >  文章  >  博弈论模板

博弈论模板

分类: 文章 • 2022-10-05 10:59:20

一。巴什博弈

只是最简单的博弈了，只简单说一下满足条件，一堆总数为n个，每次可以取1-m个石头。  核心是n=(m+1)*r+s;也就是说用n%(m+1) 判断是否等于0即可。

例题：hdu 1846 

巴什博弈

[html] view plain copy
  1. int main()  
  2. {  
  3.     int n;  
  4.     cin>>n;  
  5.     while(n--)  
  6.     {  
  7.         int a,b;  
  8.         cin>>a>>b;  
  9.         int t=a%(b+1);  
  10.         if(t>=1)  
  11.         {  
  12.             cout<<"first"<<endl;  
  13.         }  
  14.         else  
  15.         {  
  16.             puts("second");  
  17.         }  
  18.     }  
  19. }  

二。斐波那契博弈。

要求是在一堆里，轮流取石头，每次取的石头要求在1-上一次对手取的石头的2倍之间  包括两个端点，核心是把这个数分解成斐波拉契数列，换句话说，判断这个n是否是斐波拉契数即可。

例题：hdu2516

斐波那契博弈

[html] view plain copy
  1. int main()  
  2. {  
  3.     int n;  
  4.     int a[maxn];  
  5.     a[0]=2;  
  6.     a[1]=3;  
  7.     for(int i=2;i<=50;i++)  
  8.     {  
  9.         a[i]=a[i-1]+a[i-2];  
  10.     }  
  11.     while(cin>>n,n)  
  12.     {  
  13.         int flag=0;  
  14.         for(int i=0;i<=50;i++)  
  15.         {  
  16.             if(n==a[i])  
  17.             {  
  18.                 puts("Second win");  
  19.                 flag=1;  
  20.                 break;  
  21.             }  
  22.         }  
  23.         if(!flag)  
  24.         {  
  25.             puts("First win");  
  26.         }  
  27.     }  
  28. }  

三。威佐夫博弈。

要求是两堆石头，两个人轮流从某一堆同时从两堆中取同样多的物品。最少一个，多则无限。

这个博弈的关键在于一个黄金分割数。


就要提到一种叫奇异局势。

博弈论模板


博弈论模板

意思是B-A（当然保证B>A） A=黄金分割数*(B-A)的话就是奇异局势。核心就在这里。


例题：poj 1067

威佐夫博弈

[html] view plain copy
  1. int main()  
  2. {  
  3.     int a,b;  
  4.     while(cin>>a>>b)  
  5.     {  
  6.         if(a>b)  
  7.             swap(a,b);  
  8.         int c=floor((b-a)*((sqrt(5.0)+1)/2));  
  9.         if(c==a)  
  10.         {  
  11.             puts("0");  
  12.         }  
  13.         else  
  14.         {  
  15.             puts("1");  
  16.         }  
  17.     }  
  18. }  


四。尼姆博弈。要求是n堆里面，取一堆任意多的物品。每次取一个，多者不限。

博弈论模板


博弈论模板



核心也就是异或。



例题：hdu 1850

尼姆博弈

[html] view plain copy
  1. int main()  
  2. {  
  3.     int m;  
  4.     while(cin>>m,m)  
  5.     {  
  6.         int ans=0,sum=0;  
  7.         int a[maxx];  
  8.         for(int i=1;i<=m;i++)  
  9.         {  
  10.             cin>>a[i];  
  11.             ans^=a[i];  
  12.         }  
  13.         if(ans==0) puts("0");  
  14.         else  
  15.         {  
  16.             for(int i=1;i<=m;i++)  
  17.             {  
  18.                 int k=ans^a[i];  
  19.                 if(k<a[i])  
  20.                     sum++;  
  21.             }  
  22.             cout<<sum<<endl;  
  23.         }  
  24.     }  
  25. }  


五。SG值。 


博弈论模板

例题：hdu 1847

SG值


[html] view plain copy
  1. #include <bits/stdc++.h>  
  2. //#include <ext/pb_ds/tree_policy.hpp>  
  3. //#include <ext/pb_ds/assoc_container.hpp>  
  4. //using namespace __gnu_pbds;  
  5. using namespace std;  
  6.   
  7.   
  8.   
  9. #define pi acos(-1)  
  10. #define endl '\n'  
  11. #define me(x) memset(x,0,sizeof(x));  
  12. #define foreach(it,a) for(__typeof((a).begin()) it=(a).begin();it!=(a).end();it++)  
  13. typedef long long LL;  
  14. const int INF=0x3f3f3f3f;  
  15. const LL LINF=0x3f3f3f3f3f3f3f3fLL;  
  16. const int dx[]={-1,0,1,0,-1,-1,1,1};  
  17. const int dy[]={0,1,0,-1,1,-1,1,-1};  
  18. const int maxn=1e3+5;  
  19. const int maxx=2e5+100;  
  20. const double EPS=1e-7;  
  21. const int mod=1000000007;  
  22. template<class T>inline T min(T a,T b,T c) { return min(min(a,b),c);}  
  23. template<class T>inline T max(T a,T b,T c) { return max(max(a,b),c);}  
  24. template<class T>inline T min(T a,T b,T c,T d) { return min(min(a,b),min(c,d));}  
  25. template<class T>inline T max(T a,T b,T c,T d) { return max(max(a,b),max(c,d));}  
  26. //typedef tree<pt,null_type,less< pt >,rb_tree_tag,tree_order_statistics_node_update> rbtree;  
  27. /*lch[root] = build(L1,p-1,L2+1,L2+cnt);  
  28.     rch[root] = build(p+1,R1,L2+cnt+1,R2);中前*/  
  29. /*lch[root] = build(L1,p-1,L2,L2+cnt-1);  
  30.     rch[root] = build(p+1,R1,L2+cnt,R2-1);中后*/  
  31. long long gcd(long long a , long long b){if(b==0) return a;a%=b;return gcd(b,a);}  
  32.   
  33.   
  34. int sg[maxx];  
  35. int a[100];  
  36. int mex(int x)  
  37. {  
  38.     if(sg[x]!=-1) return sg[x];  
  39.     int vis[maxn];  
  40.     me(vis);  
  41.     for(int i=0;i<=10;i++)  
  42.     {  
  43.         int temp=x-a[i];  
  44.         if(temp<0) break;  
  45.         sg[temp]=mex(temp);  
  46.         vis[sg[temp]]=1;  
  47.     }  
  48.     for(int i=0;;i++)  
  49.     {  
  50.         if(!vis[i])  
  51.         {  
  52.             sg[x]=i;  
  53.             break;  
  54.         }  
  55.     }  
  56.     return sg[x];  
  57. }  
  58.   
  59.   
  60. int main()  
  61. {  
  62.     int n;  
  63.     a[0]=1;  
  64.     for(int i=1;i<=10;i++)  
  65.     {  
  66.         a[i]=a[i-1]*2;  
  67.     }  
  68.     while(cin>>n)  
  69.     {  
  70.         memset(sg,-1,sizeof(sg));  
  71.         if(mex(n)) puts("Kiki");  
  72.         else  
  73.             puts("Cici");  
  74.     }  
  75. }  

相关推荐