Steven_MengのBlog

洛谷

GDOI

发现$d \le 8$,这仿佛在提示我们要暴力枚举$x$代表的是什么,注意到$b,c$和$a,c$就可以覆盖到$x$的所有情况,所以我们只要枚举$x$是$A$或$B$即可,时间复杂度$2^d$,我们把枚举出来的地图序列叫做$Map$

考虑这样编号,$A$对应$[1,n]$,$B$对应$[n+1,2 \times n]$,$C$对应$[2 \times n +1 , 3*n]$

但是这样太过愚蠢,我们知道$Map$是什么,所以一个位置不能放什么我们是知道的,不妨这样编号:

$Map[i]==A$,不能放$A$,那么只能放$B,C$,$B -> [1,n],C -> [n+1,2 \times n]$

$Map[i]==B$,不能放$B$,那么只能放$A,C$,$A -> [1,n],C -> [n+1,2 \times n]$

$Map[i]==C$,不能放$C$,那么只能放$A,B$,$A -> [1,n],B -> [n+1,2 \times n]$

简单来说,就是按照字典序编号。

如图:

接下来分类讨论即可。

我们设$i$代表的序列为$a[i]$,$j$代表的序列为$a[j]$,$h_i=f1[i],h_j=f2[j]$

1.$f1[i]==Map[a[i]]$

这就是告诉我们不能选$f1[i]$,否则选了就挂了,直接continue掉。

1
2
3
if (f1[i]==Map[a[i]]){//一旦选了就挂了
continue;
}

2.$f2[i]==Map[b[i]]$

这也是告诉我们不能选$f1[i]$,但是我们可以选其他的,整理一下思路,发现$Map[a[i]]$不能选$f1[i]$不能选,根据上面我们的特判,发现$Map[a[i]]!=f1[i]$,所以只有一个字母能选。

如何建一个图,强制选剩下的那个字母,这里我们使用奇巧淫技,假设第一列选了$B$第三列就必须选$C$,现在我们知道第一列只能选$C$,就连一条$B->C$,这样你选了$B$就必须选$C$,造成矛盾,等于是强制选了$C$

1
2
3
4
5
else if (f2[i]==Map[b[i]]){//也是选了就挂了,但是有一种可以的选择
//eg. a[i]=='B' Map[f1[i]]=='A' so 只能选'C'
int delta=GetDelta1(i);
AddEdge(a[i]+delta,a[i]+n-delta);
}

3.$else$

这是最普通的情况,假设第一列选了$B$第三列就必须选$B$,按照$2-SAT$的问题的套路,我们要寻找有依赖性关系的点对,显然,选了第一列的$B$,就必须选第三列的$B$,还有,选了第三列的$A$,就必须选第一列的$C$,否则会发生矛盾,于是他们两个点对连边:

1
2
3
int delta1=GetDelta1(i),delta2=GetDelta2(i);
AddEdge(a[i]+delta1,b[i]+delta2);
AddEdge(b[i]+n-delta2,a[i]+n-delta1);

代码写的比较丑陋,其中一些细节模拟一下就知道了。

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
137
138
139
140
141
142
143
144
145
#include <bits/stdc++.h>
#define MAXN 2000005
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
vector<int>G[MAXN];
inline void AddEdge(int u,int v){
G[u].push_back(v);
}
int dfn[MAXN],low[MAXN],cnt;
stack<int>stk;
int scc,col[MAXN];
void tarjan(int u){
dfn[u]=low[u]=++cnt;
stk.push(u);
for (register int i=0;i<G[u].size();++i){
int v=G[u][i];
if (!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
else if (!col[v]) low[u]=min(low[u],dfn[v]);
}
if (low[u]==dfn[u]){
++scc;
do{
col[u]=scc;
u=stk.top(),stk.pop();
}while (low[u]!=dfn[u]);
}
}
inline char GetPre(char ch){
if (ch=='A') return 'B';
if (ch=='B') return 'A';
if (ch=='C') return 'A';
}
inline char GetNex(char ch){
if (ch=='A') return 'C';
if (ch=='B') return 'C';
if (ch=='C') return 'B';
}
inline char gc(){
char ch=getchar();
while (!isalpha(ch)) ch=getchar();
if (ch>='a'&&ch<='z') return ch-'a'+'A';
else return ch;
}
char Map[MAXN],ans[MAXN];
int a[MAXN],b[MAXN];
char f1[MAXN],f2[MAXN];
int pos[MAXN];//存的是x的下标
int n,m,d;
inline void Init(){
while (stk.size()) stk.pop();
memset(col,0,sizeof(col));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
scc=cnt=0;
for (register int i=0;i<MAXN;++i){
G[i].clear();
}
}
inline void GetAns(){
bool flag=true;
for (register int i=1;i<=n*2;++i){
if (!dfn[i]) tarjan(i);
}
for (register int i=1;i<=n;++i){
if (col[i]==col[i+n]){
flag=false;
break;
}
if (col[i]<col[i+n]) ans[i-1]=GetPre(Map[i]);
else ans[i-1]=GetNex(Map[i]);
}
if (flag==true){
cout<<ans;
exit(0);
}
}
inline int GetDelta1(int pos){
//写成注释里这样可能方便理解
// if (Map[a[pos]]=='A'&&f1[pos]=='B') return 0;
// if (Map[a[pos]]=='A'&&f1[pos]=='C') return n;
// if (Map[a[pos]]=='B'&&f1[pos]=='A') return 0;
// if (Map[a[pos]]=='B'&&f1[pos]=='C') return n;
// if (Map[a[pos]]=='C'&&f1[pos]=='A') return 0;
// if (Map[a[pos]]=='C'&&f1[pos]=='B') return n;
return (f1[pos]=='A'||(f1[pos]=='B'&&Map[a[pos]]=='A'))?0:n;
}
inline int GetDelta2(int pos){
// if (Map[b[pos]]=='A'&&f2[pos]=='B') return 0;
// if (Map[b[pos]]=='A'&&f2[pos]=='C') return n;
// if (Map[b[pos]]=='B'&&f2[pos]=='A') return 0;
// if (Map[b[pos]]=='B'&&f2[pos]=='C') return n;
// if (Map[b[pos]]=='C'&&f2[pos]=='A') return 0;
// if (Map[b[pos]]=='C'&&f2[pos]=='B') return n;
return (f2[pos]=='A'||(f2[pos]=='B'&&Map[b[pos]]=='A'))?0:n;
}
int main(){
n=read(),d=read();
int c=0;
scanf("%s",Map+1);
for (register int i=1;i<=n;++i){
Map[i]-='a',Map[i]+='A';
if (Map[i]=='X') pos[++c]=i;
}
m=read();
for (register int i=1;i<=m;++i){
a[i]=read(),f1[i]=getchar(),b[i]=read(),f2[i]=getchar();
getchar();
}
for (register int v=0;v<(1<<d);++v){
Init();
for (register int i=1;i<=d;++i){
if (v&(1<<(i-1))) Map[pos[i]]='A';
else Map[pos[i]]='B';
}
for (register int i=1;i<=m;++i){
if (f1[i]==Map[a[i]]){//一旦选了就挂了
continue;
}
else if (f2[i]==Map[b[i]]){//也是选了就挂了,但是有一种可以的选择
//eg. a[i]=='A' Map[f1[i]]=='B' so 只能选'C'
int delta=GetDelta1(i);
AddEdge(a[i]+delta,a[i]+n-delta);
}
else {
int delta1=GetDelta1(i),delta2=GetDelta2(i);
AddEdge(a[i]+delta1,b[i]+delta2);
AddEdge(b[i]+n-delta2,a[i]+n-delta1);
}
}
GetAns();
}
puts("-1");
}

 评论