NOI2011 兔兔与蛋蛋游戏

wjh15101051's space

卧薪尝胆，厚积薄发。

NOI2011 兔兔与蛋蛋游戏

Date: Sat Mar 23 16:06:21 CST 2019

In Category: NoCategory

Description：

一个棋盘上有黑棋子和白棋子和一个空格， $A$ 可以把一个黑棋子移动到相邻的空格里去， $B$ 同理操作白棋子，给出二人的操作序列，求在 $A$ 哪一步操作的时候 $A$ 本来有必胜策略后来 $B$ 有必胜策略。

$1\leqslant n,m\leqslant 40$

Solution：

把移动棋子看成是空格在走，首先转移不会出现环，考虑一个移动序列： $$ a_1,a_2,\dots,a_{2n} $$ 假设他形成了循环，会发现 $a_1$ 和 $a_{2n}$ 应该是同一枚棋子，但是他被两个人动过了。

那么对于一个移动序列，会发现移动的棋子必然是黑 $-$ 白 $-$ 黑 $\cdots$ ，这让我们想到二分图的增广路，把黑色点和起点放在左边，白色点放在右边，那么 $A$ 一次操作就是把空格从左边移到右边， $B$ 相反，那么 $A$ 有必胜策略当且仅当形成了一个不能更长的有奇数条边的增广路，并且从 $A$ 出发所有路径最后都是长度为奇数的交替路，换句话说就是不能交换匹配边和非匹配边增加匹配，在换句话说就是这个点一定在最大匹配上。

那检查是否有最优决策就很容易了，我们把这个点删掉再检查是否能增广即可，注意每次操作之后要强行覆盖那一个匹配。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,m,q;

#define MAXN 50

int p[MAXN][MAXN];

char getc()

{

	register char c = getchar();

	while(c != 'X' && c != 'O' && c != '.')c = getchar();

	return c;

}

int id(int x,int y){return (x - 1) * m + y;}

struct edge

{

	int to,nxt;

}e[MAXN * MAXN * 4];

int edgenum = 0;

int lin[MAXN * MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	return;

}

int mx[4] = {0,0,1,-1};

int my[4] = {1,-1,0,0};

int match[MAXN * MAXN];

int vis[MAXN * MAXN],tim = 0;

int ban[MAXN * MAXN];

bool find(int k)

{

	if(ban[k])return false;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to] != tim && !ban[e[i].to])

		{

			vis[e[i].to] = tim;

			if(match[e[i].to] == -1 || find(match[e[i].to]))

			{

				match[e[i].to] = k;match[k] = e[i].to;

				return true;

			}

		}

	}

	return false;

}

int val[2010],ans[1010];

int stack[MAXN],top = 0;

int main()

{

	scanf("%d%d",&n,&m);

	int px,py;

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= m;++j)

		{

			char ch = getc();

			if(ch == 'X')p[i][j] = 1;

			if(ch == 'O')p[i][j] = 0;

			if(ch == '.')p[i][j] = 1,px = i,py = j;

		}

	}

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= m;++j)

		{

			for(int k = 0;k < 4;++k)

			{

				int nx = i + mx[k],ny = j + my[k];

				if(1 <= nx && nx <= n && 1 <= ny && ny <= m && (p[i][j] ^ p[nx][ny]))add(id(i,j),id(nx,ny));

			}

		}

	}

	memset(match,-1,sizeof(match));

	for(int i = 1;i <= n;++i)

		for(int j = 1;j <= m;++j)

			if(p[i][j]){++tim;find(id(i,j));}

	scanf("%d",&q);

	for(int i = 1;i <= 2 * q;++i)

	{

		int x = id(px,py);

		ban[x] = 1;

		if(match[x] != -1)

		{

			int y = match[x];

			match[x] = match[y] = -1;

			++tim;

			val[i] = !find(y);

		}

		px = rd();py = rd();

	}

	for(int i = 1;i <= q;++i)

	{

		if(val[2 * i - 1] && val[2 * i])ans[i] = 1;

	}

	for(int i = 1;i <= q;++i)if(ans[i])stack[++top] = i;

	cout << top << endl;

	for(int i = 1;i <= top;++i)printf("%d\n",stack[i]);

	cout << endl;

	return 0;

}

In tag: 图论-二分图博弈

wjh15101051