链接

https://loj.ac/problem/2305
https://www.luogu.org/problemnew/show/P3825

思路

3-sat神马的就不要想了，NP问题
除去x每个点只有两种可能，2-sat
x只有8个，\(3^n\)暴力枚举哪个不选
2-sat是对称性的
当起点x的战车不存在，continue
else 当终点的战车不存在，那么起点战车也不能选呀(选了就G了呀)，起点连向剩下的那个可选点
else 起点终点都还在，连起来，否逆命题：原命题为：若a，则b。逆否命题为：若非b，则非a。
所以他俩的兄弟还要连一条边
但是计算一下发现，有点小超时呀
其实只要枚举A和B(随便两个)就好了
因为一个点最终只会用一辆车呀(有一辆就是个摆设)
\(2^n\)已经把所有可以选的情况整出来了
然后开心的\(O(2^n(n+m))\)

其他的

难道我天生就是制造bug的吗

后记：
uojTLE1个(貌似要随机化，输出，不管了)
luoguwrong1个(spj没判回车)
bzojok
lojok

代码

#include <bits/stdc++.h>
using namespace std;
const int N=3e5+7;
int read() {
    int x=0,f=1;char s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
int n,m,d,head[N<<2],tot;
int top,cnt,stak[N],low[N],dfn[N],belong[N];
bool vis[N],Choose[N];
char s[N],S[N];
struct node {
    int v,nxt;
}e[N<<2];
struct edge {
    int i,x,j,y;
}ABC[N];
void add(int u,int v) {
    swap(u,v);
    e[++tot].v=v;
    e[tot].nxt=head[u];
    head[u]=tot;
}
void tarjan(int u) {
    low[u]=dfn[u]=++cnt;
    stak[++top]=u;
    vis[u]=1;
    for(int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if(!dfn[v]) {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        } else if(vis[v]) {
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u]) {
        ++belong[0];
        while(stak[top]!=u) {
            vis[stak[top]]=0;
            belong[stak[top]]=belong[0];
            top--;
        } top--;
        vis[u]=0;
        belong[u]=belong[0];
    }
}
void Clear() {
    memset(head,0,sizeof(head));
    memset(low,0,sizeof(low));
    memset(dfn,0,sizeof(dfn));
    memset(vis,0,sizeof(vis));
    memset(belong,0,sizeof(belong));
    cnt=top=tot=belong[0]=0;
}
int mmp[5][2]={ {1,2},
                {0,2},
                {0,1},};
void solve() {
    int js=1;
    for(int i=1;i<=n;++i) {
        if(s[i]=='x'-'a') {
            if(Choose[js]==0) S[i]=0;
            else S[i]=1;
        } else S[i]=s[i];
    }
    for(int i=1;i<=m;++i) {
        if(ABC[i].x==S[ABC[i].i]) continue;
        int tmp_1= (mmp[S[ABC[i].i]][1]==ABC[i].x) ? mmp[S[ABC[i].i]][0] : mmp[S[ABC[i].i]][1];
        int tmp_2= (mmp[S[ABC[i].j]][1]==ABC[i].y) ? mmp[S[ABC[i].j]][0] : mmp[S[ABC[i].j]][1];
        if(ABC[i].y==S[ABC[i].j]) add(ABC[i].i+n*ABC[i].x,ABC[i].i+n*tmp_1);
        else {
            add(ABC[i].i+n*ABC[i].x,ABC[i].j+n*ABC[i].y);
            add(ABC[i].j+n*tmp_2,ABC[i].i+n*tmp_1);
        }
    }
    for(int i=1;i<=3*n;++i) {
        // if(S[(i-1)/3+1]==(i+2)%3) continue;一定没有这一句
        if(!dfn[i])
            tarjan(i);
    }
    for(int i=1;i<=n;++i) {
        if(belong[i+n*(mmp[S[i]][0])]==belong[i+n*(mmp[S[i]][1])]) return;
        // if(S[i]=='a'&&belong[i+n]==belong[i+2*n]) return;
        // if(S[i]=='b'&&belong[i]==belong[i+2*n]) return;
        // if(S[i]=='c'&&belong[i]==belong[i+n]) return;
    }
    for(int i=1;i<=n;++i) {
        if(S[i]==0) {
            if(belong[i+n]>belong[i+2*n]) printf("B");
            else printf("C");
        }
        if(S[i]==1) {
            if(belong[i]>belong[i+2*n]) printf("A");
            else printf("C");
        }
        if(S[i]==2) {
            if(belong[i]>belong[i+n]) printf("A");
            else printf("B");
        }
    }
    exit(0);
}
int main() {
//  freopen("a.in","r",stdin);
    n=read(),d=read();
    for(int i=1;i<=n;++i) {
        char dd;
        scanf("%c",&dd);
        s[i]=dd-'a';
    }
    m=read();
    for(int i=1;i<=m;++i) {
        char s;
        ABC[i].i=read();
        s=getchar();
        while(s==' ') s=getchar();
        ABC[i].x= (s=='A') ? 0 : (s=='B') ? 1 : 2;
        ABC[i].j=read();
        s=getchar();
        while(s==' ') s=getchar();
        ABC[i].y= (s=='A') ? 0 : (s=='B') ? 1 : 2;
        //end
    }
    for(int i=0;i<(1<<d);++i) {
        for(int j=0;j<d;++j) Choose[j+1]=(bool)(1<<j)&i;
        Clear();
        solve();
    }
    puts("-1");
    return 0;
}