Steven_Meng's Blog

洛谷

GDOI

发现$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掉。

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$，否则会发生矛盾，于是他们两个点对连边：

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");
}