P3825 [NOI2017] 游戏 题解

首先解决没有 x 的情况，这种情况下 每个事件有两种选择，例如 a 可以选择 b, c，所以这就是一个 2-SAT 问题，但是这题比较特殊，除了题目中给的命题，还需要建立原命题的逆否命题所对应的边，最后跑一遍 \(\text{Tarjan}\) 就出解了。

考虑有 \(d\) 个 \(x\) 的情况，\(x\) 有三种取值，不过 \(\text{3-SAT}\) 是 \(\text{NPC}\) 问题，所以考虑大力枚举 \(x\) 的取值，暴力枚举 \(x\) 的三种取值 \(a,b , c\)，\(O(3^d(n+m))\)。

会爆炸，考虑优化，可以发现，只需要枚举 \(x\) 的两种取值即可，因为第三种情况已经被包含了，例如 \(x = a\) 意味着 \(B, C\) 的情况被考虑了，\(x = b\)，意味着 \(A, C\) 的情况被考虑了，于是这题只需要枚举每个 \(x\) 是 \(a, b\) 即可，时间复杂度：\(O(2^d(n+m))\)。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
//#define int long long
using namespace std;
const int N = 2e5 + 10;
typedef pair<int, int> PII;
typedef long long ll;

int n, d, m;
struct qwq {
    int a, c;
    char b, d;
} q[N], q2[N];
int idx, x[N];
string s, s2;
vector<int> g[N];
void add(int a, int b) { g[a].push_back(b);
// cout << "link: "<< a << ' ' << b << '\n';
 } 

int get(char o, char t) {
    if(o == t) return -1;
    if(o == 'a') return t == 'C';
    if(o == 'b') return t == 'C';
    if(o == 'c') return t == 'B';
}
char back(char o, int t) {
    if(o == 'a') return (t ? 'C' : 'B');
    if(o == 'b') return (t ? 'C' : 'A');
    if(o == 'c') return (t ? 'B' : 'A');
}
#define rev(x) (x > n ? x - n : x + n)
void link(int i) {
    int x = get(s[q[i].a], q[i].b), y = get(s[q[i].c], q[i].d);
    int a = (x ? q[i].a + 1 + n : q[i].a + 1), b = (y ? q[i].c + 1 + n : q[i].c + 1);
//    cout << a << ' ' << b << '\n';
    if(s[q[i].a] - 'a' == q[i].b - 'A') return ;
    else if(s[q[i].c] - 'a' == q[i].d - 'A') add(a, (rev(a)));
    else add(a, b), add(rev(b), rev(a));
}

int dfn[N], low[N], timestamp, scc, id[N], stk[N], top, ins[N];
void tarjan(int u) {
    dfn[u] = low[u] = ++ timestamp, stk[++top] = u, ins[u] = 1;
    for(auto v : g[u]) {
        if(!dfn[v]) 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 y;
        scc ++;
        do {
            y = stk[top --], id[y] = scc, ins[y] = 0;
        } while(y != u);
    }
}

bool flg;
void work(int h) {
    memcpy(q, q2, sizeof q2);
    s = s2, timestamp = 0, scc = 0, top = 0;
    memset(dfn, 0, sizeof dfn);
    for(int i = 1; i <= n * 2; i ++) g[i].clear();
    for(int i = 0; i < idx; i ++)
        if((1 << i) & h) s[x[i + 1]] = 'a';
        else s[x[i + 1]] = 'b';
    for(int i = 1; i <= m; i ++) 
        link(i);
    for(int i = 1; i <= n * 2; i ++)
        if(!dfn[i]) tarjan(i);
    for(int i = 1; i <= n; i ++) if(id[i] == id[i + n]) return ;
    flg = 1;
    for(int i = 1; i <= n; i ++) {
        if(id[i] < id[i + n]) cout << back(s[i - 1], 0);
        else cout << back(s[i - 1], 1);
    }
    exit(0);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> d >> s >> m;
    s2 = s;
    for(int i = 0; i < n; i ++) if(s[i] == 'x') x[++ idx] = i;
    for(int i = 1; i <= m; i ++) 
        cin >> q[i].a >> q[i].b >> q[i].c >> q[i].d, q[i].a --, q[i].c --;
    memcpy(q2, q, sizeof q);
    work(0);
    for(int s = 1; s < (1 << idx); s ++) work(s);
    cout << -1 << '\n';
    return 0;
}