[NOI2017] 游戏

GitHub跳转原题关系图返回列表

把每场游戏的两种可用赛车建模成 2-SAT 布尔变量，用「禁 A / 禁 B」两种情形覆盖 x 地图的三种取值，2^d 次 Tarjan 判定。

OJ: luogu

题目 ID: P3825

难度:提高+/省选-

标签:2-SAT图论强连通分量枚举

创建: 2026-10-23 13:15

更新: 2026-10-23 15:28

形式化题目

有 $n$ 场游戏，第 $i$ 场使用一张地图 $S_i \in \{\texttt{a},\texttt{b},\texttt{c},\texttt{x}\}$ 。每场游戏选一辆赛车 $c_i \in \{\texttt{A},\texttt{B},\texttt{C}\}$ ，且满足：

地图 a 不允许赛车 A；地图 b 不允许 B；地图 c 不允许 C；地图 x 三种都允许。
恰有 $d$ 个位置满足 $S_i = \texttt{x}$ 。

再给定 $m$ 条蕴含约束 $(i, h_i, j, h_j)$ ：若 $c_i = h_i$ ，则必有 $c_j = h_j$ 。

求任意一组满足全部约束的赋值 $c_1, \dots, c_n$ ；若不存在则报告无解。答案不唯一，输出任意一组合法方案即可。

暴力解法

思路

最直接的做法就是"每场游戏挑一辆车"。因为每场最多 3 辆可选，直接递归枚举所有组合，凑齐 $n$ 场的方案后统一检查 $m$ 条规则即可。

一层递归负责一场游戏的选择：把这场的可用车辆逐个试过去，试完就进下一层。到第 $n+1$ 层时方案已完整，此时逐条检查规则，全部满足就记下第一组答案并停止搜索。

用样例 $S = \texttt{xcc}$ 、规则「第 1 场用 A 则第 2 场用 B」走一遍：

场次	地图	可用赛车
1	`x`	A、B、C
2	`c`	A、B
3	`c`	A、B

搜索树共 $3 \times 2 \times 2 = 12$ 个叶子。逐叶检查后，ABA、BAA、BBB、CBB 等都能通过；输出 ABA 或 BAA 都算正确。

这个做法显然正确——它遍历了全部合法赋值。但叶子的数量是 $3^{n}$ ： $n = 50$ 就已经到了 $7\times 10^{23}$ 量级，完全无法运行。

代码

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-23 13:26
 * update_at: 2026-10-23 13:26
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// brute.cpp：小数据暴力解，把「每场选哪辆车」看成选择序列来递归枚举所有可能。
// 只适合小数据：枚举量是 3^n，n 稍大就跑不动；不含任何 2-SAT 内容，
// 因此可以作为 main.cpp（2-SAT + 枚举）的独立交叉验证基线。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 15;      // 暴力只用于 n <= 8 的小数据（3^8 = 6561 个叶子）
const int MAXM = 105;     // 小数据的规则条数上界

int n, m;
char S[MAXN + 1];         // S[p]：第 p 场地图类型，1 下标
int forb[MAXN];           // forb[p]：该地图禁用的赛车（0=A,1=B,2=C），-1 表示 x 型不禁用

int rule_i[MAXM], rule_j[MAXM];   // 规则的两个位置
int rule_ci[MAXM], rule_cj[MAXM]; // 规则要求的赛车编号

int choose[MAXN];         // choose[p]：第 p 场枚举到的赛车
int first_answer[MAXN];   // 找到的第一组合法方案
bool found;

// 检查当前 choose[] 是否满足全部规则
bool check_rules() {
    for (int e = 1; e <= m; e++) {
        if (choose[rule_i[e]] != rule_ci[e]) {
            continue;  // 前提不成立，这条规则自动满足
        }
        if (choose[rule_j[e]] != rule_cj[e]) {
            return false;
        }
    }
    return true;
}

// 这一层在选择第 dep 场用哪辆车；三层分支对应 A、B、C。
void dfs_choose(int dep) {
    if (found) {
        return;
    }
    if (dep > n) {
        if (check_rules()) {
            found = true;
            for (int p = 1; p <= n; p++) {
                first_answer[p] = choose[p];
            }
        }
        return;
    }
    for (int car = 0; car <= 2; car++) {
        if (car == forb[dep]) {
            continue;  // 这张地图不适合该赛车
        }
        choose[dep] = car;
        dfs_choose(dep + 1);
        if (found) {
            return;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int d_ignored;
    cin >> n >> d_ignored;  // d 只用于限定 x 地图张数，暴力直接按 S 判断
    cin >> (S + 1);
    cin >> m;

    for (int p = 1; p <= n; p++) {
        forb[p] = (S[p] == 'x') ? -1 : S[p] - 'a';
    }

    for (int e = 1; e <= m; e++) {
        char hi, hj;
        cin >> rule_i[e] >> hi >> rule_j[e] >> hj;
        rule_ci[e] = hi - 'A';
        rule_cj[e] = hj - 'A';
    }

    found = false;
    dfs_choose(1);

    if (!found) {
        cout << -1 << '\n';
        return 0;
    }
    for (int p = 1; p <= n; p++) {
        cout << char('A' + first_answer[p]);
    }
    cout << '\n';

    return 0;
}

复杂度

时间 $O(3^n \cdot m)$ ，空间 $O(n + m)$ 。只适用于 $n$ 极小（ $n \leqslant 8$ ）的情形。

瓶颈

瓶颈非常明确：每场游戏有 3 个候选值，于是搜索树是 $3^n$ 。

要想把规模降下来，必须让每场游戏只有 2 个候选值——那样才有可能用"二选一的约束满足"类算法。问题是 x 地图确实有 3 个候选，不能简单地砍成 2 个。

这里需要换个角度：不要想着"帮算法选定车辆"，而是想着"给算法划定一个许可范围，让它自己在范围内挑"。

正解

思路

第一步：把"2 选 1"变成布尔变量

先看没有 x 地图的情形。地图 a 禁 A，可选车辆恰好是 $\{\texttt{B}, \texttt{C}\}$ 两辆；b、c 同理。于是每场游戏都能写成一个布尔变量。

按车辆编号 $\texttt{A}(0) < \texttt{B}(1) < \texttt{C}(2)$ 给两张可用车排个序：

地图	禁用车	第一辆可用	第二辆可用
`a`	A	B	C
`b`	B	A	C
`c`	C	A	B

定义布尔变量 $x_p$ ：

x_p = \begin{cases} 1 & \text{第 } p \text{ 场选第二辆可用车} \\ 0 & \text{第 } p \text{ 场选第一辆可用车} \end{cases}

于是每场游戏变成一个布尔变量，共 $2n$ 个 2-SAT 节点： $2(p-1)$ 代表 $x_p = 1$ ， $2(p-1)+1$ 代表 $x_p = 0$ 。

第二步：把规则写成蕴含

一条规则 $(i, h_i, j, h_j)$ 按 $h_i$ 、 $h_j$ 在该地图上可用与否分成三种情况：

$h_i$ 在地图 $i$ 上被禁用：前提永远不成立，规则对任何赋值都满足，不加任何边。
$h_j$ 在地图 $j$ 上被禁用：结论永远不成立，所以前提必须为假，即必须满足 $\lnot l_i$ 。在 2-SAT 里写成一条边 $l_i \to \lnot l_i$ 。
两边都可用：规则等价于 $l_i \to l_j$ 。同时加逆否边 $\lnot l_j \to \lnot l_i$ 。

这里 $l_i$ 表示"第 $i$ 场用赛车 $h_i$ "对应的文字。三种情况互斥且穷尽，建图完成后跑一遍 Tarjan 判定即可。

第三步：`x` 地图为什么只需枚举两种情形

x 地图有 3 个候选值，不能直接布尔化。最直觉的做法是枚举它到底用哪辆车，共 $3^d$ 种。

但关键在于：2-SAT 本身就是一个"自动选择器"。你不需要告诉它"这一场选 C"，你只需要告诉它"这一场不许选 A"，剩下的 B、C 就是 2 选 1，可以直接布尔化，让 2-SAT 自己在 B、C 里挑。

于是只需要两种"禁止"：

情形 0：禁 A，可选 $\{\texttt{B}, \texttt{C}\}$ ；
情形 1：禁 B，可选 $\{\texttt{A}, \texttt{C}\}$ 。

为什么两种就够？看覆盖表：

`x` 地图的真实取值	情形 0（禁 A）能找到吗	情形 1（禁 B）能找到吗
A	✗（A 被禁掉了）	✓
B	✓	✗（B 被禁掉了）
C	✓	✓

三种取值都被至少一种情形覆盖，所以枚举 $2^d$ 就够，不需要 $3^d$ 。

这里没有丢解，只是利用了 2-SAT 的"范围内自动求值"能力：一次判定能同时处理 2 个候选值，两种情形就是 $2 \times 2 = 4 \geqslant 3$ 个位置，天然覆盖了 3 个真实取值。

第四步：Tarjan 判定与取解

对每个 mask 建图后跑 Tarjan 求强连通分量：

若存在 $k$ 使 $2k$ 与 $2k+1$ 落在同一个强连通分量里，说明 $x_k$ 与 $\lnot x_k$ 互相可推，该情形无解，换下一个 mask。
否则取解。Tarjan 的分量编号顺序是"汇点侧先拿到小号"的逆拓扑序，所以按标准结论： $scc[2k] < scc[2k+1]$ 时取 $x_k = 1$ （选第二辆可用车），否则取第一辆。

实现上还有两个可做的剪枝：

静态边只建一次。不涉及 x 地图的规则每轮完全一样，先建好；每轮只追加涉及 x 地图的边，结束时精确还原。
不在规则里的 x 地图不枚举。它的取值不影响任何约束，固定成"禁 A"就行。设真正出现在规则里的 x 地图有 $d'$ 个，枚举量变成 $2^{d'} \leqslant 2^8$ 。

由于 $2n$ 可达 $10^5$ ，Tarjan 的 DFS 路径深度同样是 $10^5$ 量级，这里用显式栈而不是递归，避免爆栈。

代码

cpp

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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-23 13:25
 * update_at: 2026-10-23 13:42
 */
// 因规模必须改为迭代：Tarjan 的搜索路径深度可达 2n = 1e5，故用显式栈写法（参考 P3469）。
// 做法：2-SAT + 枚举每张 x 地图「禁用哪辆车」，2^d 次判定，d <= 8。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50005;          // n 的上界
const int MAXV = 2 * MAXN + 5;   // 2-SAT 节点数上界：每场游戏 2 个点
const int MAXM = 100005;         // m 的上界
const int MAXE = 2 * MAXM + 5;   // 每条规则最多产生 2 条蕴含边

int n, m;
char S[MAXN + 1];   // S[p]：第 p 场的地图类型（小写 a/b/c/x），1 下标
int forb[MAXN];     // forb[p]：第 p 场地图禁用的赛车编号（0=A,1=B,2=C）
int x_id[MAXN];     // x_id[p]：S[p]=='x' 时它是第几张 x 地图，否则 -1
int x_pos[10];      // x_pos[k]：第 k 张 x 地图对应的场次
int x_cnt;          // 扫描 S 得到的 x 地图张数
int enum_x[10];     // enum_x[k]：第 k 个需要枚举的 x 地图在 x_pos 中的下标
int enum_cnt;       // 需要枚举的 x 地图个数，共 2^enum_cnt 次判定
int d_declared;     // 题面第一行声明的 d，仅用于核对；实际张数以扫描 S 为准

// 规则：第 ri 场用赛车 rci，则第 rj 场必须用赛车 rcj
int ri[MAXM], rj[MAXM], rci[MAXM], rcj[MAXM];
int ri_fixed[MAXM];  // 静态规则（两端都不是 x 地图）在 ri 处的 2-SAT 文字，-1 表示该车不可用
int rj_fixed[MAXM];  // 静态规则在 rj 处的 2-SAT 文字，-1 表示该车不可用
int dyn_rule[MAXM];   // dyn_rule[]：涉及 x 地图的规则编号列表，每轮只需遍历这些
int dyn_cnt;          // dyn_rule 中的规则条数

// 链式前向星；节点 2k 表示「第 k+1 场的布尔变量为真」，2k+1 表示「为假」
struct Edge {
    int to;    // 边的终点
    int nxt;   // 同起点的下一条边
};
Edge edge[MAXE];  // 链式前向星的边池，edge[0] 作为空指针
int head[MAXV];   // head[u]：u 的第一条出边编号
int edge_cnt;         // 边池指针：最新加入的边编号
int static_edge_cnt;  // 只由静态规则建成的边数，每轮枚举结束后把 edge_cnt 退回这里

// 每轮枚举新增的动态边需要在下一轮撤销，只还原被改过 head 的节点
int saved_head[MAXV];   // saved_head[u]：本轮第一次给 u 加边之前的 head[u]
int touch_stamp[MAXV];  // touch_stamp[u]：u 最后一次被本轮修改时的轮次标记
int touched[MAXV];      // touched[]：本轮被修改过 head 的节点清单
int touched_cnt;
int run_stamp;          // 当前枚举轮次标记

// Tarjan 每个节点自己的状态：打包成一个 16 字节的 struct，遍历时一个节点只占半条缓存行。
struct Node {
    int low;   // low[u]：u 能回溯到的最小 dfn
    int dfn;   // dfn[u]：dfs 序，0 表示本轮还没访问
    int iter;  // iter[u]：u 的下一条待处理出边
    int scc;   // scc[u]：所属强连通分量编号，-1 表示尚未归属
};
Node node[MAXV];

// pair_tag[k]：第 k 个布尔变量已经弹出的那一半属于哪个强连通分量（全局唯一标签）。
// 弹出节点时顺手登记，就能 O(1) 判断「互补文字是否落在同一个分量」，不必再扫一遍栈。
long long pair_tag[MAXN];
long long cur_tag;
int dfs_clock, scc_cnt;
int tarjan_stk[MAXV], tarjan_top;   // 强连通分量栈（按 dfn 从小到大压栈）
int dfs_path[MAXV], path_top;       // 显式模拟的 DFS 路径栈

// live_node[]：真正可能进入 2-SAT 图的节点 = 所有规则端点的两个文字。
// 完全没被任何规则提到的位置，两个文字都是孤立点，不参与 DFS，也无需每轮重置。
int live_node[MAXV];
int live_cnt;

int answer_car[MAXN];   // answer_car[p]：第 p 场最终选用的赛车编号
bool satisfiable;       // 本轮判定结果

int read_car(char ch) {
    return ch - 'A';
}

void add_edge(int u, int v) {
    edge_cnt++;
    edge[edge_cnt].to = v;
    edge[edge_cnt].nxt = head[u];
    head[u] = edge_cnt;
}

// 第 p 场若禁用赛车 f，则两辆可用的车依次是 first/second。
int first_car(int f) {
    return f == 0 ? 1 : 0;
}

int second_car(int f) {
    return f == 2 ? 1 : 2;
}

// 第 p 场选赛车 car 对应的 2-SAT 文字：真文字 2(p-1)，假文字 2(p-1)+1。
// 约定布尔变量为真 == 选「第二辆可用车」，为假 == 选「第一辆可用车」。
int literal_with_forbid(int p, int f, int car) {
    return 2 * (p - 1) + (car == second_car(f) ? 0 : 1);
}

void read_data() {
    cin >> n >> d_declared;
    cin >> (S + 1);
    cin >> m;

    x_cnt = 0;
    for (int p = 1; p <= n; p++) {
        x_id[p] = -1;
        forb[p] = -1;
        if (S[p] == 'x') {
            x_id[p] = x_cnt;
            x_pos[x_cnt] = p;
            x_cnt++;
        } else {
            forb[p] = S[p] - 'a';
        }
    }

    for (int e = 1; e <= m; e++) {
        char hi, hj;
        cin >> ri[e] >> hi >> rj[e] >> hj;
        rci[e] = read_car(hi);
        rcj[e] = read_car(hj);
    }
}

// 先把不涉及 x 地图的规则建成固定的边。它们每轮枚举都不变，只需建一次。
void build_static_graph() {
    // 没出现在任何规则里的 x 地图，选哪辆车都不影响可行性，固定成「禁用 A」即可，
    // 不必为它多枚举一倍。只有出现在规则里的 x 地图才需要枚举。
    bool in_rule[10] = {false};
    for (int e = 1; e <= m; e++) {
        if (x_id[ri[e]] >= 0) {
            in_rule[x_id[ri[e]]] = true;
        }
        if (x_id[rj[e]] >= 0) {
            in_rule[x_id[rj[e]]] = true;
        }
    }
    enum_cnt = 0;
    for (int k = 0; k < x_cnt; k++) {
        if (in_rule[k]) {
            enum_x[enum_cnt++] = k;
        } else {
            forb[x_pos[k]] = 0;  // 自由变量：随便禁用一辆，剩两辆足以满足任何规则
        }
    }

    edge_cnt = 0;
    for (int e = 1; e <= m; e++) {
        bool xi = x_id[ri[e]] >= 0;
        bool xj = x_id[rj[e]] >= 0;

        // 非 x 端点上的文字每轮都一样，先算好；x 端点留到枚举时按当前禁用车辆再算。
        ri_fixed[e] = xi ? 0
                         : (rci[e] == forb[ri[e]] ? -1
                                                 : literal_with_forbid(ri[e], forb[ri[e]], rci[e]));
        rj_fixed[e] = xj ? 0
                         : (rcj[e] == forb[rj[e]] ? -1
                                                 : literal_with_forbid(rj[e], forb[rj[e]], rcj[e]));

        if (xi || xj) {
            dyn_rule[dyn_cnt++] = e;
            continue;
        }

        int li = ri_fixed[e];
        int lj = rj_fixed[e];
        if (li < 0) {
            continue;  // 前提在这张地图上本来就不可能，规则恒成立
        }
        if (lj < 0) {
            add_edge(li, li ^ 1);  // 结论不可能成立，只能强制前提为假
        } else {
            add_edge(li, lj);
            add_edge(lj ^ 1, li ^ 1);
        }
    }
    static_edge_cnt = edge_cnt;  // 静态图到此为止，之后的边都是每轮临时追加的

    // 动态边的端点只可能是规则两端的位置；静态边的端点也都在规则两端之内。
    // 因此「规则两端位置的两个文字」就是全部可能参与图的节点。
    bool seen_node[MAXV] = {false};
    live_cnt = 0;
    for (int e = 1; e <= m; e++) {
        for (int side = 0; side < 2; side++) {
            int p = (side == 0) ? ri[e] : rj[e];
            for (int half = 0; half < 2; half++) {
                int u = 2 * (p - 1) + half;
                if (!seen_node[u]) {
                    seen_node[u] = true;
                    live_node[live_cnt++] = u;
                }
            }
        }
    }
}

// 给节点 u 临时加一条边；第一次改 u 时先记下原来的 head，便于本轮结束后撤销。
void add_dynamic_edge(int u, int v) {
    if (touch_stamp[u] != run_stamp) {
        touch_stamp[u] = run_stamp;
        saved_head[u] = head[u];
        touched[touched_cnt++] = u;
    }
    edge_cnt++;
    edge[edge_cnt].to = v;
    edge[edge_cnt].nxt = head[u];
    head[u] = edge_cnt;
}

// 显式栈版 Tarjan（迭代写法的原因见文件头）。返回值：是否存在变量与其取反在同一强连通分量。
// 一旦某个强连通分量里同时出现 $2k$ 与 $2k+1$，立即返回 false，避免整张图跑完。
bool tarjan() {
    dfs_clock = 0;
    scc_cnt = 0;
    tarjan_top = 0;
    path_top = 0;

    // 每轮把「可能参与图的节点」的 dfn 清 0。出度为 0 的节点仍可能被别的点指向，
    // 所以 live_node 必须包含所有规则端点；只有完全没被规则提到的位置可以排除在外。
    for (int idx = 0; idx < live_cnt; idx++) {
        int u = live_node[idx];
        node[u].dfn = 0;
        node[u].scc = -1;
    }

    for (int idx = 0; idx < live_cnt; idx++) {
        int start = live_node[idx];
        // 出度为 0 的节点自成一个单点强连通分量，不可能与互补文字同分量，
        // 无需作为 DFS 起点（它若被别的点指向，会在那个 DFS 里被正常访问到）。
        if (head[start] == 0 || node[start].dfn != 0) {
            continue;
        }
        node[start].dfn = node[start].low = ++dfs_clock;
        node[start].iter = head[start];
        tarjan_stk[tarjan_top++] = start;
        dfs_path[path_top++] = start;

        while (path_top > 0) {
            int u = dfs_path[path_top - 1];
            int e = node[u].iter;

            if (e != 0) {
                node[u].iter = edge[e].nxt;
                int v = edge[e].to;
                if (node[v].dfn == 0) {
                    node[v].dfn = node[v].low = ++dfs_clock;
                    node[v].scc = -1;  // 新入栈的节点必须清掉上一轮遗留的分量编号
                    node[v].iter = head[v];
                    tarjan_stk[tarjan_top++] = v;
                    dfs_path[path_top++] = v;
                } else if (node[v].scc < 0 && node[v].dfn < node[u].low) {
                    node[u].low = node[v].dfn;  // 回边：v 还在栈上
                }
                continue;
            }

            // u 的出边处理完，结算 u
            path_top--;
            if (node[u].low == node[u].dfn) {
                cur_tag++;
                bool conflict = false;
                int w;
                do {
                    w = tarjan_stk[--tarjan_top];
                    int k = w >> 1;
                    if (pair_tag[k] == cur_tag) {
                        conflict = true;  // 互补的两半落在同一个强连通分量
                    }
                    pair_tag[k] = cur_tag;
                    node[w].scc = scc_cnt;
                } while (w != u);
                scc_cnt++;
                if (conflict) {
                    return false;
                }
            }
            if (path_top > 0) {
                int parent = dfs_path[path_top - 1];
                if (node[u].low < node[parent].low) {
                    node[parent].low = node[u].low;
                }
            }
        }
    }
    return true;
}

// 在 mask 指定的「每张 x 地图禁用哪辆车」方案下判定；有解时把安排写入 answer_car[]。
bool check_mask(int mask) {
    run_stamp++;
    touched_cnt = 0;

    // 每张 x 地图：mask 的第 k 位为 0 表示禁用 A，为 1 表示禁用 B。
    // 「禁用 A / 禁用 B」两种情形合起来已覆盖 A、B、C 三种真实取值。
    for (int k = 0; k < enum_cnt; k++) {
        forb[x_pos[enum_x[k]]] = ((mask >> k) & 1) ? 1 : 0;
    }

    for (int idx = 0; idx < dyn_cnt; idx++) {
        int e = dyn_rule[idx];
        int i = ri[e];
        int j = rj[e];
        int li, lj;
        if (x_id[i] >= 0) {
            li = (rci[e] == forb[i]) ? -1 : literal_with_forbid(i, forb[i], rci[e]);
        } else {
            li = ri_fixed[e];
        }
        if (x_id[j] >= 0) {
            lj = (rcj[e] == forb[j]) ? -1 : literal_with_forbid(j, forb[j], rcj[e]);
        } else {
            lj = rj_fixed[e];
        }

        if (li < 0) {
            continue;
        }
        if (lj < 0) {
            add_dynamic_edge(li, li ^ 1);
        } else {
            add_dynamic_edge(li, lj);
            add_dynamic_edge(lj ^ 1, li ^ 1);
        }
    }

    satisfiable = tarjan();

    // 撤销本轮加的动态边，恢复静态图：head 只需还原被改过的节点，边池指针退回静态边数
    for (int idx = 0; idx < touched_cnt; idx++) {
        int u = touched[idx];
        head[u] = saved_head[u];
    }
    edge_cnt = static_edge_cnt;

    if (!satisfiable) {
        return false;
    }

    for (int p = 1; p <= n; p++) {
        bool takes_second = node[2 * (p - 1)].scc < node[2 * (p - 1) + 1].scc;
        answer_car[p] = takes_second ? second_car(forb[p]) : first_car(forb[p]);
    }
    return true;
}

void solve() {
    int mask_cnt = 1 << enum_cnt;
    for (int mask = 0; mask < mask_cnt; mask++) {
        if (check_mask(mask)) {
            for (int p = 1; p <= n; p++) {
                cout << char('A' + answer_car[p]);
            }
            cout << '\n';
            return;
        }
    }
    cout << -1 << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_data();
    build_static_graph();
    solve();

    return 0;
}

复杂度

数据范围为 $n \leqslant 5 \times 10^4$ ， $m \leqslant 10^5$ ， $d \leqslant 8$ 。记 $d'$ 为真正出现在规则里的 x 地图张数（ $d' \leqslant d \leqslant 8$ ），共 $2^{d'}$ 个枚举分支。

时间： $O\big(k \cdot (n + m)\big)$ ，其中 $k$ 是「第一个可行分支的枚举序号」， $k \leqslant 2^{d'}$ 。

这里 $k$ 不是一个可以忽略的符号，它决定了真实耗时：

程序一旦某个分支找到解就立即返回，所以根本不跑满 $2^{d'}$ 轮。
有解且最早可行分支靠前时， $k$ 很小，最好情况 $k = 1$ ，此时只要一轮建图 + 一轮 Tarjan；
最坏情况是全部 $2^{d'}$ 个分支都无解，此时必须跑满 $2^{d'}$ 轮才能确认输出 -1， $k = 2^{d'}$ 是真正的上界，且常数是满的。

最坏情况的量级： $d' = 8$ 、 $n = 5\times 10^4$ 、 $m = 10^5$ 时

2^{8} \times (5\times 10^4 + 10^5) \approx 5.5\times 10^7 \text{ 次基本操作},

在 C++ 中约 1 秒量级，紧贴本题的 1s 时限。

空间： $O(n + m)$ 。

实测： $k$ 对耗时的实际影响

构造 $n = 5\times 10^4$ 、 $d = 8$ 、 $m = 10^5$ 、8 张 x 地图全部进入规则（约 $5\times 10^4$ 条规则含 x）的数据，并人为限制程序最多尝试 $k$ 个分支，测同一份数据下的耗时：

尝试分支数 $k$	1	8	32	64	128	192	256
耗时	26 ms	54 ms	151 ms	280 ms	531 ms	809 ms	约 1.1 s

耗时随 $k$ 线性增长， $k = 2^8 = 256$ 时达到约 1.1 秒。由此可以判断什么时候危险：

8 张 x 地图都进规则，且实例无解（必须跑满 256 个分支）——这是本题最坏的数据形态，约 1.1 秒，会超 1s；
有解且首个可行分支落在前几十个分支内，几十到几百毫秒就能出结果；
若某张 x 地图没有出现在任何规则里，枚举量会降到 $2^{d'}<2^8$ ，风险随之下降。

也就是说， $2^{d'}(n+m)$ 这个“总操作数”在有解时被严重高估，但在全无解时是实打实要付的成本。本实现的常数已经压得较低（静态边只建一次、每轮只追加动态边、 $\mathrm{live\_node}$ 裁剪、互补冲突早退），但无法改变“全无解要跑满 $2^{d'}$ 轮”这个固有开销——要再快只能换算法思路或上 bitset 等加速。

总结

本题的教学价值在于两次"换模型"：

“3 选 1” → “2 选 1”：非 x 地图天然只有两辆可用车，用一个布尔变量就能表示全部选择，把约束满足问题变成 2-SAT。
“指定取值” → “指定范围”：x 地图有 3 个候选，最朴素的想法是枚举 3 种取值（ $3^d$ ）。但 2-SAT 的能力是"给定范围、自己挑值"，所以只要告诉它"禁 A"或"禁 B"，两种情形就能覆盖 A、B、C 三个真实取值，枚举量降到 $2^d$ 。

第 2 步是常见误区所在：很多人会顺着"3 个取值"去枚举 $3^d$ ，虽然也能过，多花了 $1.5^d$ 的常数；而理解"2-SAT 是自动选择器"之后， $2^d$ 的方案既更省又更贴合算法本质。

实现上最容易出错的三处：

每轮 Tarjan 前必须重置所有参与图的节点 dfn。出度为 0 的节点虽然没有出边，仍可能被别的点指向而在 DFS 中被访问到；只重置"有出边的节点"会让上一轮的 dfn 残留，把"本轮未访问"误判成"已访问"。
强连通分量要整段弹出后再检查互补冲突。边弹边查会漏掉"互补的两半都在当前分量里、还没被弹出"的情况。
递归深度到 $10^5$ 级别就别用裸递归了，改显式栈。

P3825 [NOI2017] 游戏

题目背景

【本题原题时限 1s】

狂野飙车是小 L 最喜欢的游戏。与其他业余玩家不同的是，小 L 在玩游戏之余，还精于研究游戏的设计，因此他有着与众不同的游戏策略。

题目描述

小 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。

若有解，则包含一个长度为 $n$ 的仅包含大写字母 A、B、C 的字符串，表示小 L 在这 $n$ 场游戏中如何安排赛车的使用。如果存在多组解，输出其中任意一组即可。

输入输出样例 #1

输入 #1

text

1
2
3
43 1
xcc
1
1 A 2 B

输出 #1

text

1ABA

说明/提示

样例 1 解释

小 $L$ 计划进行 $3$ 场游戏，其中第 $1$ 场的地图类型是 $x$ ，适合所有赛车，第 $2$ 场和第 $3$ 场的地图是 $c$ ，不适合赛车 $C$ 。

小 $L$ 希望：若第 $1$ 场游戏使用赛车 $A$ ，则第 $2$ 场游戏使用赛车 $B$ 。

那么为这 $3$ 场游戏分别安排赛车 $A$ 、 $B$ 、 $A$ 可以满足所有条件。

若依次为 $3$ 场游戏安排赛车为 $BBB$ 或 $BAA$ 时，也可以满足所有条件，也被视为正确答案。

但依次安排赛车为 $AAB$ 或 $ABC$ 时，因为不能满足所有条件，所以不被视为正确答案。

样例 2

详见附加文件。

数据范围

测试点编号	$n$	$d$	$m$	其他性质
$1$	$\le 2$	$0$	$\le 4$	无
$2$	$\le 2$	$\le n$	$\le 4$	无
$3$	$\le 5$	$0$	$\le 10$	无
$4$	$\le 5$	$\le n$	$\le 10$	无
$5$	$\le 10$	$0$	$\le 20$	无
$6$	$\le 10$	$\le 8$	$\le 20$	无
$7$	$\le 20$	$0$	$\le 40$	$S$ 中只包含 $c$
$8$	$\le 20$	$0$	$\le 40$	无
$9$	$\le 20$	$\le 8$	$\le 40$	$S$ 中只包含 $x$ 或 $c$
$10$	$\le 20$	$\le 8$	$\le 40$	无
$11$	$\le 100$	$0$	$\le 200$	$S$ 中只包含 $c$
$12$	$\le 100$	$0$	$\le 200$	无
$13$	$\le 100$	$\le 8$	$\le 200$	$S$ 中只包含 $x$ 或 $c$
$14$	$\le 100$	$\le 8$	$\le 200$	无
$15$	$\le 5\times 10^3$	$0$	$\le 10^4$	无
$16$	$\le 5\times 10^3$	$\le 8$	$\le 10^4$	$S$ 中只包含 $x$ 或 $c$
$17$	$\le 5\times 10^3$	$\le 8$	$\le 10^4$	无
$18$	$\le 5\times 10^4$	$0$	$\le 10^5$	无
$19$	$\le 5\times 10^4$	$\le 8$	$\le 10^5$	$S$ 中只包含 $x$ 或 $c$
$20$	$\le 5\times 10^4$	$\le 8$	$\le 10^5$	无