洛谷 P3825 [NOI2017] 游戏 题解【2-SAT】【枚举】
点击量：249
复习一下 2-SAT，感觉核心还是记住了的。
题目背景
狂野飙车是小 L 最喜欢的游戏。与其他业余玩家不同的是，小 L 在玩游戏之余，还精于研究游戏的设计，因此他有着与众不同的游戏策略。
题目描述
小 L 计划进行 $n$ 场游戏，每场游戏使用一张地图，小 L 会选择一辆车在该地图上完成游戏。
小 L 的赛车有三辆，分别用大写字母 A、B、C 表示。地图一共有四种，分别用小写字母 x、a、b、c 表示。其中，赛车 A 不适合在地图 a 上使用，赛车 B 不适合在地图 b 上使用，赛车 C 不适合在地图 c 上使用，而地图 x 则适合所有赛车参加。适合所有赛车参加的地图并不多见，最多只会有 $d$ 张。
$n$ 场游戏的地图可以用一个小写字母组成的字符串描述。例如：$S=$
xaabxcbc表示小 L 计划进行 $8$ 场游戏，其中第 $1$ 场和第 $5$ 场的地图类型是 x，适合所有赛车，第 $2$ 场和第 $3$ 场的地图是 a，不适合赛车 A，第 $4$ 场和第 $7$ 场的地图是 $b$，不适合赛车 B，第 $6$ 场和第 $8$ 场的地图是 c，不适合赛车 C。小 L 对游戏有一些特殊的要求，这些要求可以用四元组 $\left(i,h_i,j,h_j\right)$ 来描述，表示若在第 $i$ 场使用型号为 $h_i$ 的车子，则第 $j$ 场游戏要使用型号为 $h_j$ 的车子。
你能帮小 L 选择每场游戏使用的赛车吗？如果有多种方案，输出任意一种方案。如果无解，输出 “$-1$’’（不含双引号）。
输入格式
从文件
game.in中读入数据。输入第一行包含两个非负整数 $n,d$。
输入第二行为一个字符串 $S$。
$n,d,S$ 的含义见题目描述，其中 $S$ 包含 $n$ 个字符，且其中恰好 $d$ 个为小写字母 x。
输入第三行为一个正整数 $m$ ，表示有 m 条用车规则。接下来 $m$ 行，每行包含一个四元组 $i,h_i,j,h_j$ ，其中 $i,j$ 为整数，$h_i,h_j$ 为字符 a、b 或 c，含义见题目描述。输出格式
输出到文件
game.out中。输出一行。
若无解输出 “$-1$’’（不含双引号）。
若有解，则包含一个长度为 $n$ 的仅包含大写字母 A、B、C 的字符串，表示小 L 在这 $n$ 场游戏中如何安排赛车的使用。如果存在多组解，输出其中任意一组即可。
样例 1 解释
小 L 计划进行 $3$ 场游戏，其中第 $1$ 场的地图类型是 x，适合所有赛车，第 $2$ 场和第 $3$ 场的地图是 c，不适合赛车 C。
小 L 希望：若第 $1$ 场游戏使用赛车 A，则第 $2$ 场游戏使用赛车 B。
那么为这 $3$ 场游戏分别安排赛车 A、B、A 可以满足所有条件。
若依次为 $3$ 场游戏安排赛车为 BBB 或 BAA 时，也可以满足所有条件，也被视为正确答案。但依次安排赛车为 AAB 或 ABC 时，因为不能满足所有条件，所以不被视为正确答案。
测试点编号 $n$ $d$ $m$ 其他性质 $1$ $\le 2$ $0$ $\le 4$ 无 $2$ $\le 2$ $\le n$ $\le 4$ 无 $3$ $\le 5$ $0$ $\le 10$ 无 $4$ $\le 5$ $\le n$ $\le 10$ 无 $5$ $\le 10$ $0$ $\le 20$ 无 $6$ $\le 10$ $\le n$ $\le 20$ 无 $7$ $\le 20$ $0$ $\le 40$ S 中只包含 c $8$ $\le 20$ $0$ $\le 40$ 无 $9$ $\le 20$ $\le 8$ $\le 40$ S 中只包含 x 或 c $10$ $\le 20$ $\le 8$ $\le 40$ 无 $11$ $\le 100$ $0$ $\le 200$ S 中只包含 c $12$ $\le 100$ $0$ $\le 200$ 无 $13$ $\le 100$ $\le 8$ $\le 200$ S 中只包含 x 或 c $14$ $\le 100$ $\le 8$ $\le 200$ 无 $15$ $\le 5000$ $0$ $\le 10000$ 无 $16$ $\le 5000$ $\le 8$ $\le 10000$ S 中只包含 x 或 c $17$ $\le 5000$ $\le 8$ $\le 10000$ 无 $18$ $\le 50000$ $0$ $\le 100000$ 无 $19$ $\le 50000$ $\le 8$ $\le 100000$ S 中只包含 x 或 c $20$ $\le 50000$ $\le 8$ $\le 100000$ 无
题解：
对于有确切的字母 abc 的地图，我们可以拆点考虑，但是题目给出的条件貌似都是单向的，不满足 2-SAT 中都有“逆否命题”的条件。
实际上我们考虑，（定义见题目描述）如果第 $i$ 个地图用了 $h_i$ 类型的车，那么 $j$ 地图要使用 $h_j$ 型号的车；但是由于每个地图一定要用一辆车，当 $j$ 地图没有用 $h_j$ 车时，一定用了另一种可用的车，此时第 $i$ 张地图就不能用 $h_i$ 车了。因此是有对称边的。
此时考虑怎么处理 x 的地图。因为如果有合法的方案，每个地图一定有一种车，可能是 A，B 或者是 C。此时可以枚举这些位置开什么车，判断合法后，剩下的跑 2-SAT，时间复杂度 $O(3^d\cdot(n-d))$。
实际上我们如果枚举地图类型而不是车的类型，则只需要枚举两种。当地图为 a 时，可以开 A，B 车；当地图为 b 时，可以开 A，C 车。只要存在合法的情况，就一定会被这样枚举到，这时时间复杂度为 $O(2^d\cdot n)$。
如果条件约束中，地图 $j$ 不能选 $h_j$，那么需要连一条边到地图 $i$ 中 $h_i$ 所在的点对面；如果地图 $i$ 不能选 $h_i$，则不需要连边。即不会产生那样的答案。
当然对于所有 2-SAT 问题都会有自己约束自己的问题，此时直接连一条边就可以了。
Code：
#include<cstdio>
#include<cstring>
struct edge
{
int n,nxt;
edge(int n,int nxt)
{
this->n=n;
this->nxt=nxt;
}
edge(){}
}e[200100];
int head[100100],ecnt=-1;
void add(int from,int to)
{
e[++ecnt]=edge(to,head[from]);
head[from]=ecnt;
}
int dfn[100100],low[100100],cnt;
int stk[100100],tp=0,del[100100],dcnt=0;
bool in[100100];
void tarjan(int x)
{
dfn[x]=++cnt;
low[x]=dfn[x];
in[x]=1;
stk[++tp]=x;
for(int i=head[x];~i;i=e[i].nxt)
if(!dfn[e[i].n])
{
tarjan(e[i].n);
low[x]=low[x]<low[e[i].n]?low[x]:low[e[i].n];
}
else if(in[e[i].n])
low[x]=low[x]<dfn[e[i].n]?low[x]:dfn[e[i].n];
if(dfn[x]==low[x])
{
++dcnt;
do
{
in[stk[tp]]=0;
del[stk[tp--]]=dcnt;
}while(stk[tp+1]!=x);
}
}
struct lim
{
int a,b;
char x,y;
}l[100100];
char s[50010],one[256],two[256],op[100];
int X[10];
int main()
{
one['a']='B',two['a']='C';
one['b']='A',two['b']='C';
one['c']='A',two['c']='B';
int n,m,d;
scanf("%d%d",&n,&d);
scanf("%s",s+1);
cnt=0;
for(int i=1;i<=n;++i)
if(s[i]=='x')
X[cnt++]=i;
scanf("%d",&m);
for(int i=1;i<=m;++i)
{
scanf("%d",&l[i].a);
scanf("%s",op);
l[i].x=op[0];
scanf("%d",&l[i].b);
scanf("%s",op);
l[i].y=op[0];
}
cnt=0;
for(int t=0;t<(1<<d);++t)
{
for(int i=0;i<d;++i)
if((t>>i)&1)
s[X[i]]='a';
else
s[X[i]]='b';
memset(head,-1,sizeof(head));
memset(dfn,0,sizeof(dfn));
ecnt=-1;
for(int i=1;i<=m;++i)
{
if(l[i].x+32==s[l[i].a])
continue;
else
{
if(l[i].y+32==s[l[i].b])
{
if(l[i].x==one[s[l[i].a]])
add(l[i].a,l[i].a+n);
else
add(l[i].a+n,l[i].a);
}
else
{
if(l[i].x==one[s[l[i].a]])
{
if(l[i].y==one[s[l[i].b]])
add(l[i].a,l[i].b),add(l[i].b+n,l[i].a+n);
else
add(l[i].a,l[i].b+n),add(l[i].b,l[i].a+n);
}
else
{
if(l[i].y==one[s[l[i].b]])
add(l[i].a+n,l[i].b),add(l[i].b+n,l[i].a);
else
add(l[i].a+n,l[i].b+n),add(l[i].b,l[i].a);
}
}
}
}
for(int i=1;i<=2*n;++i)
if(!dfn[i])
tarjan(i);
int flag=0;
for(int i=1;i<=n;++i)
if(del[i]==del[i+n])
flag=1;
if(flag)
continue;
for(int i=1;i<=n;++i)
if(del[i]<del[i+n])
printf("%c",one[s[i]]);
else
printf("%c",two[s[i]]);
return 0;
}
puts("-1");
return 0;
}
说点什么