博弈论题目总结（三）——组合游戏进阶

43 阅读 0 评论 29 点赞

我是靠谱客的博主深情咖啡豆，最近开发中收集的这篇文章主要介绍博弈论题目总结（三）——组合游戏进阶，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

第二波题目大多都是sg组合游戏的基本变形，是对游戏规则的小改动。容易提取出SG函数的模型，且SG函数的规律也比较简单

而本文的题目需要较多的模型转化思想

但博弈论的精髓还是打表

翻硬币游戏

一条直线上有很多硬币，有的正面朝上，有的反面朝上，每次可以翻一些硬币，但最右边的硬币必须由正变反，不能操作者输

翻硬币可能会有奇奇怪怪的要求，一次翻好几个，一次翻连续的几个

结论：正面朝上的石子之间互不影响，设正面朝上是1，反面朝上是0，那么SG(0101001)=SG(01)^SG(0001)^SG(0000001)

证明见论文

树形删边游戏

SG(u)=xor{SG(v)+1}

证明见jzh神犇的论文

POJ 3710 Christmas Game

环怎么处理啊？

一个奇环可以分成等长的两条链，SG函数值为0，其他后继状态的SG函数值均>1，故奇环的SG函数值为1

一个偶环只能分成异奇偶的两条链，SG函数值均>0，故奇环的SG函数值为0

tarjan边双缩点搞一下就行了


1 #include <cmath>

2 #include <cstdio>

3 #include <cstring>

4 #include <algorithm>

5 #define N1 105

6 #define M1 505

7 #define ll long long

8 #define dd double

9 using namespace std;
 10 const dd eps=1e-7;
 11
 12 template <typename _T> void read(_T &ret)
 13 {
 14
ret=0; _T fh=1; char c=getchar();
 15
while(c<'0'||c>'9'){ if(c=='-') fh=-1; c=getchar(); }
 16
while(c>='0'&&c<='9'){ ret=ret*10+c-'0'; c=getchar(); }
 17
ret=ret*fh;
 18 }
 19 struct Edge{
 20 int to[M1*2],nxt[M1*2],val[M1*2],head[N1],cte;
 21 void ae(int u,int v,int w)
 22 {
 23
cte++; to[cte]=v; nxt[cte]=head[u];
 24
head[u]=cte; val[cte]=w;
 25 }
 26 }e,E;
 27
 28 int T,n,m;
 29 int low[N1],dfn[N1],use[N1],stk[N1],dad[N1],sum[N1],tim,num,tp;
 30 void tarjan(int x,int fa)
 31 {
 32
int j,v;
 33
low[x]=dfn[x]=++tim; stk[++tp]=x; use[x]=1;
 34
for(j=e.head[x];j;j=e.nxt[j])
 35 
{
 36
v=e.to[j]; if(e.val[j]==fa) continue;
 37
if(!dfn[v]){
 38 
tarjan(v,e.val[j]);
 39
low[x]=min(low[x],low[v]);
 40
}else if(use[x]){
 41
low[x]=min(low[x],dfn[v]);
 42 
}
 43 
}
 44
if(low[x]==dfn[x])
 45 
{
 46
num++;
 47
while(stk[tp]!=x){ use[stk[tp]]=0; dad[stk[tp]]=num; sum[num]++; tp--; }
 48
use[x]=0; dad[x]=num; sum[num]++; tp--;
 49 
}
 50 }
 51
 52 void rebuild()
 53 {
 54
int i,j,v;
 55
for(i=1;i<=n;i++)
 56 
{
 57
for(j=e.head[i];j;j=e.nxt[j])
 58 
{
 59
v=e.to[j];
 60
if(dad[i]!=dad[v])
 61
E.ae(dad[i],dad[v],0);
 62 
}
 63 
}
 64 }
 65
 66 int sg[N1],de;
 67 void dfs(int x,int fa)
 68 {
 69
int j,v;
 70
for(j=E.head[x];j;j=E.nxt[j])
 71 
{
 72
v=E.to[j]; if(v==fa) continue;
 73
dfs(v,x); sg[x]^=sg[v]+1;
 74 
}
 75
if(sum[x]>1 && (sum[x]&1)) sg[x]^=1;
 76 }
 77
 78 void init()
 79 {
 80
memset(sg,0,sizeof(sg)); memset(low,0,sizeof(low));
 81
memset(sum,0,sizeof(sum)); memset(dfn,0,sizeof(dfn));
 82
memset(dad,0,sizeof(dad)); memset(use,0,sizeof(use));
 83
memset(&e,0,sizeof(e));
memset(&E,0,sizeof(E));
 84
tim=0; tp=0; num=0;
 85 }
 86
 87 int N;
 88 int main()
 89 {
 90
int i,j,x,y;
 91
while(scanf("%d",&N)!=EOF) {
 92
 93
int ans=0;
 94
while(N--)
 95 
{
 96 
init(); read(n); read(m);
 97
for(i=1;i<=m;i++)
 98 
{
 99 
read(x); read(y); e.ae(x,y,i); e.ae(y,x,i);
100 
}
101
for(i=1;i<=n;i++) if(!dfn[i]) tarjan(i,-1);
102 
rebuild();
103
dfs(dad[1],-1);
104
ans^=sg[dad[1]];
105 
}
106
if(ans) puts("Sally"); else puts("Harry");
107
108 
}
109
return 0;
110 }

View Code

K倍动态减法游戏

现在有一堆石子，两个人轮流取，后手取的石子数不能超过先手取的K倍，第一个人不能一下子把石子都取完，取最后一个石子的人赢，问谁能赢

在探究“K倍动态减法游戏前”，先研究一下2倍动态减法游戏，即fibonacci博弈

2倍动态减法游戏

结论：当剩余石子数是斐波那契数时，先手必败

简单证明如下

石子数为2,3时，显然先手必败。

拓展到更大的情况呢？可以利用归纳法证明

设当前堆中石子数是$f(k+1)$，显然$f(k+1)=f(k)+f(k-1)$

先手如果取了$xgeq f(k-1)$个，因为$f(k)leq 2f(k-1)$，故后手一定可以把剩下的都取走，先手必败

先手取了$x<f(k)$个时。

把石子分成两堆，石子数分别是$f(k)$和$f(k-1)$。不论先手在$f(k-1)$这一堆里如何取，后手都可以保证先手必败或剩余石子数是$f(k)$。

先手取的石子数$<f(k-1)/3$时，那么转化成了关于$f(k-1)$的一个子问题，继续递归下去，根据假设会输掉

先手取的石子数$=f(k-1)/3$时，后手取的石子数最大，是$(2/3)f(k-1)$

接下来先手要取$f(k)$这一堆了

先手取的最大石子数是$(4/3)f(k-1)$，而$(4/3)f(k-1)<f(k)$，不能一下子取完，剩下的被后手取走，先手必败

如果取的石子数转化成关于$f(k-1)$的一个子问题，继续递归下去，根据假设会输掉

一开始是石子数如果不是$fib$数，先手必胜

根据齐肯多夫定理，一个数能分解成若干个不相邻的fib数的和

问题变成了成多阶段博弈

而不相邻的两个$fib$数满足$2a(i)<a(j);(j-i>1)$，

先手先取走最小的一个$fib$数石子堆。

那么后手不可能一下子取完第二小的$fib$数石子堆，再根据前面的结论——先手取$fib$数的石子堆一定取不到最后一个，所以这堆石子的最后一个只能被先手取到。

对于更大的fib数也能用相同的方式处理

k倍动态减法游戏

拓展到更高倍该怎么办？

我们也可以构造一个数列$a$，满足$k$倍动态减法游戏所需要的限制

首先，对于所有正整数，都能$a$中几项表示出来，且把这几项从小到大排序后，相邻两项$ka_{j}<a_{j+1}$

我们该构造数列$a$第$i$位了，假设数列的前$i-1$项能表示出的连续的最大的数是$b_{i-1}$

显然$a_{i}=b_{i-1}+1$

加入$a_{i}$以后，我们需要找到$a_{j}$满足$ka_{j}<a_{i}$，那么$a$数列里位置小于等于$j$的每一项都和$a_{i}$组合，那么$b_{i}=a_{i}+b_{j}$

HDU 2486 裸题

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #define N1 1000010
 6 #define ll long long
 7 #define dd double
 8 using namespace std;
 9 const dd eps=1e-7;
10
11 template <typename _T> void read(_T &ret)
12 {
13
ret=0; _T fh=1; char c=getchar();
14
while(c<'0'||c>'9'){ if(c=='-') fh=-1; c=getchar(); }
15
while(c>='0'&&c<='9'){ ret=ret*10+c-'0'; c=getchar(); }
16
ret=ret*fh;
17 }
18
19 int T,n,K,m;
20 int a[N1],b[N1];
21
22
23 void print(int t)
24 {
25
int x=n,i,mi;
26
for(i=m;i>=1;i--)
27 
{
28
if(x>=a[i])
29 
{
30
x-=a[i]; mi=a[i];
31 
}
32 
}
33
printf("Case %d: %dn",t,mi);
34 }
35
36 int main()
37 {
38
freopen("t2.in","r",stdin);
39
int i,j,l,r,mid,ans,t;
40
scanf("%d",&T);
41
for(t=1;t<=T;t++) {
42
43
scanf("%d%d",&n,&K);
44
memset(a,0,sizeof(a)); memset(b,0,sizeof(b));
45
a[1]=1; b[1]=1;
46
for(i=2,m=1;b[i-1]<n;i++)
47 
{
48
a[i]=b[i-1]+1; m++;
49
l=1,r=i-1; ans=0;
50
while(l<=r)
51 
{
52
mid=(l+r)>>1;
53
if(1ll*K*a[mid]<1ll*a[i]) ans=mid, l=mid+1;
54
else r=mid-1;
55 
}
56
b[i]=a[i]+b[ans];
57 
}
58
if(a[i-1]==n) printf("Case %d: losen",t);
59
else print(t); ///
60
61 
}
62
return 0;
63 }