第二波题目大多都是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 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            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 
          
            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 }
          
         
        
       
      

 

 

K倍动态减法游戏

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

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

 

2倍动态减法游戏

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

简单证明如下

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

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

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

先手如果取了$x\geq 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 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           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 
          
            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: %d\n",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]
           
            >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: lose\n",t);59 else print(t); ///60 61 }62 return 0;63 }