【NOI2011】兔兔与蛋蛋游戏

Source and Judge

NOI2011
luogu1971

Analysis

请先思考后再展开

仔细分析题意,发现就是移动空格。棋盘问题先染色一下(强制空格为黑色),
然后只有那些【棋子和格子颜色相同】的位置能去,而且一旦出去就被删除了。
那么其实就是一个二分图,多次加点并询问现在某个点是必胜还是必败
然后有个结论

接下来就很简单了,倒着加点判是否是关键点,应该匈牙利和网络流都行吧……
时间复杂度为 O(能过)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
typedef long long ll;
#define pr pair<int,int>
#define FR first
#define SE second
#define MP make_pair
const int MAX_N=41;
char mp[MAX_N][MAX_N];
int n,m;
inline bool okay(int x,int y) {return 0<=x and x<n and 0<=y and y<m;}
inline int calc(int x,int y){return x*m+y;}
int col[MAX_N*MAX_N];//1->black
const int dx[4]={0,0,-1,1};
const int dy[4]={-1,1,0,0};
int stx,sty;queue<pr> q;
bool vis[MAX_N][MAX_N];
void bfs()
{
q.push(MP(calc(stx,sty),1));vis[stx][sty]=1;
while(q.size())
{
pr x=q.front();q.pop();
col[calc(x.FR/m,x.FR%m)]=x.SE;
for(int i=0;i<4;i++)
{
int tx=x.FR/m+dx[i],ty=x.FR%m+dy[i];
if(!okay(tx,ty) or vis[tx][ty]) continue;
q.push(MP(calc(tx,ty),x.SE^1));vis[tx][ty]=1;
}
}
}
int ti=0,ask[MAX_N*MAX_N];
bool can[MAX_N*MAX_N];
int match[MAX_N*MAX_N];
bool findm(int x)
{
for(int i=0;i<4;i++)
{
int tx=x/m+dx[i],ty=x%m+dy[i],y=calc(tx,ty);
if(!okay(tx,ty) or !can[y] or ask[y]==ti) continue;
ask[y]=ti;
if(match[y]<0 or findm(match[y]))
{
match[x]=y;
match[y]=x;
return 1;
}
}
return 0;
}
vector<int> tmp;int f[2100];
vector<int> ans;
void main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
{
scanf("%s",mp[i]);
for(int j=0;j<m;j++) if(mp[i][j]=='.') stx=i,sty=j;
}
bfs();
for(int i=0;i<n;i++) for(int j=0;j<m;j++) can[calc(i,j)]=( col[calc(i,j)]==(mp[i][j]!='O') );
int q;scanf("%d",&q);pr now=MP(stx,sty);
for(int i=1;i<=q*2;i++)
{
int x,y;scanf("%d%d",&x,&y);x--;y--;
tmp.push_back(calc(now.FR,now.SE)),can[calc(now.FR,now.SE)]=0;
now=MP(x,y);
}
memset(match,-1,sizeof match);
int tt=0;for(int i=0;i<n*m;i++) if(can[i] and col[i] and match[i]<0) {ti++;tt+=findm(i);}
for(int t=(int)tmp.size()-1;t>=0;t--)
{
int tot=0;can[tmp[t]]=1;
for(int i=0;i<n*m;i++) if(can[i] and col[i] and match[i]<0) {ti++;tot+=findm(i);}
f[t]=tot;
}
for(int i=0;i<=q*2-2;i+=2) if(f[i]==1 and f[i+1]==1) ans.push_back(i/2);
printf("%d\n",ans.size());for(int t=0;t<(int)ans.size();t++) printf("%d\n",ans[t]+1);
}
};
int main()
{
srand(time(0));
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/9d0c.html
转载请注明出处,谢谢!