自动搬运

查看原文

来自洛谷，原作者为

	xyz32768 “各方面相差太远”

搬运于2025-08-24 21:53:08，当前版本为作者最后更新于2017-08-16 17:24:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$NOI2017 Day2 T1$。

$2-SAT$。

我那时候一看发现是NOI/NOI+/CTSC的难度我没敢去做，但是一看，过的人还是比较多的，就试着做了一下...不多说了，讲一讲做法：

可以发现，除了x地图之外，其余的地图只适合两种赛车。而在这里，我们先假设所有的地图都适合且只适合两种赛车，这样就是$2-SAT$裸题了。

对于每场游戏用两个点$i$和$i'$，分别表示第$i$场游戏使用该地图适合的第一种赛车和第二种赛车（举例：如果第$i$场游戏的地图不适合A赛车，那么点$i$表示第$i$场游戏使用B赛车，点$i'$表示第$i$场游戏使用C赛车）。

对于每个限制条件，设$u$为表示「第$i$场游戏使用型号为$hi$的赛车」的点（在第$i$场游戏的地图适合型号为$hi$的赛车的情况下），$v$为表示「第$j$场游戏使用型号为$hj$的赛车」的点（在第$j$场游戏的地图适合型号为$hj$的赛车的情况下），

那么，

如果第$i$场游戏的地图不适合型号为$hi$的赛车，那么不做任何操作。

如果第$i$场游戏的地图适合型号为$hi$的赛车，但第$j$场游戏的地图不适合型号为$hj$的赛车，那么建边$u->u'$，表示如果第$i$场游戏使用了型号为$hi$的赛车则一定无解。

如果第$i$场游戏的地图适合型号为$hi$的赛车，第$j$场游戏的地图适合型号为$hj$的赛车，那么建边$u->v$，表示如果第$i$场游戏使用了型号为$hi$的赛车则第$j$场游戏必须使用型号为$hj$的赛车，再建边$v'->u'$，表示如果第$j$场游戏不使用型号为$hj$的赛车则第$i$场游戏不得使用型号为$hi$的赛车。

所有边都建完之后跑一遍$Tarjan$强连通分量缩点。对于任意一个$i$，如果$i$和$i'$在同一个强连通分量里面，那么此时无解。

否则输出方案。$2-SAT$输出方案的方法为：先把缩点之后的新图进行拓扑排序，然后判断每个点$i$，如果$i$所在强连通分量的拓扑序在$i'$所在的强连通分量的拓扑序之后，那么第$i$场游戏使用该地图适合的第一种赛车，否则使用第二种赛车。但是由于$Tarjan$求强连通分量就是按拓扑排序的逆序给出的，所以直接使用强连通分量编号判断即可。即如果$bel[]$为每个点的所在强连通分量编号，那么判断为：如果$bel[i]<bel[i']$，那么使用该地图适合的第一种赛车，否则使用第二种赛车。

现在考虑x地图，考虑到只有8张x地图，如果假设它也只适合两种赛车，那么暴力枚举每个x地图不适合赛车A或不适合赛车B（因为不适合赛车A就是适合赛车BC，不适合赛车B就是适合赛车AC，这样就包含了ABC三种赛车），这样每种地图就都只适合两种赛车了。判断时，如果已经枚举遍了所有的$2^d$种状态都是无解，则原问题无解，否则输出任意一种方案。

复杂度$O((n+m)*2^d)$。

代码：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
inline int read() {
    int res = 0; bool bo = 0; char c;
    while (((c = getchar()) < '0' || c > '9') && c != '-');
    if (c == '-') bo = 1; else res = c - 48;
    while ((c = getchar()) >= '0' && c <= '9')
        res = (res << 3) + (res << 1) + (c - 48);
    return bo ? ~res + 1 : res;
}
inline char get() {
    char c; while ((c = getchar()) != 'A' && c != 'B' && c != 'C');
    return c;
}
const int N = 2e5 + 5;
int n, d, m, a1[N], b1[N], ecnt, nxt[N], adj[N], go[N], dfn[N], low[N],
times, num, bel[N], top, stk[N], cyx[N];
char s[N], a2[N], b2[N], orz[N];
bool ins[N], flag;
void add_edge(int u, int v) {
    nxt[++ecnt] = adj[u]; adj[u] = ecnt; go[ecnt] = v;
}
int neg(int x) {return x > n ? x - n : x + n;}
int tran(int x, char c) {
    if (s[x] == 'a') return c == 'B' ? x : x + n;
    if (s[x] == 'b' || s[x] == 'c') return c == 'A' ? x : x + n;
    if (c == 'C') return x + n; return x;
}
void Tarjan(int u) {
    dfn[u] = low[u] = ++times; ins[stk[++top] = u] = 1;
    for (int e = adj[u], v; e; e = nxt[e])
        if (!dfn[v = go[e]]) {
            Tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (ins[v]) low[u] = min(low[u], dfn[v]);
    if (dfn[u] == low[u]) {
        int v; bel[u] = ++num; ins[u] = 0;
        while (v = stk[top--], v != u) bel[v] = num, ins[v] = 0;
    }
}
bool solve() {
    int i; ecnt = times = num = 0;
    for (i = 1; i <= (n << 1); i++) bel[i] = adj[i] = dfn[i] = 0;
    for (i = 1; i <= m; i++) if (s[a1[i]] != 'x' && s[b1[i]] != 'x') {
        if (a2[i] == s[a1[i]] - 32) continue;
        int u = tran(a1[i], a2[i]), v;
        if (b2[i] == s[b1[i]] - 32) {add_edge(u, neg(u)); continue;}
        v = tran(b1[i], b2[i]); add_edge(u, v);
        add_edge(neg(v), neg(u));
    }
    else {
        char o = s[a1[i]], p = s[b1[i]];
        int u, v, x = cyx[a1[i]], y = cyx[b1[i]];
        if (o == 'x' && p == 'x') {
            if (a2[i] == orz[x]) continue;
            u = tran(a1[i], a2[i]), v;
            if (b2[i] == orz[y]) {add_edge(u, neg(u)); continue;}
            v = tran(b1[i], b2[i]); add_edge(u, v);
            add_edge(neg(v), neg(u));
        }
        else if (o == 'x' && p != 'x') {
            if (a2[i] == orz[x]) continue;
            u = tran(a1[i], a2[i]), v;
            if (b2[i] == s[b1[i]] - 32) {add_edge(u, neg(u)); continue;}
            v = tran(b1[i], b2[i]); add_edge(u, v);
            add_edge(neg(v), neg(u));
        }
        else {
            if (a2[i] == s[a1[i]] - 32) continue;
            u = tran(a1[i], a2[i]), v;
            if (b2[i] == orz[y]) {add_edge(u, neg(u)); continue;}
            v = tran(b1[i], b2[i]); add_edge(u, v);
            add_edge(neg(v), neg(u));
        }
    }
    for (i = 1; i <= (n << 1); i++) if (!dfn[i]) Tarjan(i);
    for (i = 1; i <= n; i++) if (bel[i] == bel[i + n]) return 0;
    for (i = 1; i <= n; i++) {
        if (bel[i] < bel[i + n]) {
            if (s[i] == 'a') putchar('B');
            else if (s[i] == 'b' || s[i] == 'C') putchar('A');
            else if (orz[cyx[i]] == 'A') putchar('B');
            else putchar('A');
        }
        else {
            if (s[i] == 'a' || s[i] == 'b') putchar('C');
            else if (s[i] == 'c') putchar('B');
            else if (orz[cyx[i]] == 'A') putchar('C');
            else putchar('B');
        }
    }
    return 1;
}
void dfs(int dep) {
    if (dep > d) {
        if (!flag) flag = solve();
        if (flag) exit(0);
        return;
    }
    orz[dep] = 'A'; dfs(dep + 1);
    orz[dep] = 'B'; dfs(dep + 1);
}
int main() {
    int i; n = read(); read();
    scanf("%s", s + 1); m = read();
    for (i = 1; i <= n; i++) if (s[i] == 'x') cyx[i] = ++d;
    for (i = 1; i <= m; i++) a1[i] = read(), a2[i] = get(),
        b1[i] = read(), b2[i] = get(); dfs(1);
    if (!flag) puts("-1");
    return 0;
}