Luogu的spj现在挂了，要去其他OJ提交。
2-SAT
发现如果不考虑$x$的情况，这就成为一个2-SAT的裸题了，我们有$O(n + m)$的方法可以解决它。
那加上$x$的情况怎么弄……岂不是变成一个3-SAT。
滑稽吧，3-SAT已经被证明是一个完全NPC问题了……
再观察一下数据范围发现为$x$的点最多只有$8$个，那么我们思考一下（看一下题解）就会发现$x$的点取$a$或者$b$的情况其实就可以遍历到所有可行解了，所以直接取枚举这个$2^{d}$，然后$O(n + m)$地去检验它，时间复杂度$O(2^{d}(n + m))$。
连边方法（假设当前的条件是$x, c1, y, c2$）：
1、如果第$x$场不能使用$x$，那么直接$continue$，这个条件显然没有影响。
2、如果第$x$场能使用$x$，第$y$场不能使用$y$，那么直接把$(x, true)$连向$(x, false)$，代表如果选了$(x, true)$就无解。
3、如果第$x$场可以使用$x$，第$y$场也可以使用$y$，那么按照套路连成一个对偶图，把$(x, true)$向$(y, true)$连边，同时把$(y, false)$向$(x, false)$连边。
关于$(x, true)$和$(x, false)$的记法，可以自己yy一下，要把$(x, true)$记为$x$, $(x, false)$记为$x + n$， 最后输出的时候对应回来就好。
Code：
#include <cstdio> #include <cstring> #include <cstdlib> using namespace std; const int N = 2e5 + 5; int n, m, K, pos[10], tot, head[N]; int dfsc, dfn[N], low[N], top, sta[N], scc, bel[N]; char str[N]; bool vis[N]; struct Eedge { int to, nxt; } e[N << 1]; inline void add(int from, int to) { e[++tot].to = to; e[tot].nxt = head[from]; head[from] = tot; } inline void read(int &X) { X = 0; char ch = 0; int op = 1; for(; ch > '9' || ch < '0'; ch = getchar()) if(ch == '-') op = -1; for(; ch >= '0' && ch <= '9'; ch = getchar()) X = (X << 3) + (X << 1) + ch - 48; X *= op; } struct Restrain { char c1, c2; int x, y; inline void readIn() { c1 = c2 = 0; read(x); for(c1 = getchar(); c1 != 'A' && c1 != 'B' && c1 != 'C'; c1 = getchar()); read(y); for(c2 = getchar(); c2 != 'A' && c2 != 'B' && c2 != 'C'; c2 = getchar()); } } a[N]; inline int id(int now, char c) { if(str[now] == 'a') return c == 'C' ? now : now + n; if(str[now] == 'b') return c == 'A' ? now : now + n; if(str[now] == 'c') return c == 'B' ? now : now + n; return 0; } inline int opp(int nowId) { return nowId > n ? nowId - n : nowId + n; } inline int min(int x, int y) { return x > y ? y : x; } void tarjan(int x) { dfn[x] = low[x] = ++dfsc; vis[x] = 1, sta[++top] = x; for(int i = head[x]; i; i = e[i].nxt) { int y = e[i].to; if(!dfn[y]) { tarjan(y); low[x] = min(low[x], low[y]); } else if(vis[y]) low[x] = min(low[x], dfn[y]); } if(low[x] == dfn[x]) { ++scc; for(; sta[top + 1] != x; --top) { vis[sta[top]] = 0; bel[sta[top]] = scc; } } } inline bool solve() { dfsc = tot = top = scc = 0; memset(dfn, 0, sizeof(dfn)); memset(low, 0, sizeof(low)); memset(bel, 0, sizeof(bel)); memset(head, 0, sizeof(head)); for(int i = 1; i <= m; i++) { if(a[i].c1 + 32 == str[a[i].x]) continue; if(a[i].c1 == a[i].c2 && a[i].x == a[i].y) continue; int p1 = id(a[i].x, a[i].c1), p2 = opp(p1); int p3 = id(a[i].y, a[i].c2), p4 = opp(p3); if(a[i].c2 + 32 == str[a[i].y]) { add(p1, p2); continue; } add(p1, p3), add(p4, p2); } for(int i = 1; i <= 2 * n; i++) if(!dfn[i]) tarjan(i); for(int i = 1; i <= n; i++) if(bel[i] == bel[i + n]) return 0; return 1; } inline void print() { for(int i = 1; i <= n; i++) { if(bel[i] < bel[i + n]) { if(str[i] == 'a') putchar('C'); if(str[i] == 'b') putchar('A'); if(str[i] == 'c') putchar('B'); } else { if(str[i] == 'a') putchar('B'); if(str[i] == 'b') putchar('C'); if(str[i] == 'c') putchar('A'); } } exit(0); } int main() { read(n), read(K); scanf("%s", str + 1); K = 0; for(int i = 1; i <= n; i++) if(str[i] == 'x') pos[++K] = i; /* for(int i = 1; i <= K; i++) printf("%d ", pos[i]); printf(" "); */ read(m); for(int i = 1; i <= m; i++) a[i].readIn(); /* for(int i = 1; i <= m; i++) printf("%d %c %d %c ", a[i].x, a[i].c1, a[i].y, a[i].c2); */ for(int S = 0; S < (1 << K); S++) { for(int i = 0; i < K; i++) if((S >> i) & 1) str[pos[i + 1]] = 'a'; else str[pos[i + 1]] = 'b'; bool flag = solve(); if(flag) print(); } puts("-1"); return 0; }