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

第二波题目大多都是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边双缩点搞一下就行了

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N1 105
#define M1 505
#define ll long long 
#define dd double
using namespace std;
const dd eps=1e-7;

template <typename _T> void read(_T &ret)
{
    ret=0; _T fh=1; char c=getchar();
    while(c<'0'||c>'9'){ if(c=='-') fh=-1; c=getchar(); }
    while(c>='0'&&c<='9'){ ret=ret*10+c-'0'; c=getchar(); }
    ret=ret*fh;
}
struct Edge{
int to[M1*2],nxt[M1*2],val[M1*2],head[N1],cte;
void ae(int u,int v,int w)
{
    cte++; to[cte]=v; nxt[cte]=head[u];
    head[u]=cte; val[cte]=w;
}
}e,E;

int T,n,m;
int low[N1],dfn[N1],use[N1],stk[N1],dad[N1],sum[N1],tim,num,tp;
void tarjan(int x,int fa)
{
    int j,v;
    low[x]=dfn[x]=++tim; stk[++tp]=x; use[x]=1;
    for(j=e.head[x];j;j=e.nxt[j])
    {
        v=e.to[j]; if(e.val[j]==fa) continue;
        if(!dfn[v]){
            tarjan(v,e.val[j]);
            low[x]=min(low[x],low[v]);
        }else if(use[x]){
            low[x]=min(low[x],dfn[v]);
        }
    }
    if(low[x]==dfn[x])
    {
        num++;
        while(stk[tp]!=x){ use[stk[tp]]=0; dad[stk[tp]]=num; sum[num]++; tp--; }
        use[x]=0; dad[x]=num; sum[num]++; tp--;
    }
}

void rebuild()
{
    int i,j,v;
    for(i=1;i<=n;i++)
    {
        for(j=e.head[i];j;j=e.nxt[j])
        {
            v=e.to[j];
            if(dad[i]!=dad[v]) 
                E.ae(dad[i],dad[v],0);
        }
    }
}

int sg[N1],de;
void dfs(int x,int fa)
{
    int j,v;
    for(j=E.head[x];j;j=E.nxt[j])
    {
        v=E.to[j]; if(v==fa) continue;
        dfs(v,x); sg[x]^=sg[v]+1;
    }
    if(sum[x]>1 && (sum[x]&1)) sg[x]^=1;
}

void init()
{
    memset(sg,0,sizeof(sg)); memset(low,0,sizeof(low)); 
    memset(sum,0,sizeof(sum)); memset(dfn,0,sizeof(dfn)); 
    memset(dad,0,sizeof(dad)); memset(use,0,sizeof(use)); 
    memset(&e,0,sizeof(e));  memset(&E,0,sizeof(E)); 
    tim=0; tp=0; num=0;
}

int N;
int main()
{
    int i,j,x,y;
    while(scanf("%d",&N)!=EOF) {
    
    int ans=0;
    while(N--)
    {
        init(); read(n); read(m);
        for(i=1;i<=m;i++)
        {
            read(x); read(y); e.ae(x,y,i); e.ae(y,x,i);
        }
        for(i=1;i<=n;i++) if(!dfn[i]) tarjan(i,-1);
        rebuild();
        dfs(dad[1],-1);
        ans^=sg[dad[1]];
    }
    if(ans) puts("Sally"); else puts("Harry");
        
    }
    return 0;
}

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 裸题

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N1 1000010
#define ll long long 
#define dd double
using namespace std;
const dd eps=1e-7;

template <typename _T> void read(_T &ret)
{
    ret=0; _T fh=1; char c=getchar();
    while(c<'0'||c>'9'){ if(c=='-') fh=-1; c=getchar(); }
    while(c>='0'&&c<='9'){ ret=ret*10+c-'0'; c=getchar(); }
    ret=ret*fh;
}

int T,n,K,m;
int a[N1],b[N1];


void print(int t)
{
    int x=n,i,mi;
    for(i=m;i>=1;i--)
    {
        if(x>=a[i])
        {
            x-=a[i]; mi=a[i];
        }
    }
    printf("Case %d: %d
",t,mi);
}

int main()
{
    freopen("t2.in","r",stdin);
    int i,j,l,r,mid,ans,t;
    scanf("%d",&T);
    for(t=1;t<=T;t++) {
    
    scanf("%d%d",&n,&K);
    memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); 
    a[1]=1; b[1]=1; 
    for(i=2,m=1;b[i-1]<n;i++)
    {
        a[i]=b[i-1]+1; m++;
        l=1,r=i-1; ans=0;
        while(l<=r)
        {
            mid=(l+r)>>1;
            if(1ll*K*a[mid]<1ll*a[i]) ans=mid, l=mid+1;
            else r=mid-1;
        }
        b[i]=a[i]+b[ans];
    }
    if(a[i-1]==n) printf("Case %d: lose
",t);
    else print(t); ///
    
    }
    return 0;
}