思路:

本题的模型转换十分巧妙:

仅考虑空格移动,注意到空格移动的路径事实上是黑白相间,且不自交的路径.

这样我们黑白染色变成二分图,转化为二分图上的博弈问题.

显然的性质是从一个点出发先手必胜当且仅当这个点是二分图最大匹配的必须点.

若这个点没有匹配点,先手必败;否则将这个点的匹配点的匹配点设为0,删除这个点,并从这个点的匹配点开始增广.若能够增广,显然这个点不是必须点.

这样只需增广\(O(K)\)次,时间复杂度\(O(KN^4)\).

(另外本沙茶终于明白匈牙利算法是怎回事了...)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
 
#define N 41
int ano[N*N];
bool changed[N*N];
 
int head[N*N],next[N*N<<2],end[N*N<<2];
inline void addedge(int a,int b){
    static int q=1;
    end[q]=b;
    next[q]=head[a];
    head[a]=q++;
}
inline void make(int a,int b){
    addedge(a,b);
    addedge(b,a);
}
 
bool del[N*N];
inline bool dfs(int x){
    if(del[x])return 0;
    for(int j=head[x];j;j=next[j]){
        if(!changed[end[j]]&&!del[end[j]]){
            changed[end[j]]=1;
            if(!ano[end[j]]||dfs(ano[end[j]])){
                ano[x]=end[j],ano[end[j]]=x;
                return 1;
            }
        }
    }
    return 0;
}
 
char s[N];
int map[N][N],lab[N][N];
inline int hash(char c){
    if(c=='X')return 0;
    if(c=='O')return 1;
    return 2;
}
 
inline int getdis(int x,int y){
    return x>y?x-y:y-x;
}
 
#define Q 2010
bool win[Q];
 
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
     
    register int i,j;
    for(i=1;i<=n;++i){
        scanf("%s",s+1);
        for(j=1;j<=m;++j)map[i][j]=hash(s[j]);
    }
     
    int x,y;
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
            if(map[i][j]==2)
                x=i,y=j;
     
    int id=0;
    map[x][y]=0;
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
            if((((getdis(i,x)+getdis(j,y))%2)^map[i][j])==0)
                lab[i][j]=++id;
     
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)if(lab[i][j]){
            if(lab[i-1][j])addedge(lab[i][j],lab[i-1][j]);
            if(lab[i+1][j])addedge(lab[i][j],lab[i+1][j]);
            if(lab[i][j-1])addedge(lab[i][j],lab[i][j-1]);
            if(lab[i][j+1])addedge(lab[i][j],lab[i][j+1]);
        }
     
    for(i=1;i<=id;++i)
        if(!ano[i])memset(changed,0,sizeof changed),dfs(i);
 
    int steps;
    scanf("%d",&steps);
    steps<<=1;
    for(i=1;i<=steps;++i){
        if(ano[lab[x][y]]){
            int t=ano[lab[x][y]];
            ano[lab[x][y]]=ano[t]=0;
            del[lab[x][y]]=1;
            memset(changed,0,sizeof changed);
            win[i]=!dfs(t);
        }
        else{
            del[lab[x][y]]=1;
            win[i]=0;
        }
        scanf("%d%d",&x,&y);
    }
     
    int re=0;
    for(i=1;i<=steps;i+=2){
        if(win[i]&&win[i+1])++re;
    }
    printf("%d\n",re);
    for(i=1;i<=steps;i+=2){
        if(win[i]&&win[i+1])
            printf("%d\n",(i+1)>>1);
    }
    return 0;
}

思路:

首先将图黑白二染色变成二分图.

然后求出一组最大匹配.

如果某个点不在匹配中,那么先手选择这个点.

那么后手只能走向一个匹配点(否则就不是最大匹配了).于是先手就可以沿着匹配边走回来.

那么此时如果后手还能走的话,就必定走到一个匹配点上.(否则就存在增广路了).于是先手又沿着匹配边走回来.

最后总是后手无路可走.因此先手必胜.

因此如果某个点不是最大匹配的必须点.就可以选择这个点.

如何找出这个呢?

在残量网络上,从\(S\)出发能够遍历到的左端的点,以及从\(T\)出发能够反向遍历到的右端的点.

证明的话,就是如果能够遍历到,就证明可以被换掉,而使得匹配数不减少.(稍微脑补一下)

(注意总点数要开2W,我不知道为什么)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define INF ~0U>>1
struct Solver{
    static const int V=20010;
    static const int E=V<<2;
    int head[V],next[E],end[E],flow[E],ind;
    int gap[V],d[V],stk[V],top,cur[V];
    inline void reset(){
        ind=top=0,memset(head,-1,sizeof head);
    }
    inline void addedge(int a,int b,int f){
        int q=ind++;
        end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;
    }
    inline void make(int a,int b,int f){
        //printf("%d %d %d\n",a,b,f);
        addedge(a,b,f),addedge(b,a,0);
    }
    inline void bfs(int T){
        static int q[V];
        int fr=0,ta=0;
        memset(d,-1,sizeof d),memset(gap,0,sizeof gap),++gap[d[T]=0],q[ta++]=T;
        while(fr^ta){
            int i=q[fr++];
            for(int j=head[i];j!=-1;j=next[j])if(d[end[j]]==-1)
                ++gap[d[end[j]]=d[i]+1],q[ta++]=end[j];
        }
    }
    inline int Maxflow(int S,int T){
        int re=0,ins,Min,i,u=S;
        bfs(T),memcpy(cur,head,sizeof cur);
        while(d[S]<T-S+1){
            if(u==T){
                for(Min=INF,i=0;i<top;++i)if(Min>flow[stk[i]])Min=flow[stk[i]],ins=i;
                for(re+=Min,i=0;i<top;++i)flow[stk[i]]-=Min,flow[stk[i]^1]+=Min;
                u=end[stk[top=ins]^1];
            }
            if(u!=T&&!gap[d[u]-1])break;
            bool find=0;
            for(int&j=cur[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]+1==d[u]){
                find=1,ins=j;break;
            }
            if(find){
                stk[top++]=cur[u]=ins,u=end[ins];
            }
            else{
                Min=T-S+1;
                for(int j=head[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]<Min)
                    cur[u]=j,Min=d[end[j]];
                if(!--gap[d[u]])break;
                ++gap[d[u]=Min+1];
                if(u!=S)u=end[stk[--top]^1];
            }
        }
        return re;
    }
}Stg;
 
#define N 110
char s[N];
int lab[N][N],x[N*N],y[N*N];
 
int res[N*N],nums;
 
bool vis[N*N];
inline void bfs(int S,bool rev){
    static int q[N*N];
    int fr=0,ta=0;
    memset(vis,0,sizeof vis),vis[S]=1,q[ta++]=S;
    while(fr^ta){
        int i=q[fr++];
        for(int j=Stg.head[i];j!=-1;j=Stg.next[j])if(Stg.flow[j^rev]&&!vis[Stg.end[j]])
            vis[Stg.end[j]]=1,q[ta++]=Stg.end[j];
    }
}
 
int main(){
    int n,m;scanf("%d%d",&n,&m);
    register int i,j;
    int cnt=0;
    for(i=1;i<=n;++i){
        scanf("%s",s+1);
        for(j=1;j<=m;++j)if(s[j]!='#')lab[i][j]=++cnt,x[cnt]=i,y[cnt]=j;
    }
     
    int S=0,T=cnt+1,num0=0,num1=0;
    Stg.reset();
    for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(lab[i][j]){
        if((i+j)&1){
            ++num1;
            Stg.make(S,lab[i][j],1);
            if(lab[i-1][j])Stg.make(lab[i][j],lab[i-1][j],INF);
            if(lab[i+1][j])Stg.make(lab[i][j],lab[i+1][j],INF);
            if(lab[i][j-1])Stg.make(lab[i][j],lab[i][j-1],INF);
            if(lab[i][j+1])Stg.make(lab[i][j],lab[i][j+1],INF);
        }
        else
            ++num0,Stg.make(lab[i][j],T,1);
    }
     
    if(num0==0&&num1==0){
        puts("LOSE");
        return 0;
    }
     
    int re=Stg.Maxflow(S,T);
     
    /*for(i=S;i<=T;++i)for(j=Stg.head[i];j!=-1;j=Stg.next[j])
        printf("%d %d %d\n",i,Stg.end[j],Stg.flow[j]);*/
    if(num0==num1&&re==num0){
        puts("LOSE");
        return 0;
    }
    puts("WIN");
     
    bfs(S,0);
    for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(lab[i][j]&&((i+j)&1)&&vis[lab[i][j]])res[++nums]=lab[i][j];
    bfs(T,1);
    for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(lab[i][j]&&((i+j)%2==0)&&vis[lab[i][j]])res[++nums]=lab[i][j];
    sort(res+1,res+nums+1);
     
    for(i=1;i<=nums;++i){
        printf("%d %d\n",x[res[i]],y[res[i]]);
    }
     
    return 0;
}

思路:

好歹我也是做过一些博弈论的题,结果毫无思路.

因为不能分解成子游戏,所以SG函数直接废.

反正一切线索全部都指向一条唯一的道路--找规律!!(也许是构造?但我太弱)

然后有一个指数级的暴力打表:

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;

int seq[31],lim;

bool Solve(){
	int num=0;register int i,j;
	for(i=1;i<=30;++i)num+=seq[i];
	if(num==1)return 0;
	int tseq[31];memcpy(tseq,seq,sizeof seq);
	for(i=1;i<=30;++i)for(j=i;j<=30;++j){
		memcpy(seq,tseq,sizeof tseq);
		if(i==j){
			if(seq[i]<2||2*i>lim)continue;
			seq[i]-=2,seq[2*i]++;
			if(!Solve())return 1;
		}
		else{
			if(!seq[i]||!seq[j]||i+j>lim)continue;
			--seq[i],--seq[j],++seq[i+j];
			if(!Solve())return 1;
		}
	}
	return 0;
}
int main(){
	register int i,j,k;
	for(i=1;i<=7;++i){
		for(j=1;j<=26;++j){
			memset(seq,0,sizeof seq),seq[1]=j;lim=i;
			if(Solve()==1)printf("lim=%d n=%d %d\n",i,j,j%i);
		}puts("");
	}
}

然后好像发现了什么.

然后就是AC程序.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
int main(){
    int T;scanf("%d",&T);int n,lim;
    while(T--){
        scanf("%d%d",&n,&lim);
        if(lim==1)puts("1");
        else if(n==1)puts("1");
        else if(n<=lim){
            if(n&1)puts("1");else puts("0");
        }
        else if(lim==2){
            if(n%4==2||n%4==3)puts("0");else puts("1");
        }
        else{
            if(lim&1){
                if(n%lim!=0&&(n%lim)%2==0)puts("0");else puts("1");
            }
            else{
                int t=n%lim;
                if(t==0){
                    if((n/lim)&1)puts("0");else puts("1");
                }
                else if(t&1){
                    if(n%(2*lim)==lim+t)puts("0");else puts("1");
                }
                else{
                    if(n%(2*lim)==t)puts("0");else puts("1");
                }
            }
        }
    }
    return 0;
}