P3825 [NOI2017]游戏
斯德哥尔摩
2018-08-01 11:13:55
[P3825 [NOI2017]游戏](https://www.luogu.org/problemnew/show/P3825)
这题好像是$NOI2017-DAY2-T1$，吓得我瑟瑟发抖不敢做。。。
艰难地看完题目，嗯？有限制条件的$2-SAT$？
想了想，好像可行。
然而$2-SAT$不会敲。。。
可以发现，除了$x$地图之外，其余的地图只适合两种赛车。
我们先假设所有的地图都适合且只适合两种赛车，这样就是$2-SAT$裸题了。
对于每场游戏用两个点$i$和$i'$，分别表示第$i$场游戏使用该地图适合的第一种赛车和第二种赛车。
煮个栗子：如果第$i$场游戏的地图不适合$A$赛车，那么点$i$表示第$i$场游戏使用$B$赛车，点$i'$表示第$i$场游戏使用$C$赛车。
对于每个限制条件，设$u$表示第$i$场游戏使用型号为$h_i$的赛车的点（在第$i$场游戏的地图适合型号为$h_i$的赛车的情况下），$v$为表示第$j$场游戏使用型号为$h_j$的赛车的点（在第$j$场游戏的地图适合型号为$h_j$的赛车的情况下）。
那么分类讨论：
1. 如果第$i$场游戏的地图不适合型号为$h_i$的赛车：
不做任何操作。
2. 如果第$i$场游戏的地图适合型号为$h_i$的赛车，但第$j$场游戏的地图不适合型号为$h_j$的赛车：
建边$u->u'$，表示如果第$i$场游戏使用了型号为$h_i$的赛车则一定无解。
3. 如果第$i$场游戏的地图适合型号为$h_i$的赛车，第$j$场游戏的地图适合型号为$h_j$的赛车：
建边$u->v$，表示如果第$i$场游戏使用了型号为$h_i$的赛车则第$j$场游戏必须使用型号为$h_j$的赛车。
再建边$v'->u'$，表示如果第$j$场游戏不使用型号为$h_j$的赛车则第$i$场游戏不得使用型号为$h_i$的赛车。
当所有边都建完之后跑一遍$Tarjan$强连通分量缩点。
若存在一对$i$和$i'$在同一个强连通分量里面——无解。
否则输出方案。
$2-SAT$输出方案的方法：
先把缩点之后的新图进行拓扑排序，然后判断每个点$i$，如果$i$所在强连通分量的拓扑序在$i'$所在的强连通分量的拓扑序之后，那么第$i$场游戏使用该地图适合的第一种赛车，否则使用第二种赛车。
但是我不想再拓扑排序了，怎么办？
这里，由于$Tarjan$求强连通分量就是按拓扑排序的逆序给出的，所以直接使用强连通分量编号判断即可。
即：若$colour[i]<colour[i']$，那么使用该地图适合的第一种赛车，否则使用第二种赛车。（$colour[i]$为每个点的所在强连通分量的染色编号。）
好神奇！
现在考虑$x$地图，考虑到最多只有$8$张$x$地图，如果假设它也只适合两种赛车，那么暴力枚举每个$x$地图不适合赛车$A$或不适合赛车$B$。
因为不适合赛车$A$就是适合赛车$B,C$，不适合赛车$B$就是适合赛车$A,C$，这样就包含了$A,B,C$三种赛车。
这样每种地图就都只适合两种赛车了。
判断时，如果已经枚举遍了所有的$2^d$种状态都是无解，则原问题无解，否则输出任意一种方案。
复杂度？当然$O((n+m)* 2^d)$。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define MAXN 200010
using namespace std;
int n,m,k;
int pos[MAXN];
char s[MAXN],choose[MAXN];
bool flag=false;
struct Limit{
int i,j;
char x,y;
}a[MAXN];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
namespace Tarjan{
int c=1,d=1,top=1,num=0;
int cstack[MAXN],head[MAXN],deep[MAXN],low[MAXN],colour[MAXN];
bool vis[MAXN];
struct Graph{
int next,to;
}edge[MAXN];
inline void add(int x,int y){
edge[c].to=y;edge[c].next=head[x];head[x]=c++;
}
void dfs(int x){
deep[x]=low[x]=d++;
vis[x]=true;
cstack[top++]=x;
for(int i=head[x];i;i=edge[i].next){
int v=edge[i].to;
if(!deep[v]){
dfs(v);
low[x]=min(low[x],low[v]);
}
else if(vis[v])low[x]=min(low[x],deep[v]);
}
if(low[x]==deep[x]){
num++;
do{
colour[cstack[top-1]]=num;
vis[cstack[top-1]]=false;
}while(cstack[--top]!=x);
}
}
inline int point(int x){return (x>n?(x-n):(x+n));}
inline int change(int x,char ch){
if(s[x]=='a')return (ch=='B'?x:(x+n));
if(s[x]=='b'||s[x]=='c')return (ch=='A'?x:(x+n));
if(ch=='C')return (x+n);
return x;
}
void init(){
c=d=top=1;
num=0;
memset(head,0,sizeof(head));
memset(deep,0,sizeof(deep));
memset(low,0,sizeof(low));
memset(colour,0,sizeof(colour));
}
bool solve(){
init();
for(int i=1;i<=m;i++){
if(s[a[i].i]!='x'&&s[a[i].j]!='x'){
if(a[i].x==s[a[i].i]-32)continue;
int u=change(a[i].i,a[i].x);
if(a[i].y==s[a[i].j]-32)add(u,point(u));
else{
int v=change(a[i].j,a[i].y);
add(u,v);
add(point(v),point(u));
}
}
else{
int x=pos[a[i].i],y=pos[a[i].j];
if(s[a[i].i]=='x'&&s[a[i].j]=='x'){
if(a[i].x==choose[x])continue;
int u=change(a[i].i,a[i].x);
if(a[i].y==choose[y])add(u,point(u));
else{
int v=change(a[i].j,a[i].y);
add(u,v);
add(point(v),point(u));
}
}
else if(s[a[i].i]=='x'&&s[a[i].j]!='x'){
if(a[i].x==choose[x])continue;
int u=change(a[i].i,a[i].x);
if(a[i].y==s[a[i].j]-32)add(u,point(u));
else{
int v=change(a[i].j,a[i].y);
add(u,v);
add(point(v),point(u));
}
}
else{
if(a[i].x==s[a[i].i]-32)continue;
int u=change(a[i].i,a[i].x);
if(a[i].y==choose[y])add(u,point(u));
else{
int v=change(a[i].j,a[i].y);
add(u,v);
add(point(v),point(u));
}
}
}
}
for(int i=1;i<=(n<<1);i++)if(!deep[i])dfs(i);
for(int i=1;i<=n;i++)if(colour[i]==colour[i+n])return false;
for(int i=1;i<=n;i++){
if(colour[i]<colour[i+n]){
if(s[i]=='a')printf("B");
else if(s[i]=='b'||s[i]=='c')printf("A");
else if(choose[pos[i]]=='A')printf("B");
else printf("A");
}
else{
if(s[i]=='a'||s[i]=='b')printf("C");
else if(s[i]=='c')printf("B");
else if(choose[pos[i]]=='A')printf("C");
else printf("B");
}
}
return true;
}
}
void dfs(int x){
if(flag)return;
if(x>k){
if(!flag)flag=Tarjan::solve();
if(flag)return;
return;
}
choose[x]='A';dfs(x+1);
if(flag)return;
choose[x]='B';dfs(x+1);
return;
}
void work(){
dfs(1);
if(!flag)printf("-1\n");
}
void init(){
char ch[2];
n=read();k=read();
scanf("%s",s+1);
for(int i=1,j=1;i<=n;i++)if(s[i]=='x')pos[i]=j++;
m=read();
for(int i=1;i<=m;i++){
a[i].i=read();scanf("%s",ch);
a[i].x=ch[0];
a[i].j=read();scanf("%s",ch);
a[i].y=ch[0];
}
}
int main(){
init();
work();
return 0;
}
```