洛谷 P3825 [NOI2017] 游戏 题解【2-SAT】【枚举】

作者: wjyyy 分类: 2-SAT,tarjan,枚举,解题报告 发布时间: 2019-04-06 21:02

点击量:70

复习一下 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 的地图。因为如果有合法的方案,每个地图一定有一种车,可能是 AB 或者是 C。此时可以枚举这些位置开什么车,判断合法后,剩下的跑 2-SAT,时间复杂度 $O(3^d\cdot(n-d))$。

实际上我们如果枚举地图类型而不是车的类型,则只需要枚举两种。当地图为 a 时,可以开 AB 车;当地图为 b 时,可以开 AC 车。只要存在合法的情况,就一定会被这样枚举到,这时时间复杂度为 $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;
}

说点什么

avatar
  Subscribe  
提醒
/* */