bzoj2463 谁能赢呢？

题目大意：给定一个n×n的方格，从（1，1）开始走，每次可以到上下左右没有到过的一个格子，alice先手，交替操作，如果先手必胜则输出'Alice’，否则输出‘Bob’。

思路：lcomyn大爷秒暴结论。后来仔细想了想，只发现走一步肯定会改变格子奇偶性。其实如果n是偶数，那么就可以用2×1的骨牌覆盖，每次走到另一端后，另一个人走到新格子，所以先手必胜；如果n是奇数，那么就可以去掉第一个格子后骨牌覆盖，胜负正好反过来。

#include
      
       #include
       
        using namespace std;int main(){    int n;    while(scanf("%d",&n)==1)    {        if (n==0) break;        if (n%2) printf("Bob\n");        else printf("Alice\n");    }}
       
      

 

bzoj2281 黑白棋（！！！）

题目大意：一行1*n棋盘，交替放共k个白黑棋子，两个人交替操作，先手黑，后手白，可以选1～d个棋子移动，问先手必胜的初态有几种。

思路：假设白棋子左移和黑棋子右移没有意义，所以可以把一个白黑棋子看作一对，中间的棋子数是石子数。变成了每次可以从k/2堆石子中选1～d堆任取石子（每堆取得可以不同），先手必败态是：对二进制的每一位，这一位是1的石子堆数%(d+1)都是0（nimk游戏！！！，有一堆n个石子，每次可以取1～k任意个，先手必败态是：n%(k+1)=0，因为先手取x，后手可以取k+1-x）。设fi[i][j]表示前i-1个二进制位，选了j个石子，fi[i+1][j+q*(d+1)*(1<<i)]+=fi[i][j]*c(k/2,q*(d+1))。

答案是总-先手必败=c(n,k)-fi[up][i]*c(n-i-k/2,k/2)（对于有i个石子的方案，从n-i个位置中选出k对两两相临）

因为题目中没有之前的假设，所以可能会导致从必败态->必败态，这种转化就是错误的。

#include
      
       #include
       
        #include
        
         #include
         
          #define N 10005#define M 105#define up 15#define p 1000000007LL#define LL long longusing namespace std;LL fi[up+1][N],fac[N],inv[N];LL mi(LL x,int y){    LL a=1LL;    for (;y;y>>=1){        if (y&1) a=a*x%p;        x=x*x%p;    }return a;}LL getc(int n,int m){    if (n
          
           =0;--i) inv[i]=inv[i+1]*(LL)(i+1)%p;    for (fi[0][0]=1LL,i=0;i
           
            >1);++q) add(fi[i+1][j+a*(1<
            
             >1,a)%p); } for (ans=getc(n,k),i=0;i<=n-k;++i) add(ans,-(fi[up][i]*getc(n-i-(k>>1),k>>1)%p)); printf("%I64d\n",ans);}
            
           
          
         
        
       
      

 

sg函数

一个状态的sg值是它所有后继状态sg值得mex（最小未出现的自然数），sg=0是必败状态。大多情况下，多个子问题的sg的nim和!=0就是总问题可以必胜。

bzoj1228 E&D

题目大意：给定n堆石子，两堆一组，每次可以从一组中扔掉一堆，将另一堆分为两堆（每堆个数>=1），问先手有无必胜策略。

思路：sg函数在很多情况下可以通过打表找规律，然后求nim和判断。这道题目中的sg函数很有规律，斜着看是一个个的三角形，并且有递归的感觉，所以可以从2^30往下递归一下，相应的减去2^x就可以了，最后如果xy都是1，就是0。

#include
      
       #include
       
        #include
        
         #include
         
          #define LL long longusing namespace std;int sg(int x,int y){    int i=1<<30,j=30,ans=31;    for (;j;--j,i>>=1){        if (x<=i&&y<=i) ans=j;        else{            if (x>i) x-=i;            if (y>i) y-=i;        }    }if (x==1&&y==1) return 0;    return ans;}int main(){    int t,i,j,n,u,v,cnt;    scanf("%d",&t);    while(t--){        scanf("%d",&n);n/=2;cnt=0;        for (i=1;i<=n;++i){            scanf("%d%d",&u,&v);            cnt^=sg(u,v);        }if (cnt) printf("YES\n");        else printf("NO\n");    }}
         
        
       
      

 

bzoj3576 江南乐

题目大意：给定n堆石子，两个人轮流操作，操作是：挑一堆不小于f个的，分成不小于2的任意堆，且要求尽量均分。不能操作的人输。

思路：考虑求sg[i]，可以循环j从2~i表示分的堆数，k=i/j，所以i/j+1的有k1=i%j个，i/j的有k2=j-i%j个，这些sg值的异或就是答案（因为两个相同数的异或是0，所以只需要i%j^1=1才会^sg[i/j+1]，sg[i/j]同理）。但因为i/j的取值只有根i个，且只需要考虑k1、k2的奇偶就可以了，所以可以做到n根n的复杂度。写成记忆化搜索会快很多。

#include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #define N 100001 using namespace std; int sg[N]={
    0},vi[N]={
    0},f; void pre(){     int i,j,k,k1,k2,la;     for (i=f;i
          
         
        
       
      

 

二分图博弈

bzoj2437 兔兔与蛋蛋

题目大意：给定一张棋盘，有白子黑子和空格子，兔兔先手，选一个白格子移到空格子；蛋蛋后手，选一个黑格子移到空格子。给出一个操作序列，问兔兔那几个操作是失误的（认为是失误的当且仅当兔兔操作前有必胜策略，兔兔操作后也有必胜策略）。

思路：黑白染色，相当于空格子走一些黑白交替的无环的路径，不能操作的人输。把空格子和黑格子看作一样，对那些本身颜色和黑白染色一样的格子编号（只有这些格子可能移动）。如果一个点一定在二分图最大匹配中，认为这个点有必胜策略。所以这道题目中要判断每次兔兔操作前后是否有必胜策略，如果都有，就认为它失误了。动态的二分图匹配。

#include
      
       #include
       
        #include
        
         #include
         
          #define N 45#define M 10000using namespace std;int mp[N][N],mt[M]={
    0},vi[M]={
    0},tot,point[M]={
    0},next[M],en[M],fb[M]={
    0},mi[M],    id[N][N]={
    0},dx[4]={
    1,0,-1,0},dy[4]={
    0,1,0,-1};int in(){    char ch=getchar();    while(ch!='.'&&ch!='O'&&ch!='X') ch=getchar();    if (ch=='.') return -1;    return ch=='X';}int ab(int x){
    return (x<0 ? -x : x);}void add(int u,int v){next[++tot]=point[u];point[u]=tot;en[tot]=v;}bool find(int u){    int i,v;    for (i=point[u];i;i=next[i]){        if (vi[v=en[i]]==tot||fb[v]) continue;        vi[v]=tot;        if (!mt[v]||find(mt[v])){            mt[v]=u;mt[u]=v;return true;        }    }return false;}int main(){    int n,m,i,j,k,q,x,y,bx,by,nm=0;scanf("%d%d",&n,&m);    for (i=1;i<=n;++i)      for (j=1;j<=m;++j)          if ((mp[i][j]=in())<0) mp[bx=i][by=j]=1;    for (i=1;i<=n;++i)      for (j=1;j<=m;++j)        if ((mp[i][j]&&(ab(i-bx)+ab(j-by))%2==0)||(!mp[i][j]&&(ab(i-bx)+ab(j-by))%2==1))          id[i][j]=++nm;    for (tot=0,i=1;i<=n;++i)      for (j=1;j<=m;++j)        if (id[i][j])          for (k=0;k<4;++k)            if (id[x=i+dx[k]][y=j+dy[k]])              add(id[i][j],id[x][y]);    for (tot=0,i=1;i<=nm;++i)        if (!mt[i]){++tot;find(i);}    scanf("%d",&q);q<<=1;    for (i=1;i<=q;++i){        if (mt[id[bx][by]]){            j=mt[id[bx][by]];            mt[j]=mt[id[bx][by]]=0;            fb[id[bx][by]]=1;            ++tot;if(find(j)) mi[i]=1;        }else{fb[id[bx][by]]=1;mi[i]=1;}        scanf("%d%d",&bx,&by);    }for (nm=0,i=1;i<=q;i+=2)        if (!mi[i]&&!mi[i+1]) ++nm;    printf("%d\n",nm);    for (i=1;i<=q;i+=2)      if (!mi[i]&&!mi[i+1]) printf("%d\n",(i+1)/2);}
         
        
       
      

 

bzoj1443 游戏

题目大意：给定一个网格，有些格子不能走，有一枚棋子，每次走到相邻的格子。问选那些起始位置能使后手赢。

思路：黑白染色，如果一个点不一定在最大匹配上，就是后手赢。所以在匹配每个点是不是一定在就可以了。

#include
      
       #include
       
        #include
        
         #include
         
          #define N 105#define M 40005using namespace std;int id[N][N],tot=0,point[M]={
    0},next[M],en[M],mt[2][M]={
    0},vi[M]={
    0},fb[M]={
    0},mp[N][N],tt=0,    dx[4]={
    0,1,0,-1},dy[4]={
    1,0,-1,0};int in(){    char ch=getchar();    while(ch!='.'&&ch!='#') ch=getchar();    return ch=='.';}void add(int u,int v){next[++tot]=point[u];point[u]=tot;en[tot]=v;}bool find(int k,int u){    int i,v;    for (i=point[u];i;i=next[i]){        if (vi[v=en[i]]==tt||fb[v]) continue;        vi[v]=tt;        if (!mt[k][v]||find(k,mt[k][v])){            mt[k][v]=u;mt[k][u]=v;return true;        }    }return false;}int main(){    int n,m,i,j,k,x,y,cnt=0,nm=0;scanf("%d%d",&n,&m);    for (i=1;i<=n;++i)      for (j=1;j<=m;++j) if ((mp[i][j]=in())>0) id[i][j]=++nm;    for (tot=0,i=1;i<=n;++i)      for (j=1;j<=m;++j)        if (id[i][j])          for (k=0;k<4;++k)            if (id[x=i+dx[k]][y=j+dy[k]])              add(id[i][j],id[x][y]);    for (i=1;i<=nm;++i)      if (!mt[0][i]){++tt;find(0,i);}    for (i=1;i<=n;++i)      for (j=1;j<=m;++j){          if (!id[i][j]) continue;          if (!mt[0][id[i][j]]){              if (!cnt) printf("WIN\n");              printf("%d %d\n",i,j);              ++cnt;continue;          }else{              for (k=1;k<=nm;++k) mt[1][k]=mt[0][k];              fb[id[i][j]]=1;k=mt[1][id[i][j]];              ++tt;mt[1][k]=mt[1][id[i][j]]=0;              if (find(1,k)){                if (!cnt) printf("WIN\n");                  printf("%d %d\n",i,j);++cnt;              }fb[id[i][j]]=0;          }      }if (!cnt) printf("LOSE\n");}
         
        
       
      

还有一种写法比较快，用网络流求出最大匹配之后，如果从S通过有流量的边到的左边的点和从T通过没流量的边到的右边的点都是不一定出现的点，就是答案。

 

bzoj4600 硬币游戏（！！！）

题目大意：给出一行n个硬币和mq，每次可以选一个反面向上的硬币c*2^i*3^j，（1）选定p、q，p>=1,q>=1&&p*q<=i&&q<=mq，可以把c*2^(i-k*q)*3^j翻过来；（2）选定p、q，p>=1,q>=1&&p*q<=j&&q<=mq，可以把c*2^i*3^(j-k*q)翻过来。

思路：可以看出和c没关系，可以对c的不同看作不同的游戏，sg异或起来就可以了。除去c之后，可以看作i*j的矩阵，每次可以翻i行或者j列的等差数列的棋子，可以把n个棋子看作x个只有右下角(i,j)是1的独立游戏的sg异或，因为每个棋子如果被翻偶数次是不影响先后手胜负的，对于每一个独立游戏，除了右下角的棋子翻了奇数次，其他都翻了偶数次，所以看作独立的是对的。枚举i、j、p、q看作是i、j的一种后继状态，后继又可以看作一个游戏，sg异或起来，求出mex就是ij的sg了。

（orz现场a掉的vampire爷）

#include
      
       #include
       
        #include
        
         #include
         
          #define N 15#define M 21#define up 30001using namespace std;int in(){    char ch=getchar();int x=0;    while(ch<'0'||ch>'9') ch=getchar();    while(ch>='0'&&ch<='9'){        x=x*10+ch-'0';ch=getchar();    }return x;}int sg[M][N][N],m2[N],m3[N],ai[up][2],vi[500]={
    0},vt=0;void pre(int mq){    int i,j,k,p,q,ci,mx;    for (i=0;i
          
           >=1) ++ai[i][0];        for (j=i;j%3==0;j/=3) ++ai[i][1];    }for (i=1;i