题目描述
http://www.lydsy.com/JudgeOnline/upload/Noi2017D2.pdf
题解
如果说没有x的话，那么每一局只能有两种选择，可以描述为是/非，每条限制也可以描述是x即y。
那么这就是一道经典的2-SAT问题。
现在有了x的限制，但是观察到x的数目很少最多只有8，所以我们可以考虑枚举限制。
注意到其他的地方有两种情况是因为有一种情况被ban了，所以我们考虑枚举2^x枚举该局禁哪个，因为禁A和禁B已经可以包含所有的情况，所以就不用禁C了。
仅为有ban的存在，所以我们在处理限制的时候要注意，如果某个位置连向的位置被ban了，那么直接连x->x‘表示x不合法。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define M 100002
#define N 50002
using namespace std;
char s[N],ss[];
int head[M],st[M],top,low[M],dfn[M],tot,co[M],num,ban[N],jin[N],n;
bool vis[M];
inline int rd(){
int x=;char c=getchar();bool f=;
while(!isdigit(c)){if(c=='-')f=;c=getchar();}
while(isdigit(c)){x=(x<<)+(x<<)+(c^);c=getchar();}
return f?-x:x;
}
struct node{
int x,y,xx,yy;
}b[M];
struct edge{int n,to;}e[M<<];
inline void add(int u,int v){e[++tot].n=head[u];e[tot].to=v;head[u]=tot;}
void tarjan(int u){
vis[u]=;st[++top]=u;low[u]=dfn[u]=++dfn[];
for(int i=head[u];i;i=e[i].n){
int v=e[i].to;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(vis[v])low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
++num;int x;
do{
x=st[top];
vis[x]=;
co[x]=num;
top--;
}
while(x!=u);
}
}
int main(){
n=rd();int d=rd();
scanf("%s",s+);
for(int i=;i<=n;++i){
if(s[i]=='x')jin[++jin[]]=i;
else if(s[i]=='a')ban[i]=;
else ban[i]=;
s[i]-='a';
}
int m=rd();
for(int i=;i<=m;++i){
b[i].x=rd();scanf("%s",ss);b[i].xx=ss[]-'A';
b[i].y=rd();scanf("%s",ss);b[i].yy=ss[]-'A';
}
for(int i=;i<(<<d);++i){
for(int j=;j<=jin[];++j){
int x=(i&(<<j-))!=;
if(x)s[jin[j]]=,ban[jin[j]]=;
else s[jin[j]]=,ban[jin[j]]=;
}
memset(head,,sizeof(head));tot=;
for(int j=;j<=m;++j){
if(s[b[j].x]==b[j].xx)continue;
int nowx,nowy,antix,antiy;
nowx=(b[j].xx==ban[b[j].x])?b[j].x:b[j].x+n;antix=nowx<=n?nowx+n:nowx-n;
if(s[b[j].y]==b[j].yy){
add(nowx,antix);continue;
}
nowy=(b[j].yy==ban[b[j].y])?b[j].y:b[j].y+n;antiy=nowy<=n?nowy+n:nowy-n;
add(nowx,nowy);
add(antiy,antix);
}
memset(dfn,,sizeof(dfn));num=;
for(int j=;j<=n*;++j)if(!dfn[j])tarjan(j);
bool ta=;
for(int j=;j<=n;++j)if(co[j]==co[j+n]){ta=;break;}
if(ta)continue;
for(int j=;j<=n;++j)if(co[j]<co[j+n]){
if(ban[j]==)printf("B");
else printf("A");
}
else{
if(ban[j]==)printf("C");
else if(s[j]==)printf("C");else printf("B");
}
return ;
}
printf("-1");
return ;
}