博弈论模板

港控/mmm° 2022-05-31 10:49 218阅读 0赞

一。巴什博弈

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

例题：hdu 1846

[巴什博弈][Link 1]

**\[html\]** [view plain][] [copy][view plain]

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

[斐波那契博弈][Link 2]

**\[html\]** [view plain][] [copy][view plain]

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. \}

三。威佐夫博弈。

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

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

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

![Center][]

![Center 1][]

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

例题：poj 1067

[威佐夫博弈][Link 3]

**\[html\]** [view plain][] [copy][view plain]

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堆里面，取一堆任意多的物品。每次取一个，多者不限。

![Center 2][]

![20170327232001780][]

核心也就是异或。

例题：hdu 1850

[尼姆博弈][Link 4]

**\[html\]** [view plain][] [copy][view plain]

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值。

![20170327233540792][]

例题：hdu 1847

[SG值][SG]

**\[html\]** [view plain][] [copy][view plain]

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. \} 
76.

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=1846
[view plain]: http://blog.csdn.net/qq_36553623/article/details/67061459#
[Link 2]: http://acm.hdu.edu.cn/showproblem.php?pid=2516
[Center]: /images/20220531/44eba495440b4cbba3317a9eb2255e2c.png
[Center 1]: /images/20220531/9ee67064d7b04c7c889a73583bda4778.png
[Link 3]: http://poj.org/problem?id=1067
[Center 2]: /images/20220531/fd970400618b4b3eb20b82fb0a1cd576.png
[20170327232001780]: /images/20220531/797e213a6dbb4e65bc32dfa9199889a9.png
[Link 4]: http://acm.hdu.edu.cn/showproblem.php?pid=1850
[20170327233540792]: /images/20220531/5dd0f1e8737341e3857892b29ac32d21.png
[SG]: http://acm.hdu.edu.cn/showproblem.php?pid=1847