题目描述
小 L 计划进行 $n$ 场游戏，每场游戏使用一张地图，小 L 会选择一辆车在该地图上完成游戏。
小 L 的赛车有三辆，分别用大写字母 $A$、$B$、$C$ 表示。地图一共有四种，分别用小写字母 $x$、$a$、$b$、$c$ 表示。
其中，赛车 $A$ 不适合在地图 $a$ 上使用，赛车 $B$ 不适合在地图 $b$ 上使用，赛车 $C$ 不适合在地图 $c$ 上使用，而地图 $x$ 则适合所有赛车参加。
适合所有赛车参加的地图并不多见，最多只会有 $d$ 张。
$n$ 场游戏的地图可以用一个小写字母组成的字符串描述。例如：$S=\texttt{xaabxcbc}$ 表示小L计划进行 $8$ 场游戏，其中第 $1$ 场和第 $5$ 场的地图类型是 $x$，适合所有赛车，第 $2$场和第 $3$ 场的地图是 $a$，不适合赛车 $A$，第 $4$ 场和第 $7$ 场的地图是 $b$，不适合赛车 $B$，第 $6$ 场和第 $8$ 场的地图是 $c$，不适合赛车 $C$。
小 L 对游戏有一些特殊的要求，这些要求可以用四元组 $ (i, h_i, j, h_j) $ 来描述，表示若在第 $i$ 场使用型号为 $h_i$ 的车子，则第 $j$ 场游戏要使用型号为 $h_j$ 的车子。
你能帮小 L 选择每场游戏使用的赛车吗？如果有多种方案，输出任意一种方案。
如果无解，输出 -1。
输入格式
输入第一行包含两个非负整数 $n$, $d$。
输入第二行为一个字符串 $S$。
$n$, $d$, $S$ 的含义见题目描述，其中 $S$ 包含 $n$ 个字符，且其中恰好 $d$ 个为小写字母 $x$。
输入第三行为一个正整数 $m$ ，表示有 $m$ 条用车规则。
接下来 $m$ 行，每行包含一个四元组 $i,h_i,j,h_j$ ，其中 $i,j$ 为整数，$h_i,h_j$ 为字符 $A$ 、$B$ 或 $C$，含义见题目描述。
输出格式
输出一行。
若无解输出 -1。
样例
样例输入
样例输出
小 $L$ 计划进行 $3$ 场游戏，其中第 $1$ 场的地图类型是 $x$，适合所有赛车，第 $2$ 场和第 $3$ 场的地图是 $c$，不适合赛车 $C$。
小 $L$ 希望：若第 $1$ 场游戏使用赛车 $A$，则第 $2$ 场游戏使用赛车 $B$。
那么为这 $3$ 场游戏分别安排赛车 $A$、$B$、$A$ 可以满足所有条件。
若依次为 $3$ 场游戏安排赛车为 $BBB$ 或 $BAA$ 时，也可以满足所有条件，也被视为正确答案。
但依次安排赛车为 $AAB$ 或 $ABC$ 时，因为不能满足所有条件，所以不被视为正确答案。
数据范围与提示
题解
2-SAT
上来看这到题。
感到 $a,b,c$ 的时候很好搞， 但是不知道 $x$ 怎么办。
$a, b, c$ 的时候是2-SAT， 那 $x$ 不就是 3-SAT 了么。
这是NPC问题啊。
之后看来一下数据范围， $x \le 8$ 发现 $x$ 可以枚举。 然后就是一个裸的2-SAT了。
2-SAT 输出方案
Tarjan
Tarjan缩点时会给联通块编号
对于一对相互对立的问题，谁的新编号小就选谁。
简单清真， 不用去跑什么 反图+拓扑排序 了。
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
| #pragma GCC optimize("O3")
#include <bits/stdc++.h>
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 * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
const int MAXN = 50005;
const int MAXM = 100005;
struct data {
int i, hi, j, hj;
} D[MAXM];
struct edge {
int END, next;
} v[MAXM << 2];
int first[MAXN << 1], p;
void add(int a, int b) {
v[p].END = b;
v[p].next = first[a];
first[a] = p++;
}
char tmp[2][5];
char S[MAXN];
int id[10];
int ID(int x, int y) {
if (S[x] - 'a' == y) return 0;
if (S[x] == 'a') return x * 2 + y - 1;
else if (S[x] == 'b') return x * 2 + y / 2;
else return x * 2 + y;
}
int dfn[MAXN << 1], low[MAXN << 1], Index, belong[MAXN << 1], T;
bool vis[MAXN << 1];
int st[MAXN << 1], top;
void Tarjan(int rt) {
dfn[rt] = low[rt] = ++Index;
st[++top] = rt;
vis[rt] = 1;
for (int i = first[rt]; i != -1; i = v[i].next) {
if (!dfn[v[i].END]) {
Tarjan(v[i].END);
low[rt] = min(low[rt], low[v[i].END]);
} else if (vis[v[i].END])
low[rt] = min(low[rt], dfn[v[i].END]);
}
if (low[rt] == dfn[rt]) {
T++;
int x;
do {
x = st[top--];
vis[x] = 0;
belong[x] = T;
} while (low[x] != dfn[x]);
}
}
bool Calc(int n, int m) {
memset(first, -1, sizeof(first)), p = 0;
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
memset(belong, 0, sizeof(belong));
T = Index = 0;
for (int i = 1; i <= m; ++i) {
int t1 = ID(D[i].i, D[i].hi);
int t2 = ID(D[i].j, D[i].hj);
if (t1) {
if (t2) add(t1, t2), add(t2 ^ 1, t1 ^ 1);
else add(t1, t1 ^ 1);
}
}
for (int i = 2; i <= 2 * n + 1; ++i) {
if (!dfn[i]) Tarjan(i);
if (i & 1) {
if (belong[i] == belong[i - 1]) return 0;
}
}
for (int i = 1; i <= n; ++i) {
if (belong[2 * i] < belong[2 * i + 1]) {
if (S[i] == 'a') printf("B");
if (S[i] == 'b') printf("A");
if (S[i] == 'c') printf("A");
} else {
if (S[i] == 'a') printf("C");
if (S[i] == 'b') printf("C");
if (S[i] == 'c') printf("B");
}
}
printf("\n");
return 1;
}
int main() {
int n = read(), d = read();
scanf("%s", S + 1);
int x = 0;
int m = read();
for (int i = 1; i <= m; ++i) {
scanf("%d%s%d%s", &D[i].i, tmp[0], &D[i].j, tmp[1]);
D[i].hi = tmp[0][0] - 'A';
D[i].hj = tmp[1][0] - 'A';
}
for (int i = 1; i <= n; ++i)
if (S[i] == 'x') id[++x] = i;
int N = (1 << d) + 1;
for (int i = 0; i <= N; ++i) {
for (int j = 1; j <= x; ++j)
if (i & (1 << (j - 1))) S[id[j]] = 'a';
else S[id[j]] = 'b';
if (Calc(n, m)) return 0;
}
return printf("-1\n"), 0;
}
|
