题目大意
有一个长度为 $n$ 的字符串 $S$（包含 a，b，c，x）和 $m$ 组限制关系，要求构造一个只包含 A，B，C 的字符串 $T$，满足 $S_i \neq \text{lowercase}(T_i)$ 以及所有的限制关系。一组限制形如：如果 $T_{u_j} = a_j$，则 $T_{v_j} = b_j$。
数据范围：$n \le 5 \times 10^4, m \le 10^5$，x 的个数 $d$ 不会超过 $8$。
思路分析
首先考虑没有 x 怎么做。发现每个位置最多只能取两种字符，还有一些额外的限制。容易想到 2 - SAT 模型。具体地，我们对于每个位置能取的字符建两个点，然后连边时需要分类讨论：
- 如果 $u_j$ 不可能取 $a_j$，则这组限制无效。
- 如果 $u_j$ 可能取 $a_j$ 且 $v_j$ 不可能取 $b_j$，则 $u_j$ 不能够取 $a_j$。连边 $(u_j, a_j) \rightarrow (u_j, a’_j)$。
- 如果 $u_j$ 可能取 $a_j$ 且 $v_j$ 可能取 $b_j$，则连边 $(u_j, a_j) \rightarrow (v_j, b’_j)$，$(v_j, b_j) \rightarrow (u_j, a’_j)$。注意 2 - SAT 大部分情况下是一个对称的结构，很多限制都是要连对称的边的，原因是若一个命题成立那么它的逆否命题也是成立的。
接下来，我们跑 2 - SAT 算法即可。注意 2 - SAT 输出方案时要取两个结点所在 SCC 标号较小的那个。
这样，我们已经可以获得 $45$ 分的好成绩。
接下来考虑加入 x。发现 x 的数量很小，我们可以枚举该位置是什么字符。这样的时间复杂度是 $O(3^d \times (n + m))$ 的，不能通过本题。
但是我们可以将它转化成没有 x 的情况。每次枚举 $S_i$ 是 a 还是 b 即可覆盖所有的情况。这样的时间复杂度是 $O(2^d \times (n + m))$ 的，可以通过本题的的数据，但是因为常数大会在 UOJ 上被卡成 $97$ 分。
考虑随机 $S_i$ 是 a，b 还是 c。假设只有一种合法的解，那么每次猜中的概率是 $\left( \frac{2}{3} \right)^8 \approx 0.03901844231$，那么猜 $100$ 次猜错的概率是 $(1 - 0.03901844231) ^ {100} \approx 0.018685525458$，那么在 $20$ 个测试点的题目中全对的概率就是 $(1 - 0.018685525458) ^ {20} \approx 0.6857472838 \approx 68.57 \%$，脸白就可以过了。时间复杂度 $O(100 \times (n + m))$。
代码实现
第一次 AC 就是 UOJ 最短代码耶！
1 | |
2 | |
3 | |
4 | using namespace std; |
5 | |
6 | const int maxn = 1e5, maxm = 2e5; |
7 | int n, d, m, u[maxm + 3], v[maxm + 3], p[maxn + 3], id[maxn + 3][3]; |
8 | int tm, dfn[maxn + 3], low[maxn + 3], top, st[maxn + 3], cnt, bel[maxn + 3]; |
9 | char s[maxn + 3], a[maxm + 3], b[maxm + 3], t[maxn + 3]; |
10 | bool in[maxn + 3]; |
11 | vector<int> G[maxn + 3]; |
12 | |
13 | void tarjan(int u) { |
14 | dfn[u] = low[u] = ++tm; |
15 | st[++top] = u, in[u] = true; |
16 | for (int i = 0, v; i < G[u].size(); i++) { |
17 | v = G[u][i]; |
18 | if (!dfn[v]) { |
19 | tarjan(v); |
20 | low[u] = min(low[u], low[v]); |
21 | } else if (in[v]) { |
22 | low[u] = min(low[u], dfn[v]); |
23 | } |
24 | } |
25 | if (dfn[u] == low[u]) { |
26 | ++cnt; |
27 | do { |
28 | bel[st[top]] = cnt; |
29 | in[st[top]] = false; |
30 | } while (st[top--] != u); |
31 | } |
32 | } |
33 | |
34 | bool solve() { |
35 | for (int i = 1; i <= n; i++) { |
36 | for (int j = 0; j < 3; j++) { |
37 | id[i][(s[i] - 'a' + j) % 3] = j; |
38 | } |
39 | } |
40 | for (int i = 1; i <= n * 2; i++) { |
41 | G[i].clear(), dfn[i] = 0; |
42 | } |
43 | for (int i = 1, x, y; i <= m; i++) { |
44 | x = id[u[i]][a[i] - 'A'], y = id[v[i]][b[i] - 'A']; |
45 | if (x && !y) { |
46 | G[u[i] + (x - 1) * n].push_back(u[i] + (2 - x) * n); |
47 | } else if (x) { |
48 | G[u[i] + (x - 1) * n].push_back(v[i] + (y - 1) * n); |
49 | G[v[i] + (2 - y) * n].push_back(u[i] + (2 - x) * n); |
50 | } |
51 | } |
52 | tm = cnt = 0; |
53 | for (int i = 1; i <= n * 2; i++) { |
54 | if (!dfn[i]) tarjan(i); |
55 | } |
56 | for (int i = 1; i <= n; i++) { |
57 | if (bel[i] == bel[i + n]) { |
58 | return false; |
59 | } else if (bel[i] < bel[i + n]) { |
60 | t[i] = (s[i] - 'a' + 1) % 3 + 'A'; |
61 | } else { |
62 | t[i] = (s[i] - 'a' + 2) % 3 + 'A'; |
63 | } |
64 | } |
65 | return true; |
66 | } |
67 | |
68 | int main() { |
69 | srand(19260817); |
70 | scanf("%d %*d %s %d", &n, s + 1, &m); |
71 | for (int i = 1; i <= m; i++) { |
72 | scanf("%d %c %d %c", &u[i], &a[i], &v[i], &b[i]); |
73 | } |
74 | for (int i = 1; i <= n; i++) { |
75 | if (s[i] == 'x') p[++d] = i; |
76 | } |
77 | for (int k = 1; k <= 100; k++) { |
78 | for (int i = 1; i <= d; i++) { |
79 | s[p[i]] = rand() % 3 + 'a'; |
80 | } |
81 | if (solve()) { |
82 | printf("%s\n", t + 1); |
83 | return 0; |
84 | } |
85 | } |
86 | puts("-1"); |
87 | return 0; |
88 | } |
另外，附赠一个 checker！
1 | |
2 | |
3 | const int maxn = 1e5, maxm = 2e5; |
4 | int n, m, u[maxm + 3], v[maxm + 3], p[maxn + 3]; |
5 | char s[maxn + 3], a[maxm + 3], b[maxm + 3], t[maxn + 3]; |
6 | |
7 | int main() { |
8 | // freopen("game.in", "r", stdin); |
9 | scanf("%d %*d %s %d", &n, s + 1, &m); |
10 | for (int i = 1; i <= m; i++) { |
11 | scanf("%d %c %d %c", &u[i], &a[i], &v[i], &b[i]); |
12 | } |
13 | // freopen("game.out", "r", stdin); |
14 | scanf("%s", t + 1); |
15 | for (int i = 1; i <= n; i++) { |
16 | if (s[i] - t[i] == 'a' - 'A') { |
17 | printf("error: car unavailable in round #%d\n", i); |
18 | return 0; |
19 | } |
20 | } |
21 | for (int i = 1; i <= m; i++) { |
22 | if (t[u[i]] == a[i] && t[v[i]] != b[i]) { |
23 | printf("error: not satisfy limit #%d\n", i); |
24 | return 0; |
25 | } |
26 | } |
27 | puts("correct!"); |
28 | return 0; |
29 | } |