链接
https://www.luogu.org/problemnew/show/P3825
思路
3-sat神马的就不要想了，NP问题
除去x每个点只有两种可能，2-sat
x只有8个，\(3^n\)暴力枚举哪个不选
2-sat是对称性的
当起点x的战车不存在，continue
else 当终点的战车不存在，那么起点战车也不能选呀(选了就G了呀)，起点连向剩下的那个可选点
else 起点终点都还在，连起来，否逆命题：原命题为：若a，则b。逆否命题为：若非b，则非a。
所以他俩的兄弟还要连一条边
但是计算一下发现，有点小超时呀
其实只要枚举A和B(随便两个)就好了
因为一个点最终只会用一辆车呀(有一辆就是个摆设)
\(2^n\)已经把所有可以选的情况整出来了
然后开心的\(O(2^n(n+m))\)
其他的
难道我天生就是制造bug的吗
后记：
uojTLE1个(貌似要随机化，输出，不管了)
luoguwrong1个(spj没判回车)
bzojok
lojok
代码
#include <bits/stdc++.h>
using namespace std;
const int N=3e5+7;
int read() {
int x=0,f=1;char s=getchar();
for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
return x*f;
}
int n,m,d,head[N<<2],tot;
int top,cnt,stak[N],low[N],dfn[N],belong[N];
bool vis[N],Choose[N];
char s[N],S[N];
struct node {
int v,nxt;
}e[N<<2];
struct edge {
int i,x,j,y;
}ABC[N];
void add(int u,int v) {
swap(u,v);
e[++tot].v=v;
e[tot].nxt=head[u];
head[u]=tot;
}
void tarjan(int u) {
low[u]=dfn[u]=++cnt;
stak[++top]=u;
vis[u]=1;
for(int i=head[u];i;i=e[i].nxt) {
int v=e[i].v;
if(!dfn[v]) {
tarjan(v);
low[u]=min(low[u],low[v]);
} else if(vis[v]) {
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u]) {
++belong[0];
while(stak[top]!=u) {
vis[stak[top]]=0;
belong[stak[top]]=belong[0];
top--;
} top--;
vis[u]=0;
belong[u]=belong[0];
}
}
void Clear() {
memset(head,0,sizeof(head));
memset(low,0,sizeof(low));
memset(dfn,0,sizeof(dfn));
memset(vis,0,sizeof(vis));
memset(belong,0,sizeof(belong));
cnt=top=tot=belong[0]=0;
}
int mmp[5][2]={ {1,2},
{0,2},
{0,1},};
void solve() {
int js=1;
for(int i=1;i<=n;++i) {
if(s[i]=='x'-'a') {
if(Choose[js]==0) S[i]=0;
else S[i]=1;
} else S[i]=s[i];
}
for(int i=1;i<=m;++i) {
if(ABC[i].x==S[ABC[i].i]) continue;
int tmp_1= (mmp[S[ABC[i].i]][1]==ABC[i].x) ? mmp[S[ABC[i].i]][0] : mmp[S[ABC[i].i]][1];
int tmp_2= (mmp[S[ABC[i].j]][1]==ABC[i].y) ? mmp[S[ABC[i].j]][0] : mmp[S[ABC[i].j]][1];
if(ABC[i].y==S[ABC[i].j]) add(ABC[i].i+n*ABC[i].x,ABC[i].i+n*tmp_1);
else {
add(ABC[i].i+n*ABC[i].x,ABC[i].j+n*ABC[i].y);
add(ABC[i].j+n*tmp_2,ABC[i].i+n*tmp_1);
}
}
for(int i=1;i<=3*n;++i) {
// if(S[(i-1)/3+1]==(i+2)%3) continue;一定没有这一句
if(!dfn[i])
tarjan(i);
}
for(int i=1;i<=n;++i) {
if(belong[i+n*(mmp[S[i]][0])]==belong[i+n*(mmp[S[i]][1])]) return;
// if(S[i]=='a'&&belong[i+n]==belong[i+2*n]) return;
// if(S[i]=='b'&&belong[i]==belong[i+2*n]) return;
// if(S[i]=='c'&&belong[i]==belong[i+n]) return;
}
for(int i=1;i<=n;++i) {
if(S[i]==0) {
if(belong[i+n]>belong[i+2*n]) printf("B");
else printf("C");
}
if(S[i]==1) {
if(belong[i]>belong[i+2*n]) printf("A");
else printf("C");
}
if(S[i]==2) {
if(belong[i]>belong[i+n]) printf("A");
else printf("B");
}
}
exit(0);
}
int main() {
//freopen("a.in","r",stdin);
n=read(),d=read();
for(int i=1;i<=n;++i) {
char dd;
scanf("%c",&dd);
s[i]=dd-'a';
}
m=read();
for(int i=1;i<=m;++i) {
char s;
ABC[i].i=read();
s=getchar();
while(s==' ') s=getchar();
ABC[i].x= (s=='A') ? 0 : (s=='B') ? 1 : 2;
ABC[i].j=read();
s=getchar();
while(s==' ') s=getchar();
ABC[i].y= (s=='A') ? 0 : (s=='B') ? 1 : 2;
//end
}
for(int i=0;i<(1<<d);++i) {
for(int j=0;j<d;++j) Choose[j+1]=(bool)(1<<j)&i;
Clear();
solve();
}
puts("-1");
return 0;
}
