Description
http://www.lydsy.com/JudgeOnline/upload/Noi2017D2.pdf
Solution
字符串里的'x'看起来很烦，于是考虑枚举这些'x'的情况。这里只要枚举'a'和'b'就行了，因为如果存在解的话，肯定包含了解
那么在枚举之后，每场比赛两个点，对应可以选的两辆车，然后就是个2-SAT的裸题了
#include<bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
const int MAXN=100000+10;
int n,m,d,e,ps[10],p[MAXN][3],tot,cnt,Be[MAXN],beg[MAXN],nex[MAXN<<2],to[MAXN<<2],DFN[MAXN],LOW[MAXN],Visit_Num,Stack[MAXN],In_Stack[MAXN],Stack_Num;
char s[MAXN];
struct node{
int i;char hi;
int j;char hj;
};
node limit[MAXN];
template<typename T> inline void read(T &x)
{
T data=0,w=1;
char ch=0;
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();
x=data*w;
}
template<typename T> inline void write(T x,char ch=' ')
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
if(ch!=' ')putchar(ch);
}
template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}
template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}
template<typename T> inline T min(T x,T y){return x<y?x:y;}
template<typename T> inline T max(T x,T y){return x>y?x:y;}
inline void insert(int x,int y)
{
to[++e]=y;
nex[e]=beg[x];
beg[x]=e;
}
inline void Tarjan(int x)
{
DFN[x]=LOW[x]=++Visit_Num;
In_Stack[x]=1;
Stack[++Stack_Num]=x;
for(register int i=beg[x];i;i=nex[i])
if(!DFN[to[i]])Tarjan(to[i]),chkmin(LOW[x],LOW[to[i]]);
else if(In_Stack[to[i]]&&DFN[to[i]]<LOW[x])LOW[x]=DFN[to[i]];
if(DFN[x]==LOW[x])
{
int temp;++cnt;
do{
temp=Stack[Stack_Num--];
In_Stack[temp]=0;
Be[temp]=cnt;
}while(temp!=x);
}
}
inline bool solve()
{
tot=1;
for(register int i=1;i<=n;++i)
{
p[i][0]=p[i][1]=p[i][2]=0;
if(s[i]!='a')p[i][0]=++tot;
if(s[i]!='b')p[i][1]=++tot;
if(s[i]!='c')p[i][2]=++tot;
}
e=0;memset(beg,0,sizeof(beg));cnt=0;
memset(Be,0,sizeof(Be));
memset(DFN,0,sizeof(DFN));
memset(LOW,0,sizeof(LOW));
for(register int i=1;i<=m;++i)
if(s[limit[i].i]!=limit[i].hi-'A'+'a')
{
int u=p[limit[i].i][limit[i].hi-'A'],v=p[limit[i].j][limit[i].hj-'A'];
if(s[limit[i].j]==limit[i].hj-'A'+'a')insert(u,u^1);
else insert(u,v),insert(v^1,u^1);
}
for(register int i=2;i<=tot;++i)
if(!DFN[i])Tarjan(i);
for(register int i=2;i<=tot;i+=2)
if(Be[i]==Be[i^1])return false;
for(register int i=2,u;i<=tot;i+=2)
{
u=Be[i]>Be[i^1]?i^1:i;
if(p[i>>1][0]==u)putchar('A');
if(p[i>>1][1]==u)putchar('B');
if(p[i>>1][2]==u)putchar('C');
}
return true;
}
int main()
{
read(n);read(d);d=0;
scanf("%s",s+1);
read(m);
for(register int t=1;t<=m;++t)
{
int i,j;char hi,hj;
read(i);scanf("%c",&hi);
read(j);scanf("%c",&hj);
limit[t]=(node){i,hi,j,hj};
}
for(register int i=1;i<=n;++i)
if(s[i]=='x')ps[++d]=i;
int st=0;
for(;st<(1<<d);++st)
{
for(register int i=0;i<d;++i)s[ps[i+1]]=(st&(1<<i))?'b':'a';
if(solve())break;
}
if(st>=(1<<d))write(-1);
puts("");
return 0;
}