如果不看 $x$ 赛场的话，剩下的三个赛场显然每个赛场只有两个赛车选择项，也就是说这样就变成了裸的 $2-sat$ ，直接做就好了。
如果加入有三个赛车选择项的 $x$ 赛场的话，显然就不好用 $2-sat$ 做了，难不成用 $3-sat$ ？
其实，如果 $x$ 只有两个赛车选择项的话一样是可以做的，我们考虑枚举每一个 $x$ 赛场所禁用的那个赛车，这样子就可以 $2-sat$ 了，不过这样 $dfs$ 的复杂度是 $3^d$ 的，爆炸了……
但是最终情况就是每一个 $x$ 赛场都要有过 $A,B,C$ 三种赛车的选择项，那么在禁掉 $A,B$ 的时候，剩下的赛车分别是 $B,C$ 和 $A,C$ ，这已经包含 $A,B,C$ 三种赛车了，所以我们的 $dfs$ 只有两个分支了…… 复杂度就是 $2^d$ ，过去了。
考虑 $2-sat$ 怎么做，首先对于一组限制，如果 $i$ 选了 $h_i$ ，$j$ 就必须选 $h_j$ 。反之如果 $j$ 没选 $h_j$ ，那么 $i$ 就一定不能选择 $h_i$ ，这样连边就好了。注意如果 $j$ 不能选 $h_j$ 的话，$i$ 直接连 $i+n$ 即可。输出方案的话，对于一个 $i$ 点，我们只要对缩点后的图中拓扑一下，然后看 $i$ 所在的强连通分量和 $i+n$ 所在的强连通分量谁拓扑序更小谁就是答案。当然 $tarjan$ 已经按照拓扑序来了…… 所以直接判就好了。
细节多，看代码。
Code：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+2;
const int M=4e5+2;
char S[N],No[N];
int n,d,m,book,t[N],head[N],cnt;
struct Edge{int nxt,to;} G[M];
struct Stint{int i,j;char hi,hj;} E[M];
int bel[N],dfn[N],low[N],hep[N],siz[N],tot,top,now;
void add(int u,int v) {
G[++cnt]=(Edge){head[u],v},head[u]=cnt;
}
template <typename _Tp> inline void IN(_Tp&x) {
char ch;bool flag=0;x=0;
while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
if(flag) x=-x;
}
void Tarjan(int u) {
low[u]=dfn[u]=++now,hep[++top]=u;
for(int i=head[u];i;i=G[i].nxt) {
int v=G[i].to;
if(!dfn[v]) Tarjan(v),low[u]=min(low[u],low[v]);
else if(!bel[v]) low[u]=min(low[u],dfn[v]);
}
if(!(low[u]^dfn[u])) {
bel[u]=++tot,siz[tot]=1;
while(hep[top]^u)
++siz[tot],bel[hep[top--]]=tot;
--top;
}return;
}
int opposite(int u) {return u>n?u-n:u+n;}
int point_id(int u,char c) {
/*
点的编号的规则就是对于一个赛场，除去禁用的赛车
后，剩下的赛车小的为 i，大的为 i+n.
*/
if(S[u]=='a') return c=='B'?u:n+u;
if(S[u]=='b'||S[u]=='c') return c=='A'?u:n+u;
return c=='C'?u+n:u;
}
bool sol() {
cnt=tot=now=0;
for(int i=1;i<=(n<<1);++i) bel[i]=head[i]=dfn[i]=0;
for(int i=1;i<=m;++i)
if(S[E[i].i]!='x'&&S[E[i].j]!='x') {
/*如果 E[i].i 本身就不可以选择对应赛车的话直接跳*/
if(S[E[i].i]-32==E[i].hi) continue;
int u=point_id(E[i].i,E[i].hi);/*得到点编号*/
/*如果 E[i].j 不可以选择对应赛车的话那么 u 无解*/
if(S[E[i].j]-32==E[i].hj) {add(u,opposite(u));continue;}
int v=point_id(E[i].j,E[i].hj);
/*按要求连边*/
add(u,v),add(opposite(v),opposite(u));
} else {
char si=S[E[i].i],sj=S[E[i].j];
if(si=='x'&&sj=='x') {
/*
注意这里禁掉的赛车变了，x 的那一方就判断一下当前
dfs 无法使用的赛车，其他的按照上面即可
*/
if(No[t[E[i].i]]==E[i].hi) continue;
int u=point_id(E[i].i,E[i].hi);
if(No[t[E[i].j]]==E[i].hj) {add(u,opposite(u));continue;}
int v=point_id(E[i].j,E[i].hj);
add(u,v),add(opposite(v),opposite(u));
} else if(si=='x'&&sj!='x') {
if(No[t[E[i].i]]==E[i].hi) continue;
int u=point_id(E[i].i,E[i].hi);
if(S[E[i].j]-32==E[i].hj) {add(u,opposite(u));continue;}
int v=point_id(E[i].j,E[i].hj);
add(u,v),add(opposite(v),opposite(u));
} else if(si!='x'&&sj=='x') {
if(S[E[i].i]-32==E[i].hi) continue;
int u=point_id(E[i].i,E[i].hi);
if(No[t[E[i].j]]==E[i].hj) {add(u,opposite(u));continue;}
int v=point_id(E[i].j,E[i].hj);
add(u,v),add(opposite(v),opposite(u));
}
}
/*2-sat 基础不再赘述*/
for(int i=1;i<=(n<<1);++i) if(!dfn[i]) Tarjan(i);
for(int i=1;i<=n;++i) if(bel[i]==bel[i+n]) return false;
for(int i=1,j=0;i<=n;++i)
if(S[i]=='a') printf("%c",bel[i]<bel[i+n]?'B':'C');
else if(S[i]=='b') printf("%c",bel[i]<bel[i+n]?'A':'C');
else if(S[i]=='c') printf("%c",bel[i]<bel[i+n]?'A':'B');
else if(S[i]=='x') {/*可以简洁点但是懒得改了 (QwQ)*/
char c=No[++j]=='A'?'B':'A';
printf("%c",bel[i]<bel[i+n]?c:'C');
}
return true;
}
void dfs(int step) {
if(step>d) {
if(book) exit(0);
else book=sol();
return;
}
No[step]='A',dfs(step+1),/*两个分支*/
No[step]='B',dfs(step+1);
}
int main() {
IN(n),IN(d),scanf("%s",S+1);
for(int i=1,j=0;i<=n;++i) if(S[i]=='x') t[i]=++j;
char op1[2],op2[2];
IN(m);
for(int i=1;i<=m;++i)
scanf("%d%s%d%s",&E[i].i,op1,&E[i].j,op2),E[i].hi=op1[0],E[i].hj=op2[0];
dfs(1);
if(!book) puts("-1");/*无解*/
return 0;
}
0 条评论