「NOI2017」游戏

发表于 | 分类于 | | 浏览量： 次

2-SAT裸题？有点难写qwq。

传送门

洛谷P3825

BZOJ4945

题解

如果只有a、b、c三种地图，由于只有两种赛车选择，所以是裸的2-SAT问题。

但是有x地图。

不过数量并不多，最多只有$8$张。

所以可以暴力枚举这$d$张x地图用什么车，然后再套2-SAT。时间复杂度为$O((n+m)*3^d)$。

这样复杂度太高了，并不容易过。

然后不难发现，对于一张地图，不选A和不选B这两种方案中其实已近包含了所有可能。

所以复杂度就可以降到$O((n+m)*2^d)$，可以过了。

代码

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100005,maxm=200005;
int n,d,m,len,X[10],tot,lnk[maxn],son[maxm],nxt[maxm],idx,top,cnt,dfn[maxn],low[maxn],stack[maxn],id[maxn];bool vis[maxn];char S[maxn];
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
inline char GetChar()
{
	char ch=getchar();
	while(!isalpha(ch)) ch=getchar();
	return ch;
}
inline void add_e(int x,int y){tot++;son[tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;}
inline void del(int x){lnk[x]=nxt[tot];nxt[tot]=0;son[tot]=0;tot--;}
inline void NoSolution(){printf("-1");exit(0);}
struct Claim
{
	int i,j;char hi,hj;
	bool operator < (const Claim& b)const{return (S[i]!='x'&&S[j]!='x')<(S[b.i]!='x'&&S[b.j]!='x');}
}C[maxn],T[maxn];
inline int GetID(int x,char Car)
{
	int flg=0;
	for(char i='A';i<='C';i++)
	{
		if(i==Car) return x+flg*n;
		if(S[x]!=i+'a'-'A') flg=1;
	}
}
inline void PutChar(int x,int id)
{
	for(char i='A';i<='C';i++)
	{
		if(S[x]!=i+'a'-'A')
		{
			if(!id){putchar(i);return;}
			id--;
		}
	}
}
inline char GetAn(int x,char Car){for(int i='A';i<='C';i++)if(i+'a'-'A'!=S[x]&&i!=Car)return i;} 
inline int Pair(int x){return x>n?x-n:x+n;}
void Tarjan(int now)
{
	dfn[now]=low[now]=++idx;
	vis[now]=true;stack[++top]=now;
	for(int i=lnk[now];i;i=nxt[i])
	{
		if(!dfn[son[i]])
		{
			Tarjan(son[i]);
			if(low[son[i]]<low[now]) low[now]=low[son[i]];
		}
		else if(vis[son[i]]&&dfn[son[i]]<low[now]) low[now]=dfn[son[i]];
	}
	if(dfn[now]==low[now])
	{
		cnt++;
		do
		{
			id[stack[top]]=cnt;
			vis[stack[top]]=false;top--;
		}while(stack[top+1]!=now);
	}
}
inline void Solve()
{
	int leng=len;
	for(int i=1,j=1;i<=leng&&j<=len;i++,j++)
	{
		C[i]=T[j];
		if((C[i].i==C[i].j&&C[i].hi==C[i].hj)||(S[C[i].i]==C[i].hi+'a'-'A')){i--;leng--;continue;}
		if(S[C[i].j]==C[i].hj+'a'-'A'){C[i].j=C[i].i;C[i].hj=GetAn(C[i].i,C[i].hi);}
	}
	idx=cnt=0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));
	for(int i=1;i<=leng;i++)
	{
		add_e(GetID(C[i].i,C[i].hi),GetID(C[i].j,C[i].hj));
		add_e(Pair(GetID(C[i].j,C[i].hj)),Pair(GetID(C[i].i,C[i].hi)));
	}
	for(int i=1;i<=2*n;i++) if(!dfn[i]) Tarjan(i);
	for(int i=1;i<=n;i++)
	{
		if(id[i]==id[i+n])
		{
			for(int j=leng;j;j--)
				{del(Pair(GetID(C[j].j,C[j].hj)));del(GetID(C[j].i,C[j].hi));}
			return;
		}
	}
	for(int i=1;i<=n;i++) PutChar(i,id[i]>id[i+n]);
	exit(0);
}
void DFS(int step)
{
	if(step>d){Solve();return;}
	S[X[step]]='a';DFS(step+1);
	S[X[step]]='b';DFS(step+1);
}
int main()
{
	n=read();read();
	for(int i=1;i<=n;i++)
	{
		S[i]=GetChar();
		if(S[i]=='x') X[++d]=i;
	}
	m=read();
	for(int i=1;i<=m;i++)
	{
		C[i].i=read();C[i].hi=GetChar();
		C[i].j=read();C[i].hj=GetChar();
		if((C[i].i==C[i].j&&C[i].hi==C[i].hj)||(S[C[i].i]==C[i].hi+'a'-'A')){i--;m--;continue;}
		if(S[C[i].j]==C[i].hj+'a'-'A'){C[i].j=C[i].i;C[i].hj=GetAn(C[i].i,C[i].hi);}
	}
	sort(C+1,C+1+m);
	while(S[C[len+1].i]=='x'||S[C[len+1].j]=='x') len++;
	for(int i=len+1;i<=m;i++)
	{
		add_e(GetID(C[i].i,C[i].hi),GetID(C[i].j,C[i].hj));
		add_e(Pair(GetID(C[i].j,C[i].hj)),Pair(GetID(C[i].i,C[i].hi)));
	}
	memcpy(T,C,sizeof(Claim)*(len+1));
	DFS(1);
	NoSolution();
	return 0;
}