LOJ2305 「NOI2017」游戏

「NOI2017」游戏

题目背景

狂野飙车是小 L 最喜欢的游戏。与其他业余玩家不同的是,小 L 在玩游戏之余,还精于研究游戏的设计,因此他有着与众不同的游戏策略。

题目描述

小 L 计划进行$n$场游戏,每场游戏使用一张地图,小 L 会选择一辆车在该地图上完成游戏。

小 L 的赛车有三辆,分别用大写字母ABC表示。地图一共有四种,分别用小写字母xabc表示。其中,赛车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 对游戏有一些特殊的要求,这些要求可以用四元组 $(i, h_i, j, h_j)$来描述,表示若在第$i$场使用型号为$h_i$的车子,则第$j$场游戏要使用型号为$h_j$的车子。

你能帮小 L 选择每场游戏使用的赛车吗?如果有多种方案,输出任意一种方案。如果无解,输出 “-1’’(不含双引号)。

输入输出格式

输入格式:

输入第一行包含两个非负整数$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$为字符abc,含义见题目描述。

输出格式:

输出一行。

若无解输出 “-1’’(不含双引号)。

若有解,则包含一个长度为$n$的仅包含大写字母ABC的字符串,表示小 L 在这$n$场游戏中如何安排赛车的使用。如果存在多组解,输出其中任意一组即可。

输入输出样例

输入样例#1: 复制
3 1
xcc
1
1 A 2 B
输出样例#1: 复制
ABA

说明

【样例1解释】

小 L 计划进行$3$场游戏,其中第$1$场的地图类型是x,适合所有赛车,第$2$场和第$3$场的地图是c,不适合赛车C

小 L 希望:若第$1$场游戏使用赛车A,则第$2$场游戏使用赛车B。那么为这$3$场游戏分别安排赛车ABA可以满足所有条件。若依次为$3$场游戏安排赛车为BBBBAA时,也可以满足所有条件,也被视为正确答案。但依次安排赛车为AABABC时,因为不能满足所有条件,所以不被视为正确答案。

LOJ2305 「NOI2017」游戏

xyz32768的题解

\(NOI2017 Day2 T1\)。\(2-SAT\)。

可以发现,除了x地图之外,其余的地图只适合两种赛车。而在这里,我们先假设所有的地图都适合且只适合两种赛车,这样就是\(2-SAT\)裸题了。

对于每场游戏用两个点\(i\)和\(i'\),分别表示第\(i\)场游戏使用该地图适合的第一种赛车和第二种赛车(举例:如果第\(i\)场游戏的地图不适合A赛车,那么点\(i\)表示第\(i\)场游戏使用B赛车,点\(i'\)表示第\(i\)场游戏使用C赛车)。

对于每个限制条件,设\(u\)为表示「第\(i\)场游戏使用型号为\(hi\)的赛车」的点(在第\(i\)场游戏的地图适合型号为\(hi\)的赛车的情况下),\(v\)为表示「第\(j\)场游戏使用型号为\(hj\)的赛车」的点(在第\(j\)场游戏的地图适合型号为\(hj\)的赛车的情况下),

那么,

如果第\(i\)场游戏的地图不适合型号为\(hi\)的赛车,那么不做任何操作。

如果第\(i\)场游戏的地图适合型号为\(hi\)的赛车,但第\(j\)场游戏的地图不适合型号为\(hj\)的赛车,那么建边\(u->u'\),表示如果第\(i\)场游戏使用了型号为\(hi\)的赛车则一定无解。

如果第\(i\)场游戏的地图适合型号为\(hi\)的赛车,第\(j\)场游戏的地图适合型号为\(hj\)的赛车,那么建边\(u->v\),表示如果第\(i\)场游戏使用了型号为\(hi\)的赛车则第\(j\)场游戏必须使用型号为\(hj\)的赛车,再建边\(v'->u'\),表示如果第\(j\)场游戏不使用型号为\(hj\)的赛车则第\(i\)场游戏不得使用型号为\(hi\)的赛车。

所有边都建完之后跑一遍\(Tarjan\)强连通分量缩点。对于任意一个\(i\),如果\(i\)和\(i'\)在同一个强连通分量里面,那么此时无解。

否则输出方案。\(2-SAT\)输出方案的方法为:先把缩点之后的新图进行拓扑排序,然后判断每个点\(i\),如果\(i\)所在强连通分量的拓扑序在\(i'\)所在的强连通分量的拓扑序之后,那么第\(i\)场游戏使用该地图适合的第一种赛车,否则使用第二种赛车。但是由于\(Tarjan\)求强连通分量就是按拓扑排序的逆序给出的,所以直接使用强连通分量编号判断即可。即如果\(bel[]\)为每个点的所在强连通分量编号,那么判断为:如果\(bel[i]<bel[i']\),那么使用该地图适合的第一种赛车,否则使用第二种赛车。

现在考虑x地图,考虑到只有8张x地图,如果假设它也只适合两种赛车,那么暴力枚举每个x地图不适合赛车A或不适合赛车B(因为不适合赛车A就是适合赛车BC,不适合赛车B就是适合赛车AC,这样就包含了ABC三种赛车),这样每种地图就都只适合两种赛车了。判断时,如果已经枚举遍了所有的\(2^d\)种状态都是无解,则原问题无解,否则输出任意一种方案。

复杂度\(O((n+m)*2^d)\)。

#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
    rg T data=0,w=1;rg char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-') w=-w;
    for(;isdigit(ch);ch=getchar()) data=data*10+ch-'0';
    return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;
using namespace std;

co int maxm=5e5+5,maxn=1e5+5,maxe=maxm*2;
co int lst[3][2]={{1,2},{0,2},{0,1}};
int n,D,m,c[maxn][2],pos[15],ban[maxn],ans[maxn];
int head[maxn*2],next[maxe],ver[maxe],tot;
char map[maxn];
struct data {int x,hx,y,hy;}q[maxm];
il void add(int x,int y){
    ver[++tot]=y,next[tot]=head[x],head[x]=tot;
}
int dfn[maxn*2],low[maxn*2],tim,stk[maxn*2],top,scc,blg[maxn*2];
bool ins[maxn];
void tarjan(int x){
    dfn[x]=low[x]=++tim;
    stk[++top]=x,ins[x]=1;
    for(int j=head[x];j;j=next[j]){
        if(!dfn[ver[j]]) tarjan(ver[j]),low[x]=min(low[x],low[ver[j]]);
        else if(ins[ver[j]]) low[x]=min(low[x],dfn[ver[j]]);
    }
    if(dfn[x]==low[x]){
        ++scc;
        do{
            ins[stk[top]]=0;
            blg[stk[top]]=scc;
        }while(stk[top--]!=x);
    }
}
int main(){
    read(n),read(D),scanf("%s",::map+1);
    read(m);
    for(int i=1;i<=m;++i){
        static char ch[2];
        read(q[i].x);
        scanf("%s",ch),q[i].hx=ch[0]-'A';
        read(q[i].y);
        scanf("%s",ch),q[i].hy=ch[0]-'A';
    }
    for(int i=1,_d=0;i<=n;++i){
        if(::map[i]=='x') pos[++_d]=i;
        else{
            ban[i]=::map[i]-'a';
            c[i][0]=lst[ban[i]][0],c[i][1]=lst[ban[i]][1];
        }
    }
    for(int s=0;s<1<<D;++s){
        for(int i=1;i<=D;++i){
            ban[pos[i]]=(s>>i-1)&1;
            c[pos[i]][0]=lst[ban[pos[i]]][0],c[pos[i]][1]=lst[ban[pos[i]]][1];
        }
        memset(head,0,sizeof head),tot=0;
        for(int i=1;i<=m;++i){
            if(ban[q[i].x]==q[i].hx) continue;
            if(ban[q[i].y]==q[i].hy){
                int a=c[q[i].x][1]==q[i].hx;
                add(q[i].x<<1|a,(q[i].x<<1|a)^1);
            }
            else{
                int a=c[q[i].x][1]==q[i].hx,b=c[q[i].y][1]==q[i].hy;
                add(q[i].x<<1|a,q[i].y<<1|b);
                add((q[i].y<<1|b)^1,(q[i].x<<1|a)^1);
            }
        }
        memset(dfn,0,sizeof dfn),tim=scc=0;
        for(int i=2;i<=(n<<1|1);++i)
            if(!dfn[i]) tarjan(i);
        bool flag=0;
        for(int i=1;i<=n;++i){
            if(blg[i<<1]==blg[i<<1|1]) {flag=1;break;}
            ans[i]=c[i][blg[i<<1|1]<blg[i<<1]];
        }
        if(flag) continue;
        for(int i=1;i<=n;++i) putchar('A'+ans[i]);
        return 0;
    }
    puts("-1");
    return 0;
}
上一篇:【BZOJ4942】[NOI2017]整数(分块)


下一篇:M1 Dock智能硬件环境搭建(MaixPy安装及使用)