LOJ2305 「NOI2017」游戏

2024-03-28 22:02:22

「NOI2017」游戏

题目背景

狂野飙车是小 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 对游戏有一些特殊的要求，这些要求可以用四元组 $(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$为字符a、b或c，含义见题目描述。

输出格式：

输出一行。

若无解输出 “-1’’（不含双引号）。

若有解，则包含一个长度为$n$的仅包含大写字母A、B、C的字符串，表示小 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$场游戏分别安排赛车A、B、A可以满足所有条件。若依次为$3$场游戏安排赛车为BBB或BAA时，也可以满足所有条件，也被视为正确答案。但依次安排赛车为AAB或ABC时，因为不能满足所有条件，所以不被视为正确答案。

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;
}

码农公寓