代码

// NOI2017 游戏 (noi17d) correct solver - 2-SAT with 2^d enumeration over 'x'
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

static const int MAXN = 50005;
static int n, d, m;
static char S[MAXN];
static int xpos[10];       // positions of 'x' (0-based), count d
static int cur[10];        // 0 -> 'a', 1 -> 'b' for each x

// 2-SAT graph: 2*n nodes
static vector<int> g[2*MAXN];
static int dfn[2*MAXN], low[2*MAXN], bel[2*MAXN];
static int stk[2*MAXN], top, ts, scc;
static bool instk[2*MAXN];

// constraints
static int ci[MAXN*2], cj[MAXN*2]; char chi[MAXN*2], chj[MAXN*2];

static inline int carId(int i, char car){
    // what node corresponds to "position i uses car"? 0 -> first allowed, 1 -> second allowed
    // allowed cars for position i depend on S[i] and cur[] for x
    char a0, a1;
    char typ = S[i];
    if(typ == 'x'){
        // find its x index
        int xi = -1;
        for(int k=0;k<d;k++) if(xpos[k]==i){ xi=k; break; }
        typ = (cur[xi]==0) ? 'a' : 'b';
    }
    if(typ=='a'){ a0='B'; a1='C'; }
    else if(typ=='b'){ a0='A'; a1='C'; }
    else { a0='A'; a1='B'; } // 'c'
    if(car==a0) return 2*i;
    if(car==a1) return 2*i+1;
    return -1;
}

static inline void addEdge(int u, int v){ g[u].push_back(v); }

static void tarjan(int u){
    dfn[u]=low[u]=++ts; stk[top++]=u; instk[u]=true;
    for(int v: g[u]){
        if(!dfn[v]){ tarjan(v); low[u]=min(low[u],low[v]); }
        else if(instk[v]) low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        ++scc;
        int v;
        do { v=stk[--top]; instk[v]=false; bel[v]=scc; } while(v!=u);
    }
}

static bool solve2sat(){
    int N = 2*n;
    for(int i=0;i<N;i++){ dfn[i]=low[i]=bel[i]=0; instk[i]=false; }
    ts=0; scc=0; top=0;
    for(int i=0;i<N;i++) if(!dfn[i]) tarjan(i);
    for(int i=0;i<n;i++) if(bel[2*i]==bel[2*i+1]) return false;
    return true;
}

int main(){
    if(scanf("%d %d",&n,&d)!=2) return 0;
    scanf("%s", S);
    scanf("%d", &m);
    // collect x positions
    int xc = 0;
    for(int i=0;i<n;i++) if(S[i]=='x') xpos[xc++]=i;
    for(int t=0;t<m;t++){
        int i,j; char hi[2], hj[2];
        scanf("%d %s %d %s", &i, hi, &j, hj);
        ci[t]=i-1; chi[t]=hi[0]; cj[t]=j-1; chj[t]=hj[0];
    }
    // enumerate
    for(int mask=0; mask < (1<<d); mask++){
        for(int k=0;k<d;k++) cur[k] = (mask>>k)&1;
        for(int i=0;i<2*n;i++) g[i].clear();
        for(int t=0;t<m;t++){
            int i=ci[t], j=cj[t]; char hi=chi[t], hj=chj[t];
            int a = carId(i, hi);
            if(a < 0) continue; // hi not allowed at i
            int b = carId(j, hj);
            if(b < 0){
                // i cannot use hi -> force i to use the other car
                int other = (a == 2*i) ? (2*i+1) : (2*i);
                addEdge(a, other);
            } else {
                addEdge(a, b);
                int na = (a == 2*i) ? (2*i+1) : (2*i);
                int nb = (b == 2*j) ? (2*j+1) : (2*j);
                addEdge(nb, na);
            }
        }
        if(solve2sat()){
            // output assignment: choose car whose bel is larger (Tarjan gives reverse topo)
            for(int i=0;i<n;i++){
                char a0,a1;
                char typ=S[i];
                if(typ=='x'){
                    int xi=-1; for(int k=0;k<d;k++) if(xpos[k]==i){xi=k;break;}
                    typ=(cur[xi]==0)?'a':'b';
                }
                if(typ=='a'){a0='B';a1='C';}
                else if(typ=='b'){a0='A';a1='C';}
                else {a0='A';a1='B';}
                if(bel[2*i] > bel[2*i+1]) putchar(a0); else putchar(a1);
            }
            putchar('\n');
            return 0;
        }
    }
    printf("-1\n");
    return 0;
}

评测结果