游戏「NOI2017」

发现 $d \le 8$ ，这仿佛在提示我们要暴力枚举 $x$ 代表的是什么，注意到 $b,c$ 和 $a,c$ 就可以覆盖到 $x$ 的所有情况，所以我们只要枚举 $x$ 是 $A$ 或 $B$ 即可，时间复杂度 $2^d$ ，我们把枚举出来的地图序列叫做 $Map$

考虑这样编号， $A$ 对应 $[1,n]$ ， $B$ 对应 $[n+1,2 \times n]$ ， $C$ 对应 $[2 \times n +1 , 3*n]$

但是这样太过愚蠢，我们知道 $Map$ 是什么，所以一个位置不能放什么我们是知道的，不妨这样编号：

$Map[i]==A$ ，不能放 $A$ ，那么只能放 $B,C$ ， $B -> [1,n],C -> [n+1,2 \times n]$

$Map[i]==B$ ，不能放 $B$ ，那么只能放 $A,C$ ， $A -> [1,n],C -> [n+1,2 \times n]$

$Map[i]==C$ ，不能放 $C$ ，那么只能放 $A,B$ ， $A -> [1,n],B -> [n+1,2 \times n]$

简单来说，就是按照字典序编号。

如图：

接下来分类讨论即可。

我们设 $i$ 代表的序列为 $a[i]$ ， $j$ 代表的序列为 $a[j]$ ， $h_i=f1[i]，h_j=f2[j]$

1. $f1[i]==Map[a[i]]$

这就是告诉我们不能选 $f1[i]$ ，否则选了就挂了，直接continue掉。

1
2
3

if (f1[i]==Map[a[i]]){//一旦选了就挂了
    continue;
}

2. $f2[i]==Map[b[i]]$

这也是告诉我们不能选 $f1[i]$ ，但是我们可以选其他的，整理一下思路，发现 $Map[a[i]]$ 不能选 $f1[i]$ 不能选，根据上面我们的特判，发现 $Map[a[i]]!=f1[i]$ ，所以只有一个字母能选。

如何建一个图，强制选剩下的那个字母，这里我们使用奇巧淫技，假设第一列选了 $B$ 第三列就必须选 $C$ ，现在我们知道第一列只能选 $C$ ，就连一条 $B->C$ ，这样你选了 $B$ 就必须选 $C$ ，造成矛盾，等于是强制选了 $C$

else if (f2[i]==Map[b[i]]){//也是选了就挂了，但是有一种可以的选择
      //eg. a[i]=='B' Map[f1[i]]=='A' so 只能选'C'
      int delta=GetDelta1(i);
      AddEdge(a[i]+delta,a[i]+n-delta);
}

3. $else$

这是最普通的情况，假设第一列选了 $B$ 第三列就必须选 $B$ ，按照 $2-SAT$ 的问题的套路，我们要寻找有依赖性关系的点对，显然，选了第一列的 $B$ ，就必须选第三列的 $B$ ，还有，选了第三列的 $A$ ，就必须选第一列的 $C$ ，否则会发生矛盾，于是他们两个点对连边：

1
2
3

int delta1=GetDelta1(i),delta2=GetDelta2(i);
AddEdge(a[i]+delta1,b[i]+delta2);
AddEdge(b[i]+n-delta2,a[i]+n-delta1);

代码写的比较丑陋，其中一些细节模拟一下就知道了。

#include <bits/stdc++.h>
#define MAXN 2000005
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
vector<int>G[MAXN];
inline void AddEdge(int u,int v){
    G[u].push_back(v);
}
int dfn[MAXN],low[MAXN],cnt;
stack<int>stk;
int scc,col[MAXN];
void tarjan(int u){
    dfn[u]=low[u]=++cnt;
    stk.push(u);
    for (register int i=0;i<G[u].size();++i){
        int v=G[u][i];
        if (!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
        else if (!col[v]) low[u]=min(low[u],dfn[v]);
    }
    if (low[u]==dfn[u]){
        ++scc;
        do{
            col[u]=scc;
            u=stk.top(),stk.pop();
        }while (low[u]!=dfn[u]);
    }
}
inline char GetPre(char ch){
    if (ch=='A') return 'B';
    if (ch=='B') return 'A';
    if (ch=='C') return 'A';
}
inline char GetNex(char ch){
    if (ch=='A') return 'C';
    if (ch=='B') return 'C';
    if (ch=='C') return 'B';
}
inline char gc(){
    char ch=getchar();
    while (!isalpha(ch)) ch=getchar();
    if (ch>='a'&&ch<='z') return ch-'a'+'A';
    else return ch;
}
char Map[MAXN],ans[MAXN];
int a[MAXN],b[MAXN];
char f1[MAXN],f2[MAXN];
int pos[MAXN];//存的是x的下标
int n,m,d;
inline void Init(){
    while (stk.size()) stk.pop();
    memset(col,0,sizeof(col));
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    scc=cnt=0;
    for (register int i=0;i<MAXN;++i){
        G[i].clear();
    }
}
inline void GetAns(){
    bool flag=true;
    for (register int i=1;i<=n*2;++i){
        if (!dfn[i]) tarjan(i);
    }
    for (register int i=1;i<=n;++i){
        if (col[i]==col[i+n]){
            flag=false;
            break;
        }
        if (col[i]<col[i+n]) ans[i-1]=GetPre(Map[i]);
        else ans[i-1]=GetNex(Map[i]);
    }
    if (flag==true){
        cout<<ans;
        exit(0);
    }
}
inline int GetDelta1(int pos){
    //写成注释里这样可能方便理解
    // if (Map[a[pos]]=='A'&&f1[pos]=='B') return 0;
    // if (Map[a[pos]]=='A'&&f1[pos]=='C') return n;
    // if (Map[a[pos]]=='B'&&f1[pos]=='A') return 0;
    // if (Map[a[pos]]=='B'&&f1[pos]=='C') return n;
    // if (Map[a[pos]]=='C'&&f1[pos]=='A') return 0;
    // if (Map[a[pos]]=='C'&&f1[pos]=='B') return n;
    return (f1[pos]=='A'||(f1[pos]=='B'&&Map[a[pos]]=='A'))?0:n;
}
inline int GetDelta2(int pos){
    // if (Map[b[pos]]=='A'&&f2[pos]=='B') return 0;
    // if (Map[b[pos]]=='A'&&f2[pos]=='C') return n;
    // if (Map[b[pos]]=='B'&&f2[pos]=='A') return 0;
    // if (Map[b[pos]]=='B'&&f2[pos]=='C') return n;
    // if (Map[b[pos]]=='C'&&f2[pos]=='A') return 0;
    // if (Map[b[pos]]=='C'&&f2[pos]=='B') return n;
    return (f2[pos]=='A'||(f2[pos]=='B'&&Map[b[pos]]=='A'))?0:n;
}
int main(){
    n=read(),d=read();
    int c=0;
    scanf("%s",Map+1);
    for (register int i=1;i<=n;++i){
        Map[i]-='a',Map[i]+='A';
        if (Map[i]=='X') pos[++c]=i;
    }
    m=read();
    for (register int i=1;i<=m;++i){
        a[i]=read(),f1[i]=getchar(),b[i]=read(),f2[i]=getchar();
        getchar();
    }
    for (register int v=0;v<(1<<d);++v){
        Init();
        for (register int i=1;i<=d;++i){
            if (v&(1<<(i-1))) Map[pos[i]]='A';
            else Map[pos[i]]='B';
        }
        for (register int i=1;i<=m;++i){
            if (f1[i]==Map[a[i]]){//一旦选了就挂了
                continue;
            }
            else if (f2[i]==Map[b[i]]){//也是选了就挂了，但是有一种可以的选择
                //eg. a[i]=='A' Map[f1[i]]=='B' so 只能选'C'
                int delta=GetDelta1(i);
                AddEdge(a[i]+delta,a[i]+n-delta);
            }
            else {
                int delta1=GetDelta1(i),delta2=GetDelta2(i);
                AddEdge(a[i]+delta1,b[i]+delta2);
                AddEdge(b[i]+n-delta2,a[i]+n-delta1);
            }
        }
        GetAns();
    }
    puts("-1");
}