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