题目大意

有四种类型的比赛 \(x,a,b,c\)，三种赛车（\(A,B,C\))。其中 \(x\) 的数量为 \(d\)。

\(x\) 表示三种赛车都可以选， \(a\) 表示 \(A\) 种不能选，\(b\) 表示 \(B\) 种不能选，\(c\) 表示 \(C\) 种不能选。

现在要比 \(n\) 场，有 \(m\) 个限制形如：

\(p,f,q,t\) 表示如果第 \(p\) 场选了第 \(f\) 种的赛车则第 \(q\) 场必须选用第 \(t\) 种赛车。

求任意一组满足所有要求的赛车选择方案。

\(n,m\leq10^5\)，\(d\leq8\)。

思路

如果没有 \(x\) 的话可以直接考虑 \(2-SAT\)，以每一场比赛作为变量，能选的两种赛车作为布尔变量即可，然后就是找规律。将变量设为 \(i_0\) 和 \(i_1\)。

但是现在处理 \(x\)，注意到数量很少，所以可以直接枚举 \(x\) 的种类，将它变成 \(a\) 或 \(b\)。

为什么我们不需要再变成 \(c\) 呢？因为在发现如果要不选 \(C\) 的话在 \(a,b\) 中都可以直接不选（如果这样是对的话），所以重复了，直接不选。这样我们可以大概猜的最终时间复杂度是 \(O(2^d(m+n))\)。

考虑建图。分三种情况，设第 \(i\) 个比赛目前不能选 \(F_i\)：

\(f_p=F_p\)，则这个情况一定不会成立，可以直接忽略
\(t_q=F_q\)，则这个情况的前提一定不能成立，连 \(p_0\rightarrow p_1\)。
除此以外的情况，连命题 \(p_0\rightarrow q_0\) 与它的逆否命题 \(q_1\rightarrow p_1\)。

之后跑 \(2-SAT\) 求是否合法与输出方案数即可。对于 \(2-SAT\) 方案数，我们理应按照缩点后图跑拓扑排序后优先输出拓扑序大的，但因为 \(Tarjan\) 缩点就是按拓扑排序的逆序输出的，所以我们只需要输出强连通分量编号小的即可。

代码

#include<bits/stdc++.h>
#define T(u,v) u+turn[rc[u]][v]
#define N(u,v) u+turn2[rc[u]][v]
using namespace std;
typedef long long ll;
const ll MAXN=1e5+5;
ll n,d,m;
vector<ll>adj[MAXN];
ll lyymcl[MAXN],dfn[MAXN],yjr[MAXN],tot;
ll id[MAXN],scc;
bool ins[MAXN];
void add(ll u,ll v){
	adj[u].push_back(v);
}
stack<ll>sta;
ll turn[3][3],turn2[3][3];
ll rc[MAXN];
void lycnpy(ll u){
	dfn[u]=lyymcl[u]=++tot;
	ins[u]=true;
	sta.push(u);
	for(auto lmy:adj[u]){
		if(!dfn[lmy]){
			lycnpy(lmy);
			lyymcl[u]=min(lyymcl[u],lyymcl[lmy]);
		}else if(ins[lmy]){
			lyymcl[u]=min(lyymcl[u],dfn[lmy]);
		}
	}
	if(lyymcl[u]==dfn[u]){
		++scc;
		while(sta.top()!=u){
			id[sta.top()]=scc;
			ins[sta.top()]=false;
			sta.pop();
		}
		id[u]=scc;
		ins[u]=false;
		sta.pop();
	}
}
void lyc(){
	for(int i=1;i<=2*n;++i){
		if(!dfn[i]){
			lycnpy(i);
		}
	}
}
struct Query{
	ll p,q;
	ll t,f;
}ask[MAXN];
void clear(){
	for(int i=0;i<=2*n+3;++i){
		adj[i].clear();
	}
	memset(lyymcl,0,sizeof(lyymcl));
	memset(dfn,0,sizeof(dfn));
	memset(yjr,0,sizeof(yjr));
	tot=scc=0;
	memset(id,0,sizeof(id));
} 
ll tn(char c){
	if(c=='a'||c=='A'){
		return 0;
	} 
	if(c=='b'||c=='B'){
		return 1;
	}
	if(c=='c'||c=='C'){
		return 2;
	}
	return 4;
}
void check(){
		clear();
		for(int i=1;i<=m;++i){
			ll t=ask[i].t,f=ask[i].f,p=ask[i].p,q=ask[i].q;
			if(f==rc[p]){
				continue;
			}
			if(t==rc[q]){
				add(T(p,f),N(p,f));
			}else{
				add(T(p,f),T(q,t));
				add(N(q,t),N(p,f));
			}
		}
		lyc();
		bool good=false;
		for(int i=1;i<=n;++i){
			if(id[i]==id[n+i]){
				good=true;
				break;
			}
		}
		if(!good){
			for(int i=1;i<=n;++i){
				if(id[i]<id[n+i]){
					if(rc[i]==0){
						cout<<"B";
					}else if(rc[i]==1){
						cout<<"A";
					}else{
						cout<<"A";
					}
				}else{
					if(rc[i]==0){
						cout<<"C";
					}else if(rc[i]==1){
						cout<<"C";
					}else{
						cout<<"B";
					}
				}
			}
			exit(0);
		}
}
void dfs(ll x){
	if(x==n+1){
		check();
		return;
	}
	if(rc[x]==4){
		rc[x]=0;
		dfs(x+1);
		rc[x]=1;
		dfs(x+1);
		return;
	}
	dfs(x+1);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>d;
	for(int i=1;i<=n;++i){
		char c;
		cin>>c;
		rc[i]=tn(c);
	}
	for(int i=0;i<3;++i){
		bool good=false;
		for(int j=0;j<3;++j){
			if(j==i){
				continue;
			}
			if(good){
				turn[i][j]=n;
				turn2[i][j]=0;
			}else{
				good=true;
				turn[i][j]=0;
				turn2[i][j]=n;
			}
		}
	}
	cin>>m;
	for(int i=1;i<=m;++i){
		char f,t;
		cin>>ask[i].p>>f>>ask[i].q>>t;
		ask[i].f=tn(f);
		ask[i].t=tn(t);
	}
	dfs(1);
	cout<<-1<<endl;
	return 0;
}