Description
Solution
首先我们发现一个位置如果不是 ('x'),那么就只有两种选择
而 ('x') 的个数小于等于 (8),直接枚举是哪个就好了
然后就是 (2-sat) 连边:
设一个点 (i) 的对立点为 (i')
如果 (a[i]=h[i]),那么就可以直接忽略这个限制
如果 (a[j]=h[j]),那么 (i) 就不能选 (a[i]),为了保证这个限制直接连边 ((i,i')) 就好了
如果上述两种情况都不是,那么直接连 ((i,j),(j',i')) 就好了
值得注意的是:
(2-sat) 如果没有字典序最小的要求,可以直接 (tarjan) (O(n)) 的判断是否合法
方法就是判断对立点是否在同一强连通分量里即可
输出方案(拓扑排序贪心):
正向贪心会有后效性
把缩点之后的 (DAG) 的边反向,发现一个点 (i) 选了之后,拓扑序在 (i') 之后的点就都不可以选了
每一次选了 (i) 之后,就把 (i') 打上标记即可,就不拿有标记的点删边了
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,D,m,lis[N],fr[N],tr[N];char s[N],a[N],b[N];
int head[N],nxt[N*2],to[N*2],num=1,in[N];
inline void link(int x,int y){nxt[++num]=head[x];to[num]=y;head[x]=num;}
int dfn[N],low[N],DFN=0,st[N],top,sum,be[N];bool inst[N],vis[N],fc[N];
vector<int>v[N],sc[N];vector<int>::iterator it;
inline void Clear(){
num=1;DFN=sum=top=0;
for(register int i=0;i<N;i++)
vector<int>().swap(sc[i]),head[i]=low[i]=dfn[i]=inst[i]=0;
}
inline int id(int i,char j){
if(s[i]=='a'){if(j=='b')return i;return i+n;}
if(s[i]=='b'){if(j=='a')return i;return i+n;}
if(j=='a')return i;return i+n;
}
inline int f(int x){return x>n?x-n:x+n;}
inline void tarjan(int x){
low[x]=dfn[x]=++DFN;inst[x]=1;st[++top]=x;
for(int i=head[x],u;i;i=nxt[i]){
if(!dfn[u=to[i]])tarjan(u),low[x]=min(low[x],low[u]);
else if(inst[u])low[x]=min(low[x],dfn[u]);
}
if(low[x]==dfn[x]){
int v;sum++;
do{
v=st[top--];be[v]=sum;inst[v]=0;
sc[sum].push_back(v);
}while(top && v!=x);
}
}
inline void Cliear(){
for(register int i=0;i<N;i++)
vector<int>().swap(v[i]),in[i]=vis[i]=fc[i]=0;
}
inline void solve(){
Clear();
for(int i=1;i<=m;i++){
if(s[fr[i]]==a[i])continue;
if(s[tr[i]]==b[i])link(id(fr[i],a[i]),f(id(fr[i],a[i])));
else{
int x=id(fr[i],a[i]),y=id(tr[i],b[i]);
link(x,y);link(f(y),f(x));
}
}
for(int i=1,li=n*2;i<=li;i++)if(!dfn[i])tarjan(i);
for(int i=1;i<=n;i++)if(be[i]==be[i+n])return ;
Cliear();
for(int i=1,li=n*2;i<=li;i++)
for(int j=head[i];j;j=nxt[j]){
int u=to[j];
if(be[u]==be[i])continue;
v[be[u]].push_back(be[i]);in[be[i]]++;
}
queue<int>Q;
for(int i=1;i<=sum;i++)if(!in[i])Q.push(i);
while(!Q.empty()){
int x=Q.front();Q.pop();
if(vis[x])continue;fc[x]=1;
for(it=sc[x].begin();it!=sc[x].end();++it)vis[be[f(*it)]]=1;
for(it=v[x].begin();it!=v[x].end();++it)
if(!(--in[*it]))Q.push(*it);
}
for(int i=1;i<=n;i++){
if(fc[be[i]]){
if(s[i]=='a')putchar('B');
else putchar('A');
}
else{
if(s[i]=='c')putchar('B');
else putchar('C');
}
}
exit(0);
}
inline void dfs(int x){
if(x==D+1){solve();return ;}
s[lis[x]]='a';dfs(x+1);
s[lis[x]]='b';dfs(x+1);
}
int main(){
freopen("pp.in","r",stdin);
freopen("pp.out","w",stdout);
scanf("%d%d%s",&n,&D,s+1);
for(int i=1,j=0;i<=n;i++)if(s[i]=='x')lis[++j]=i;
scanf("%d",&m);char p1[2],p2[2];
for(int i=1;i<=m;i++){
scanf("%d%s%d%s",&fr[i],p1,&tr[i],p2);
a[i]=p1[0]+32;b[i]=p2[0]+32;
}
dfs(1);
puts("-1");
return 0;
}