代码

// This code is AI-generated. (AI 生成的代码)
// NOI2017 游戏: enumerate the two usable types for every 'x' track (2^d cases),
// then solve the resulting 2-SAT with Tarjan.
#include <cstdio>
#include <cstring>

static const int MAXN = 50005, MAXE = 200005;
static int n, D, m, nx;
static int ft[MAXN];          // forbidden type of a track: 0=A,1=B,2=C, 3=x
static int xp[10];
static int cu[MAXE], cv[MAXE], ci[MAXE], cj[MAXE];
static int all[MAXN][2];      // the two usable types of a track
static int head[2 * MAXN], nxt[4 * MAXE], to[4 * MAXE], tc;
static int dfn[2 * MAXN], low[2 * MAXN], stk[2 * MAXN], in[2 * MAXN], comp[2 * MAXN];
static int timer, scc, top;

static inline void add_edge(int u, int v) {
    to[++tc] = v; nxt[tc] = head[u]; head[u] = tc;
}

static void tarjan(int u) {
    dfn[u] = low[u] = ++timer;
    stk[++top] = u; in[u] = 1;
    for (int e = head[u]; e; e = nxt[e]) {
        int v = to[e];
        if (!dfn[v]) { tarjan(v); if (low[v] < low[u]) low[u] = low[v]; }
        else if (in[v] && dfn[v] < low[u]) low[u] = dfn[v];
    }
    if (low[u] == dfn[u]) {
        ++scc;
        int v;
        do { v = stk[top--]; in[v] = 0; comp[v] = scc; } while (v != u);
    }
}

// node of literal "track i runs type t"; node 2i = first usable, 2i+1 = second
static inline int lit(int i, int t) {
    return all[i][0] == t ? (2 * i + 1) : (2 * i);
}

static char res[50005];

int main() {
    scanf("%d%d", &n, &D);
    static char s[50005];
    scanf("%s", s + 1);
    for (int i = 1; i <= n; i++) {
        char c = s[i];
        if (c == 'x') { xp[nx++] = i; ft[i] = 3; }
        else ft[i] = c - 'a';
    }
    scanf("%d", &m);
    static char u[4], v[4];
    for (int k = 0; k < m; k++) {
        scanf("%d%s%d%s", &ci[k], u, &cj[k], v);
        cu[k] = u[0] - 'A'; cv[k] = v[0] - 'A';
    }

    for (int i = 1; i <= n; i++) {
        if (ft[i] == 3) continue;
        if (ft[i] == 0) { all[i][0] = 1; all[i][1] = 2; }
        else if (ft[i] == 1) { all[i][0] = 0; all[i][1] = 2; }
        else { all[i][0] = 0; all[i][1] = 1; }
    }

    int total = 1 << nx;
    for (int mask = 0; mask < total; mask++) {
        for (int k = 0; k < nx; k++) {
            int i = xp[k];
            all[i][0] = 0;
            all[i][1] = ((mask >> k) & 1) ? 2 : 1;
        }
        memset(head, 0, sizeof(int) * (2 * n + 1));
        tc = 0;
        for (int k = 0; k < m; k++) {
            int i = ci[k], uu = cu[k], j = cj[k], vv = cv[k];
            if (uu != all[i][0] && uu != all[i][1]) continue;
            int ni = lit(i, uu);
            if (vv == all[j][0]) { int nj = 2 * j + 1; add_edge(ni, nj); add_edge(nj ^ 1, ni ^ 1); }
            else if (vv == all[j][1]) { int nj = 2 * j; add_edge(ni, nj); add_edge(nj ^ 1, ni ^ 1); }
            else add_edge(ni, ni ^ 1);
        }
        memset(dfn, 0, sizeof(int) * (2 * n));
        timer = scc = top = 0;
        for (int i = 0; i < 2 * n; i++) if (!dfn[i]) tarjan(i);
        int ok = 1;
        for (int i = 1; i <= n; i++) if (comp[2 * i] == comp[2 * i + 1]) { ok = 0; break; }
        if (!ok) continue;
        for (int i = 1; i <= n; i++) {
            int b = (comp[2 * i] < comp[2 * i + 1]) ? 1 : 0;
            res[i - 1] = (char)('A' + all[i][b]);
        }
        res[n] = 0;
        puts(res);
        return 0;
    }
    puts("-1");
    return 0;
}

评测结果