bzoj1188

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1188

一道非常好的SG函数题，加深了对博弈论的理解。

以前做的SG函数的题，都是每个瓶子看成一个子游戏，但这里不同，这里是将“每一个豆子”都看成一个子游戏。

SG[i]表示在瓶子i的“每一个豆子”的SG值（即使在同一个瓶子中，每个豆子之间都是相互独立的子游戏）

然后在瓶子i的豆子有去处j和k，我们把有序数对(j,k)看成一个后继，我们知道，每个后继(j,k)也是两个子游戏，所以后继(i,j)的SG值为SG[j]^SG[k]

这样所有后继(j,k)的SG值都知道了，然后根据SG函数的定义就可以求SG[i]了。

最后总游戏是“每一个豆子”的SG值的异或和了。

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<fstream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#include<set>
#include<bitset>
#include<vector>
#include<functional>
#include<deque>
#include<cctype>
#include<climits>
#include<complex>
//#include<bits/stdc++.h>适用于CF,UOJ，但不适用于poj
 
using namespace std;

typedef long long LL;
typedef double DB;
typedef pair<int,int> PII;
typedef complex<DB> CP;

#define mmst(a,v) memset(a,v,sizeof(a))
#define mmcy(a,b) memcpy(a,b,sizeof(a))
#define re(i,a,b)  for(i=a;i<=b;i++)
#define red(i,a,b) for(i=a;i>=b;i--)
#define fi first
#define se second
#define m_p(a,b) make_pair(a,b)
#define SF scanf
#define PF printf
#define two(k) (1<<(k))

template<class T>inline T sqr(T x){return x*x;}
template<class T>inline void upmin(T &t,T tmp){if(t>tmp)t=tmp;}
template<class T>inline void upmax(T &t,T tmp){if(t<tmp)t=tmp;}

const DB EPS=1e-9;
inline int sgn(DB x){if(abs(x)<EPS)return 0;return(x>0)?1:-1;}
const DB Pi=acos(-1.0);

inline int gint()
  {
        int res=0;bool neg=0;char z;
        for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar());
        if(z==EOF)return 0;
        if(z=='-'){neg=1;z=getchar();}
        for(;z!=EOF && isdigit(z);res=res*10+z-'0',z=getchar());
        return (neg)?-res:res; 
    }
inline LL gll()
  {
      LL res=0;bool neg=0;char z;
        for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar());
        if(z==EOF)return 0;
        if(z=='-'){neg=1;z=getchar();}
        for(;z!=EOF && isdigit(z);res=res*10+z-'0',z=getchar());
        return (neg)?-res:res; 
    }

const int maxN=21;

int N;
int SG[maxN+10];
int a[maxN+10];
int tol,bak[maxN*maxN+100];
int cnt,ansi,ansj,ansk;

inline int check()//返回1表示为必败态 
  {
      int res=0,i;
      re(i,1,N)if(a[i]%2==1) res^=SG[i];
      return res==0;
  }

int main()
  {
      freopen("game.in","r",stdin);
      freopen("game.out","w",stdout);
      int i,j,k;
      for(int Case=gint();Case;Case--)
        {
            N=gint();
            re(i,1,N)a[i]=gint();
            SG[N]=0;
            red(i,N-1,1)
              {
                  tol=0;
                        re(j,i+1,N)re(k,j,N)bak[++tol]=SG[j]^SG[k];
                  sort(bak+1,bak+tol+1);
                  tol=unique(bak+1,bak+tol+1)-bak-1;
                  SG[i]=-1;
                  re(j,1,tol)if(bak[j]!=j-1){SG[i]=j-1;break;}
                  if(SG[i]==-1)SG[i]=tol;
              }
            cnt=0;
            re(i,1,N)if(a[i]>=1)re(j,i+1,N)re(k,j,N)
              {
                  a[i]--;a[j]++;a[k]++;
                  if(check()){cnt++;if(cnt==1){ansi=i;ansj=j;ansk=k;}}
                        a[i]++;a[j]--;a[k]--;
                    }
                if(cnt==0)PF("-1 -1 -1
0
"); else PF("%d %d %d
%d
",ansi-1,ansj-1,ansk-1,cnt);
        }
      return 0;
  }