一道简单的 $\texttt{2-SAT}$ 题目。
题目链接:Luogu P3825/BZOJ 4945/NOI2017 D2T1。
题目
题目描述
小 L 计划进行 $n$ 场游戏,每场游戏使用一张地图,小 L 会选择一辆车在该地图上完成游戏。
小 L 的赛车有三辆,分别用大写字母 ABC
表示。地图一共有四种,分别用小写字母 xabc
表示。其中,赛车 A
不适合在地图 a
上使用,赛车 B
不适合在地图 b
上使用,赛车 C
不适合在地图 c
上使用,而地图 x
则适合所有赛车参加。适合所有赛车参加的地图并不多见,最多只会有 $d$ 张。
$n$ 场游戏的地图可以用一个小写字母组成的字符串描述。小 L 对游戏有一些特殊的要求,这些要求可以用四元组 $(i,h _ i,j,h _ j)$ 来描述,表示若在第 $i$ 场使用型号为 $h _ i$ 的车子,则第 $j$ 场游戏要使用型号为 $h _ j$ 的车子。
你能帮小 L 选择每场游戏使用的赛车吗?如果有多种方案,输出任意一种方案。如果无解,输出 -1
。
数据范围
变量 | 取值范围 |
---|---|
$n$ | $\leq 5\times 10^4$ |
$d$ | $\leq 8$ |
$m$ | $\leq 10^5$ |
时空限制
题目 | 时间限制 | 空间限制 |
---|---|---|
Luogu P3825 | $1\text{s}$ | $125\text{MiB}$ |
BZOJ 4945 | $20\text{s}$ | $512\text{MiB}$ |
NOI2017 D2T1 | $1\text{s}$ | $512\text{MiB}$ |
题解
思路
考虑 $d=0$ 的情况,发现是裸的 $\texttt{2-SAT}$。
又发现 $d$ 不太大,于是考虑每一个 x
处选择改为 a
或 b
来满足 $\texttt{2-SAT}$ 的条件,并且发现 c
的情况已经包含无需枚举,所以最多考虑 $2^d$ 次。
单次 $\texttt{2-SAT}$ 的时间复杂度为 $\Theta(n+m)$,所以程序的时间复杂度为 $O(2^d(n+m))$。
代码
程序的时间复杂度为 $O(2^d(n+m))$。
#include<bits/stdc++.h>
using namespace std;
#define reg register
const int MAXN=50000+5;
const int MAXM=100000+5;
inline void Read(void);
inline void Work(void);
int main(void){
ios::sync_with_stdio(false);
Read();
Work();
return 0;
}
struct Rule{
int i,hi,j,hj;
inline void Read(void){
static char a,b;
cin>>i>>a>>j>>b;
hi=a-'A',hj=b-'A';
return;
}
};
int n,d,m;
char str[MAXN];
Rule R[MAXM];
inline void Read(void){
cin>>n>>d>>(str+1)>>m;
for(reg int i=1;i<=m;++i)
R[i].Read();
return;
}
int cnt,head[MAXN<<1],to[MAXM<<1],Next[MAXM<<1];
inline void Add_Edge(reg int u,reg int v){
Next[++cnt]=head[u];
to[cnt]=v;
head[u]=cnt;
return;
}
bool vis[MAXN<<1];
int tim,dfn[MAXN<<1],low[MAXN<<1];
int top,S[MAXN<<1];
int Tarjan_cnt,color[MAXN<<1];
inline void Tarjan(reg int ID){
dfn[ID]=low[ID]=++tim;
vis[ID]=true;
S[++top]=ID;
for(reg int i=head[ID];i;i=Next[i])
if(!dfn[to[i]]){
Tarjan(to[i]);
low[ID]=min(low[ID],low[to[i]]);
}
else if(vis[to[i]])
low[ID]=min(low[ID],dfn[to[i]]);
if(dfn[ID]==low[ID]){
reg int To;
++Tarjan_cnt;
do{
To=S[top--];
vis[To]=false;
color[To]=Tarjan_cnt;
}while(To!=ID);
}
return;
}
int p[MAXN];
int pos[MAXN][3];
int Ans[MAXN<<1];
int partner[MAXN<<1];
inline void Solve(void){
cnt=0;
memset(head,0,sizeof(head));
memset(dfn,0,sizeof(dfn));
for(reg int i=1;i<=n;++i)
partner[partner[i]=n+i]=i;
for(reg int i=1;i<=m;++i)
if(p[R[i].i]!=R[i].hi){
reg int u=pos[R[i].i][R[i].hi],v=pos[R[i].j][R[i].hj];
if(p[R[i].j]==R[i].hj)
Add_Edge(u,partner[u]);
else
Add_Edge(u,v),Add_Edge(partner[v],partner[u]);
}
for(reg int i=1;i<=2*n;++i)
if(!dfn[i])
Tarjan(i);
for(reg int i=1;i<=n;++i)
if(color[i]!=color[i+n])
partner[color[i+n]]=color[i],partner[color[i]]=color[i+n];
else
return;
for(reg int i=1;i<=n;++i)
putchar('A'+Ans[i+(color[i]<color[i+n]?0:n)]);
exit(0);
return;
}
vector<int> V;
inline void Work(void){
for(reg int i=1;i<=n;++i)
switch(p[i]=str[i]-'a'){
case 0:{
pos[i][1]=i,pos[i][2]=i+n;
Ans[i]=1,Ans[i+n]=2;
break;
}
case 1:{
pos[i][0]=i,pos[i][2]=i+n;
Ans[i]=0,Ans[i+n]=2;
break;
}
case 2:{
pos[i][0]=i,pos[i][1]=i+n;
Ans[i]=0,Ans[i+n]=1;
break;
}
default:break;
}
for(int i=1;i<=n;++i)
if(p[i]>2)
V.push_back(i);
for(reg int i=0;i<(1<<d);++i){
for(reg int j=0;j<d;++j)
switch(p[V[j]]=((i>>j)&1)){
case 0:{
pos[V[j]][1]=V[j],pos[V[j]][2]=V[j]+n;
Ans[V[j]]=1,Ans[V[j]+n]=2;
break;
}
case 1:{
pos[V[j]][0]=V[j],pos[V[j]][2]=V[j]+n;
Ans[V[j]]=0,Ans[V[j]+n]=2;
break;
}
case 2:{
pos[V[j]][0]=V[j],pos[V[j]][1]=V[j]+n;
Ans[V[j]]=0,Ans[V[j]+n]=1;
break;
}
default:break;
}
Solve();
}
puts("-1");
return;
}
近期评论