http://www.lydsy.com/JudgeOnline/problem.php?id=2437
这道题真是极好的。
75分做法：
搜索。
出题人真的挺良心的，前15个数据点的范围都很小，可以直接搜索。
#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，但不适用于pojusing 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-;
inline int sgn(DB x){if(abs(x)<EPS)return ;return(x>)?:-;}
const DB Pi=acos(-1.0);inline int gint()
{
int res=;bool neg=;char z;
for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar());
if(z==EOF)return ;
if(z=='-'){neg=;z=getchar();}
for(;z!=EOF && isdigit(z);res=res*+z-'',z=getchar());
return (neg)?-res:res;
}
inline LL gll()
{
LL res=;bool neg=;char z;
for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar());
if(z==EOF)return ;
if(z=='-'){neg=;z=getchar();}
for(;z!=EOF && isdigit(z);res=res*+z-'',z=getchar());
return (neg)?-res:res;
}const int maxN=;
const int dx[]={,,-,};
const int dy[]={,-,,};
const int maxK=;int N,M,K;
int mp[maxN+][maxN+];
int x,y;int tot,win[maxK+];inline int find(int x,int y,int z)
{
int i;
re(i,,)
{
int tx=x+dx[i],ty=y+dy[i];
if(<=tx && tx<=N && <=ty && ty<=M && mp[tx][ty]==z)
{
swap(mp[x][y],mp[tx][ty]);
if(!find(tx,ty,((z-)^)+)){swap(mp[x][y],mp[tx][ty]);return ;}
swap(mp[x][y],mp[tx][ty]);
}
}
return ;
}int main()
{
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
int i,j;
N=gint();M=gint();
re(i,,N)re(j,,M)
{
char z=getchar();while(z!='.' && z!='O' && z!='X')z=getchar();
switch(z)
{
case 'O':mp[i][j]=;break;
case 'X':mp[i][j]=;break;
case '.':mp[i][j]=;x=i;y=j;break;
}
}
K=gint();
re(i,,K)
{
int tx=gint(),ty=gint();
win[i]=find(x,y,);
swap(mp[x][y],mp[tx][ty]);
x=tx;y=ty;
if(win[i] && find(x,y,)){tot++;win[i]=;}else win[i]=;
tx=gint(),ty=gint();
swap(mp[x][y],mp[tx][ty]);
x=tx;y=ty;
}
PF("%d\n",tot);
re(i,,K)if(win[i])PF("%d\n",i);
return ;
}
100分做法：
二分图匹配。
性质1 空格移动的路径一定不会自交。
记出发格子为A_0，第i步到达的格子为A_i。
虽然第一次相交的点不一定是A_0，但不失一般性，假设走了n步之后第一次与A_0相交，即走过了A_0,A_1,A_2,…,A_n-1,A_n。
因为每次是移动是上下左右四个方向之一，因为又回到出发点，所以有多少次向上走就有多少次向下走，有多少次向左走就有多少次向右走，所以n是偶数。
我们发现，第奇数次移动的为先手，即A_1,A_3,A_5,…,A_n-1；第偶数次移动的为后手，即A_0,A_2,A_4,…,A_n。
因为又回到了出发地，所以A_1和A_n是同一个棋子，但是2个人同时移动了这个棋子，矛盾，所以空格移动的路径一定不会自交。
不妨将刚开始时空格所在的格子看成黑色 那么空格移动的路径一定是黑白相间的。
建立二分图，左边为黑色，右边为白色，之间有相邻关系的连边。兔兔是从左边走到右边，蛋蛋是从右边走到左边。
性质2 当且仅当最大匹配一定覆盖空格所在的结点时，兔兔必胜；否则蛋蛋必胜。
（1）如果存在一个最大匹配不覆盖空格所在的结点，蛋蛋必胜。
如图实线是匹配边，虚线是非匹配边，空格所在的结点为start。
因为最大匹配不覆盖空格所在的结点start，所以兔兔只能沿着某一条非匹配边到右边，不妨设到了v（如果没有到右边的没走过的非匹配边，那么兔兔输了）。
v一定是被覆盖的（不然start就可以连到v，就不是最大匹配了）。
蛋蛋可以沿着覆盖v的匹配边到左边的u。
也就是说，当兔兔到了右边后，蛋蛋一定有路径回到左边；但是当蛋蛋到了左边后，兔兔不一定有路径到右边。
所以如果存在一个最大匹配不覆盖空格所在的结点，蛋蛋必胜。
（2）如果最大匹配一定覆盖空格所在的结点时，兔兔必胜。
我们可以类似（1）中进行分析。
虽然这道题不是问我们谁必胜，但这给我们接下来提供了一种思考方法。
现在兔兔走第1步，从start走到v。
首先我们根据性质2，判断兔兔是否必胜，就是判断使用start点和不使用start点时的最大匹配是否相等，如果不相等，说明最大匹配一定覆盖start点，兔兔必胜。
然后强行覆盖start到v的边。
我们要这时候蛋蛋要从左边往右边走，我们要判断蛋蛋是否必胜。
如果蛋蛋能够走到兔兔的一个必败态，那么蛋蛋必胜。
根据性质2，我们得出结论：在start到v的边一定被覆盖的情况下，当且仅当与v有边相连的所有点都一定被最大匹配覆盖，蛋蛋必输；否则蛋蛋必胜。
所以如果在某种最大匹配方案中，与v相连的某个点没有被最大匹配覆盖，那么蛋蛋必胜。
如图，与v相连的点为a,b,c，在图示的最大匹配方案中，c没有被最大匹配覆盖，所以蛋蛋必胜。
接下来读入蛋蛋第1步走的格子，start变成为蛋蛋第1步走的格子。
然后类似做就可以了。
#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，但不适用于pojusing 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-;
inline int sgn(DB x){if(abs(x)<EPS)return ;return(x>)?:-;}
const DB Pi=acos(-1.0);inline int gint()
{
int res=;bool neg=;char z;
for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar());
if(z==EOF)return ;
if(z=='-'){neg=;z=getchar();}
for(;z!=EOF && isdigit(z);res=res*+z-'',z=getchar());
return (neg)?-res:res;
}
inline LL gll()
{
LL res=;bool neg=;char z;
for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar());
if(z==EOF)return ;
if(z=='-'){neg=;z=getchar();}
for(;z!=EOF && isdigit(z);res=res*+z-'',z=getchar());
return (neg)?-res:res;
}const int maxN=;
const int dx[]={,,-,};
const int dy[]={,-,,};
const int maxcnt=maxN*maxN;
const int maxK=;int N,M,K;
char mp[maxN+][maxN+];
int idx[maxN+][maxN+],cntB,cntW;
int x,y;int now,first[maxcnt+];
struct Tedge{int v,next;}edge[maxcnt*+];
inline void addedge(int u,int v){now++;edge[now].v=v;edge[now].next=first[u];first[u]=now;}int maxmatching;
int form[maxcnt+],flag[maxcnt+];int vis[maxcnt+];
inline int find(int u)
{
int i,v;
vis[u]=;
for(i=first[u],v=edge[i].v;i!=-;i=edge[i].next,v=edge[i].v)
if(flag[v]== && (form[v]== || (vis[form[v]]== && find(form[v]))))
{
form[u]=v;form[v]=u;
return ;
}
return ;
}
inline int check(int u)
{
int i;
re(i,,cntB+cntW)vis[i]=;
return find(u);
}inline void disuse(int u)
{
if(form[u]==)return;
int v=form[u];
form[u]=form[v]=;
maxmatching--;
flag[u]=;
if(check(v))maxmatching++;
}
inline void use(int u)
{
flag[u]=;
if(check(u))maxmatching++;
}inline void cover(int u,int v)
{
if(form[u]==v){flag[u]=flag[v]=;return;}
int f=,g=;
if(form[u]!=)g=form[u],form[g]=form[u]=,maxmatching--;
if(form[v]!=)f=form[v],form[f]=form[v]=,maxmatching--;
form[u]=v;form[v]=u;
flag[u]=flag[v]=;
maxmatching++;
if(f && check(f))maxmatching++;
if(g && check(g))maxmatching++;
}int tot,out[maxK+];int main()
{
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
int i,j,k;
N=gint();M=gint();
re(i,,N)scanf("%s\n",mp[i]+);
re(i,,N)re(j,,M)
{
if(mp[i][j]=='O')idx[i][j]=++cntW;else idx[i][j]=++cntB;
if(mp[i][j]=='.')mp[i][j]='X',x=i,y=j;
}
re(i,,N)re(j,,M)if(mp[i][j]=='O')idx[i][j]+=cntB;
now=-;mmst(first,-);
re(i,,N)re(j,,M)if(mp[i][j]=='X')re(k,,)
{
int x=i+dx[k],y=j+dy[k];
if(x< || N<x || y< || M<y) continue;
if(mp[x][y]=='O')addedge(idx[i][j],idx[x][y]),addedge(idx[x][y],idx[i][j]);
} re(i,,cntB)if(check(i))maxmatching++; K=gint();
re(i,,K)
{
int tx=gint(),ty=gint(),u=idx[x][y],v=idx[tx][ty];
disuse(u);
int res1=maxmatching;
use(u);
int res2=maxmatching;
cover(u,v);
if(res1!=res2)
{
int f=,t;
for(j=first[v],t=edge[j].v;j!=-;j=edge[j].next,t=edge[j].v)
if(flag[t]== && form[t]==){f=;break;}
if(!f)
{
int res3=maxmatching;
for(j=first[v],t=edge[j].v;j!=-;j=edge[j].next,t=edge[j].v)if(flag[t]==)
{
disuse(t);
int res4=maxmatching;
use(t);
if(res4==res3){f=;break;}
}
}
if(f)out[++tot]=i;
}
x=gint();y=gint();
}
PF("%d\n",tot);
re(i,,tot)PF("%d\n",out[i]);
return ;
}
