来复习\(\text{2-sat}\)了

首先对于\(\operatorname{'a'},\rm{'b'},\rm{'c'}\)这三种地图，能放在上面的车只有两种

但是对于\(\rm{'x'}\)能放三种车，变成一个\(\text{3-sat}\)

众所周知\(\text{3-sat}\)只能搜索，于是我们爆搜这个位置放什么车

剩下的我们还是直接用\(\text{2-sat}\)来判定

对于一组限制\(u,h_i,v,h_j\)，如果\(u\)上不能放\(h_i\)这辆车，那么这个操作就不用处理了

如果\(v\)上不能放\(h_j\)这辆车，那么就让\(u->u'\)，表示一旦选择\(u\)就不合法了

否则我们就正常连边，连\(u->v\)，表示选择\(h_i\)就必须选\(h_j\)；最重要的是，根据对称性，我们还得连\(v'->u'\)，表示不选\(h_j\)就不能选\(h_i\)

这样做的复杂度是\(O(3^d(n+m))\) ，不大可行

考虑我们爆搜的时候不搜\('x'\)放什么车了，改为搜\('x'\)不放什么车，不放\(A\)车，那么就能放\(B\)车和\(C\)车；不放\(B\)车就能放\(A\)车和\(C\)车；所以我们只搜这个位置填成\(a\)还是\(b\)就把三种情况都计算了

于是复杂度\(O(2^d(n+m))\)

代码

#include
    
     #define re register#define LL long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))inline int read() {    char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;}const int maxn=1e5+5;char S[maxn],opv[maxn],opu[maxn];struct E{int v,nxt;}e[maxn*3];int u[maxn],v[maxn],tot,pos[15];int head[maxn],n,m,num,d,__,top,cnt;int dfn[maxn],col[maxn],low[maxn],st[maxn],f[maxn],id[2][maxn];inline void add(int x,int y) {    e[++num].v=y;e[num].nxt=head[x];head[x]=num;}void tarjan(int x) {    dfn[x]=low[x]=++__,f[x]=1,st[++top]=x;    for(re int i=head[x];i;i=e[i].nxt)     if(!dfn[e[i].v]) tarjan(e[i].v),low[x]=min(low[x],low[e[i].v]);    else if(f[e[i].v]) low[x]=min(low[x],dfn[e[i].v]);    if(dfn[x]==low[x]) {        ++cnt;int now;        do{now=st[top--];col[now]=cnt;f[now]=0;}while(now!=x);    }}inline int getid(int i,char c) {    if(S[i]==c+'a'-'A') return -1;    if(S[i]=='a') return c=='B'?0:1;    if(S[i]=='b') return c=='C'?0:1;    if(S[i]=='c') return c=='A'?0:1;}inline void put(int i,int c) {    if(S[i]=='a') putchar(c?'C':'B');    if(S[i]=='b') putchar(c?'A':'C');    if(S[i]=='c') putchar(c?'B':'A');}inline void solve() {    cnt=__=0;num=0;memset(head,0,sizeof(head));top=0;    memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));    memset(col,0,sizeof(col));memset(f,0,sizeof(f));    for(re int i=1;i<=m;i++) {        int x=getid(u[i],opu[i]);        if(x==-1) continue;        int y=getid(v[i],opv[i]);        if(y==-1) {add(id[x][u[i]],id[x^1][u[i]]);continue;}        add(id[x][u[i]],id[y][v[i]]);        add(id[y^1][v[i]],id[x^1][u[i]]);    }    for(re int i=1;i<=n+n;i++) if(!dfn[i]) tarjan(i);    for(re int i=1;i<=n;i++) if(col[i]==col[i+n]) return;    for(re int i=1;i<=n;i++)         if(col[i]
     
      >opu[i];        v[i]=read();std::cin>>opv[i];    }    for(re int i=1;i<=n;i++) id[0][i]=i,id[1][i]=i+n;    for(re int i=1;i<=n;i++) if(S[i]=='x') pos[++tot]=i;    dfs(1);puts("-1");return 0;}