先来讲一下到底什么叫K-SAT
先来看看2-SAT的准确定义
那么对于k-SAT，不是说每个集合就有\(k\)个元素了（每个集合仍然只有两个元素，因为布尔变量的取值只有\(0\)和\(1\)），而是说给出的限制条件涉及\(k\)个元素，比如3-SAT
那么对于这道题目，如果不考虑\(\text{x}\)的话，就是一个裸的2-SAT问题；发现\(d\)很小，考虑\(\text{x}\)的话，枚举即可（由于也要让\(\text{x}\)只包含两个元素，所以是枚举的不能用哪一类型的赛车）。具体见这篇题解
但是要讲一下细节
一.最好先将每个地图可以用的赛车类型用字符串存下来（按字典序排序），比如pt[i]="AB"表示第\(i\)个地图可以用的赛车类型为\(A\)和\(B\)，然后在加边的时候，再去判断是\(i\)还是\(i+n\)，要简单很多
二.不要用STL，用手写栈
三.如果对每个\(\text{x}\)枚举三种情况的话，理论复杂度就会炸掉，这个时候就要思考能不能只枚举两种情况，另外一种情况已经被包含了
四.也是卡常新操作：将链式前向星清空一部分。我们枚举的时候，每一次都要情况链式前向星的话，常熟太大了；此时我们可以先将所有不涉及\(\text{x}\)的边全部加入，然后在枚举的时候不删除这些边，只删除新加入的边（涉及\(\text{x}\)的边）即可
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10,M=1e5+10;
int n,m,d;
int visitime;
int dfn[N<<1],low[N<<1];
int pos[10];
int s[N<<1],tp;
char S[N];
bool instack[N<<1];
string pt[N];
int scc;
int belong[N<<1];
int cnt,Cnt;
int End[M<<2],Last[N<<1],Next[M<<2];
int num,edge[M];
int u[M],v[M];
char a[M],b[M];
void add(int x,int y)
{
End[++Cnt]=y,Next[Cnt]=Last[x],Last[x]=Cnt;
}
void tarjan(int u)
{
dfn[u]=low[u]=++visitime;
s[++tp]=u;instack[u]=1;
for(int i=Last[u];i;i=Next[i])
{
int v=End[i];
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(dfn[v]&&instack[v])
{
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u])
{
++scc;
int v;
do{
v=s[tp--];instack[v]=0;
belong[v]=scc;
}while(v!=u);
}
}
void del(int x)
{
Cnt--;
Last[x]=Next[Last[x]];
}
int main()
{
bool mark=0;
scanf("%d%d",&n,&d);
scanf("%s",S);
for(int i=1;i<=n;i++)
switch(S[i-1])
{
case 'a':pt[i]="BC";break;
case 'b':pt[i]="AC";break;
case 'c':pt[i]="AB";break;
case 'x':pos[++cnt]=i;break;//pos记录每个x的位置
}
scanf("%d",&m);
for(int i=1;i<=m;i++)
scanf("%d %c%d %c\n",&u[i],&a[i],&v[i],&b[i]);
for(int i=1;i<=m;i++)
if(S[u[i]-1]!='x'&&S[v[i]-1]!='x')
{
if(pt[u[i]][0]==a[i])
{
if(pt[v[i]][0]==b[i]) add(u[i],v[i]),add(v[i]+n,u[i]+n);
else if(pt[v[i]][1]==b[i]) add(u[i],v[i]+n),add(v[i],u[i]+n);
else add(u[i],u[i]+n);
}
else if(pt[u[i]][1]==a[i])
{
if(pt[v[i]][0]==b[i]) add(u[i]+n,v[i]),add(v[i]+n,u[i]);
else if(pt[v[i]][1]==b[i]) add(u[i]+n,v[i]+n),add(v[i],u[i]);
else add(u[i]+n,u[i]);
}
}
else edge[++num]=i;
for(int i=0;i<(1<<cnt);i++)
{
visitime=scc=0;
tp=0;
for(int j=1;j<=(n<<1);j++)
dfn[j]=low[j]=instack[j]=belong[j]=0;
for(int j=1;j<=cnt;j++)
switch(i>>(j-1)&1)
{
case 0:pt[pos[j]]="BC";break;
case 1:pt[pos[j]]="AC";break;
}
for(int k=1,j=edge[k];k<=num;k++,j=edge[k])
if(pt[u[j]][0]==a[j])
{
if(pt[v[j]][0]==b[j]) add(u[j],v[j]),add(v[j]+n,u[j]+n);
else if(pt[v[j]][1]==b[j]) add(u[j],v[j]+n),add(v[j],u[j]+n);
else add(u[j],u[j]+n);
}
else if(pt[u[j]][1]==a[j])
{
if(pt[v[j]][0]==b[j]) add(u[j]+n,v[j]),add(v[j]+n,u[j]);
else if(pt[v[j]][1]==b[j]) add(u[j]+n,v[j]+n),add(v[j],u[j]);
else add(u[j]+n,u[j]);
}
for(int j=1;j<=(n<<1);j++)
if(!dfn[j]) tarjan(j);
bool flag=1;
for(int j=1;j<=n;j++)
if(belong[j]==belong[j+n])
{
flag=0;
break;
}
for(int k=1,j=edge[k];k<=num;k++,j=edge[k])//删边操作，想一下为什么成立
if(pt[u[j]][0]==a[j])
{
if(pt[v[j]][0]==b[j]) del(u[j]),del(v[j]+n);
else if(pt[v[j]][1]==b[j]) del(u[j]),del(v[j]);
else del(u[j]);
}
else if(pt[u[j]][1]==a[j])
{
if(pt[v[j]][0]==b[j]) del(u[j]+n),del(v[j]+n);
else if(pt[v[j]][1]==b[j]) del(u[j]+n),del(v[j]);
else del(u[j]+n);
}
if(!flag) continue;
mark=1;
for(int j=1;j<=n;j++)
printf("%c",belong[j]>belong[j+n]?pt[j][1]:pt[j][0]);
break;
}
if(!mark) puts("-1");
return 0;
}