「LOJ 2305」「NOI2017」游戏

发表于

小 L 计划进行 nn 场游戏，每场游戏使用一张地图，小 L 会选择一辆车在该地图上完成游戏。

小 L 的赛车有三辆，分别用大写字母 AA、BB、CC 表示。地图一共有四种，分别用小写字母 xx、aa、bb、cc 表示。

其中，赛车 AA 不适合在地图 aa 上使用，赛车 BB 不适合在地图 bb 上使用，赛车 CC 不适合在地图 cc 上使用，而地图 xx 则适合所有赛车参加。适合所有赛车参加的地图并不多见，最多只会有 dd 张。

nn 场游戏的地图可以用一个小写字母组成的字符串描述。

小 L 对游戏有一些特殊的要求，这些要求可以用四元组 (i,hi,j,hj)(i, h_i, j, h_j) 来描述，表示若在第 ii 场使用型号为 hih_i 的车子，则第 jj 场游戏要使用型号为 hjh_j 的车子。

你能帮小 L 选择每场游戏使用的赛车吗？如果有多种方案，输出任意一种方案。如果无解，输出 −1-1 。

Constraints

n≤50000n\leq 50000 ， m≤100000m\leq 100000 ， d≤8d \leq 8

Solution

据题意显然需要为 2-SAT 。因为 xx 的地图适合三种赛车，且最多只有 88 张，所以我们可以通过枚举每张 xx 的地图为 aa 或 bb 来将问题转化为 2-SAT 的裸题。

对于一条限制，点 ii 代表第 ii 场选择了赛车 hih_i ，点 i′i' 代表不选择赛车 hih_i ，点 jj 与点 j′j' 同理。具体连边方式为：若第 ii 场无法使用 hih_i ，直接跳过；若第 jj 场无法使用 hjh_j ，则连边 ii 到 i′i' ，代表一旦选择 ii 则无解；否则连边 ii 到 jj ， j′j' 到 i′i' 。

建完图以后 tarjan 缩点，判断是否有可行方案。输出方案时输出强连通分量编号较小的一个即可。

时间复杂度 O(m⋅2d)O(m\cdot 2^d) 。

Code

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
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define LL long long
using namespace std;
const int N=2e5+5;
int n,d,m,cnt,tim,color,top,pos[10];
int first[N],ci[N],hi[N],cj[N],hj[N];
int s[N],low[N],dfn[N],sta[N],c[N];
bool vis[N];
char ch[N];
struct edge{int to,next;}e[N*2];
int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
int get()
{
	char c=getchar();
	while(c<'A'||c>'C')c=getchar();
	return c-'A';
}
void ins(int u,int v){e[++cnt]=(edge){v,first[u]};first[u]=cnt;}
void tarjan(int x)
{
	low[x]=dfn[x]=++tim;
	sta[++top]=x;vis[x]=true;
	for(int i=first[x];i;i=e[i].next)
	{
		int to=e[i].to;
		if(!dfn[to])tarjan(to),low[x]=min(low[x],low[to]);
		else if(vis[to])low[x]=min(low[x],dfn[to]);
	}
	if(low[x]==dfn[x])
	{
		color++;
		while(sta[top]!=x)vis[sta[top]]=false,c[sta[top--]]=color;
		vis[x]=false;c[x]=color;top--;
	}
}
int id(int x,int c)
{
	if(!s[x])return c==1?x:x+n;
	else return c==0?x:x+n;
}
int xo(int x){return x>n?x-n:x+n;}
bool solve(int state)
{
	cnt=tim=color=top=0;
	memset(c,0,sizeof(c));
	memset(vis,0,sizeof(vis));
	memset(low,0,sizeof(low));
	memset(dfn,0,sizeof(dfn));
	memset(first,0,sizeof(first));
	for(int i=0;i<d;i++)
		if(state&(1<<i))s[pos[i+1]]=0;
		else s[pos[i+1]]=1;
	for(int i=1;i<=m;i++)
	{
		if(hi[i]==s[ci[i]])continue;
		int x=id(ci[i],hi[i]),y=id(cj[i],hj[i]);
		if(hj[i]==s[cj[i]]){ins(x,xo(x));continue;}
		ins(x,y);ins(xo(y),xo(x));
	}
	for(int i=1;i<=n*2;i++)
		if(!dfn[i])tarjan(i);
	for(int i=1;i<=n;i++)
		if(c[i]==c[n+i])return false;
	for(int i=1;i<=n;i++)
		if(c[i]<c[i+n])
		{
			if(!s[i])putchar('B');
			else putchar('A');
		}
		else
		{
			if(s[i]==2)putchar('B');
			else putchar('C');
		}
	return true;
}
int main()
{
	n=read();read();
	scanf("%s",ch+1);m=read();
	for(int i=1;i<=n;i++)
	{
		s[i]=ch[i]-'a';
		if(ch[i]=='x')pos[++d]=i;
	}
	for(int i=1;i<=m;i++)
		ci[i]=read(),hi[i]=get(),
		cj[i]=read(),hj[i]=get();
	for(int i=0;i<(1<<d);i++)
		if(solve(i))return 0;
	printf("-1");
	return 0;
}