https://www.lydsy.com/JudgeOnline/problem.php?id=4945
https://www.luogu.org/problemnew/show/P3825
题目不粘了。
对于冲突关系很明显是2-SAT，但是注意是2-SAT（lz曾经天真的gg过），也就是说，我们没法处理x。
不用慌，我们完全可以O(3^d)枚举，然而常数很大过不去uoj的hack。
但是思考如果为A则只可以选b/c，B则只可以选a/c，所以选C的情况已经被前面讨论完了，故可以O(2^d)枚举。
另外加点常数优化，比如if语句写else之类的TAT浪费我30min的时间卡常。
#include<cmath>
#include<stack>
#include<vector>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=5e4+;
const int M=1e5+;
inline int read(){
int X=,w=;char ch=;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();
return w?-X:X;
}
inline int getc(){
char ch;
while((ch=getchar())==' '||ch=='\n');
if(ch=='A'||ch=='a')return ;
if(ch=='B'||ch=='b')return ;
if(ch=='C'||ch=='c')return ;
return ;
}
struct data{
int x,l,y,r;
}p[M];
struct node{
int to,nxt;
}e[M<<];
int n,d,m,cnt,head[N<<],to[N<<],a[N],mp[];
int dfn[N<<],low[N<<],t,l;
bool inq[N<<];
stack<int>q;
inline void add(int u,int v){
e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;
}
void tarjan(int u){
dfn[u]=low[u]=++t;
q.push(u);inq[u]=;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}else if(inq[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u]){
int v;l++;
do{
v=q.top();q.pop();
to[v]=l;inq[v]=;
}while(v!=u);
}
}
inline int g(int x){
if(x>=)x-=;
return x;
}
inline int f(int x){
if(x>n)return x-n;
return x+n;
}
inline int num(int x,int k){
if(k==g(a[x]+))return x;
return x+n;
}
inline void print(int x,int on){
int t;
if(!on)t=g(a[x]+);
else t=g(a[x]+);
if(t==)putchar('A');
else if(t==)putchar('B');
else putchar('C');
}
inline void init(){
cnt=t=l=;
memset(head,,sizeof(head));
memset(dfn,,sizeof(dfn));
}
void solve(){
init();
for(int i=;i<=m;i++){
int x=p[i].x,l=p[i].l,y=p[i].y,r=p[i].r;
if(a[x]==l)continue;
int u=num(x,l),v=num(y,r);
if(a[y]==r)add(u,f(u));
else{
add(u,v);add(f(v),f(u));
}
}
for(int i=;i<=*n;i++)
if(!dfn[i])tarjan(i);
for(int i=;i<=n;i++)
if(to[i]==to[i+n])return;
for(int i=;i<=n;i++){
if(to[i]<to[i+n])print(i,);
else print(i,);
}
puts("");exit();
}
void dfs(int now){
if(now==d+){
solve();return;
}
a[mp[now]]=;dfs(now+);
a[mp[now]]=;dfs(now+);
}
int main(){
n=read();read();
for(int i=;i<=n;i++){
a[i]=getc();
if(a[i]==)mp[++d]=i;
}
m=read();
for(int i=;i<=m;i++){
p[i].x=read(),p[i].l=getc();
p[i].y=read(),p[i].r=getc();
}
dfs();
puts("-1");
return ;
}
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/ +
+++++++++++++++++++++++++++++++++++++++++++