这是约半年前写的题解了，就搬过来吧
感觉这是NOI2017最水的一题（当然我还是不会2333），因为是一道裸的2-SAT。我就是看着这道题学的2-SAT
算法一：暴力枚举。对于abc二进制枚举，对于x则采用三进制枚举即可，复杂度O(3^d*2^(n-d))，再进行适当剪支，期望得分：40~50
算法二：对于d=0的点，采用2-SAT算法，这是最裸的2-SAT，这样，复杂度为O(n+m)，综合算法一，期望得分为60
算法三：不妨对于d个x，采用三进制枚举，枚举a/b/c，再做裸的2-SAT即可，复杂度O(3^d*(n+m))，期望得分：75~90，如果常数小可以X过去
算法四：不难发现，三进制枚举不但效率慢，而且难写、没必要，对于判断会很复杂，不如只枚举禁止使用A/B，因为这样已经包含了A/B/C三种赛车，所以可以这么做（因为题目只要求一组解），复杂度O(2^d*(n+m))，期望得分：100
难点：2-SAT和输出方案的2-SAT
注意：选A就选B等价于选B'就选A’，所以需要连接双向边！！
不说了上code
#include<bits/stdc++.h> #define mem(x) memset(x,0,sizeof x) using namespace std; const int N=2e5+99; int n,m,d,scc,cnt,top,c[N],s1[N],t1[N],dfn[N],low[N],part[N],hd[N],v[N],nxt[N],q[N]; char s[N],s2[N],t2[N],t[N]; bool vis[N],flag; void add(int x,int y){v[++cnt]=y;nxt[cnt]=hd[x];hd[x]=cnt;} int opp(int x){return x>n?x-n:x+n;} int jisuan(int x,char ch) { if(s[x]=='a')return ch=='B'?x:x+n; if(s[x]=='b'||s[x]=='c')return ch=='A'?x:x+n; if(ch=='C')return x+n; return x; } void tarjan(int u) { dfn[u]=low[u]=++cnt; q[++top]=u; vis[u]=1; for(int i=hd[u];i;i=nxt[i]) if(!dfn[v[i]]) { tarjan(v[i]); low[u]=min(low[u],low[v[i]]); } else if(vis[v[i]])low[u]=min(low[u],dfn[v[i]]); if(dfn[u]==low[u]) { part[u]=++scc; vis[u]=0; int now; do{ now=q[top--]; vis[now]=0; part[now]=scc; }while(now!=u); } } void solve() { scc=cnt=0; mem(dfn);mem(low);mem(part);mem(hd);mem(nxt); for(int i=1;i<=m;i++) if(s[s1[i]]!='x'&&s[t1[i]]!='x'&&s[s1[i]]-32!=s2[i]) { int u=jisuan(s1[i],s2[i]),v; if(s[t1[i]]-32==t2[i])add(u,opp(u)); else{ v=jisuan(t1[i],t2[i]); add(u,v);add(opp(v),opp(u)); } } else{ char S=s[s1[i]],T=s[t1[i]]; int x=c[s1[i]],y=c[t1[i]]; if(S=='x'&&T=='x'&&s2[i]!=t[x]) { int u=jisuan(s1[i],s2[i]),v; if(t2[i]==t[y])add(u,opp(u)); else{ v=jisuan(t1[i],t2[i]); add(u,v);add(opp(v),opp(u)); } } else if(S=='x'&&T!='x'&&s2[i]!=t[x]) { int u=jisuan(s1[i],s2[i]),v; if(s[t1[i]]-32==t2[i])add(u,opp(u)); else{ v=jisuan(t1[i],t2[i]); add(u,v);add(opp(v),opp(u)); } } else if(S!='x'&&T=='x'&&s[s1[i]]-32!=s2[i]) { int u=jisuan(s1[i],s2[i]),v; if(t2[i]==t[y])add(u,opp(u)); else{ v=jisuan(t1[i],t2[i]); add(u,v);add(opp(v),opp(u)); } } } cnt=0; for(int i=1;i<=n*2;i++)if(!dfn[i])tarjan(i); for(int i=1;i<=n;i++)if(part[i]==part[i+n])return; for(int i=1;i<=n;i++) if(part[i]<part[i+n]) { if(s[i]=='a')printf("B"); else if(s[i]=='b'||s[i]=='c')printf("A"); else if(t[c[i]]=='A')printf("B"); else printf("A"); } else{ if(s[i]=='a'||s[i]=='b')printf("C"); else if(s[i]=='c')printf("B"); else if(t[c[i]]=='A')printf("C"); else printf("B"); } flag=1; } void fact(int k) { if(flag)return; if(k>d){solve();return;} t[k]='A';fact(k+1);t[k]='B';fact(k+1); } int main() { scanf("%d%d",&n,&d); d=0; scanf("%s",s+1); for(int i=1;i<=n;i++)if(s[i]=='x')c[i]=++d; scanf("%d",&m); for(int i=1;i<=m;i++)scanf("%d %c%d %c",&s1[i],&s2[i],&t1[i],&t2[i]); fact(1); if(!flag)puts("-1"); }