第二波题目大多都是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