题解：P15119 [ICPC 2024 LAC] Expanding STACKS!

· · 题解

前言：真有这样的店吗，我好想去！

题意

题目描述得非常清晰了，我来大概总结一下。
输入给出顾客的出入情况，顾客后进先出。有两个队伍可以站，分别对应 G 和 S，要求我们给出合法的分配方式，否则输出字符 "*"。

思路

很明显，由于后进先出，两个队伍就是两个栈。接下来，我们又可以把顾客的在队时间看成一个区间。所以，若要合法，我们就要使栈中的区间不交叉。 ::::info[什么情况不交叉呢？]

  1. 完全不在一起，即满足 x_{出队}<y_{入队}。
  2. 嵌套，即第 x 人和 第 y 人满足 x_{出队}<y_{出队} 并且 x_{入队}>y_{出队}。 ::::
    那么，聪明的小朋友就要问了，相交呢？
    很明显，若相交，他们肯定不能站在一个栈中，就要去另一边。我们可以通过对区间染色的方式来标记人所处的队列。
    首先先得处理顾客之间是否相交的问题，枚举顾客两两讨论，判断区间是否相交，若相交，可以用一个 vector 数组记录两人区间相交。
    然后，再枚举一遍顾客，若未染色，进行染色，并为与之区间相交的顾客染不同的颜色并继续访问其相交顾客（有点绕？代码里面会有注释，可能容易理解一些）。
    最后不同的颜色输出 G 和 S 即可。 ::::info[那什么是无解情况呢？] 若顾客对区间相交的顾客染色时，发现对方已被染色且颜色相同，说明无解了。 ::::

    代码

    #include<bits/stdc++.h>
using namespace std;
int n;
int man[1005][2];//记录顾客的出入时间 
vector<int> sp[1005];
int clr[1005];
bool flag=1;
bool jiao_cha(int x,int y){
int lx=man[x][0],rx=man[x][1];
int ly=man[y][0],ry=man[y][1];
//完全分离无交集
if(rx<ly||ry<lx){
    return 0;
}
//互相嵌套包含
if((lx<ly&&ry<rx)||(ly<lx&&rx<ry)){
    return 0;
}
//交叉互斥
return 1;
}
bool pt(int x){//返回false说明无解 
queue<int> q;
q.push(x); 
if(!clr[x]){//未染色 
    clr[x]=1;
}
while(!q.empty()){
    int now=q.front();
    q.pop();
    for(int v : sp[now]){//染色与之区间相交的顾客 
        if(!clr[v]){
            clr[v]=(clr[now]==1?2:1);
            q.push(v);//再讨论 
        }else if(clr[v]==clr[now]){//无解情况 
            return 0;
        }
    }
}
return 1;
}
int main(){
ios::sync_with_stdio(0);//关流，数据小可有可无 
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=2*n;++i){
    int po;
    cin>>po;
    if(po>0){//进入时间 
        man[po][0]=i;
    }else{//出去时间 
        man[-po][1]=i;
    }
}
for(int i=1;i<=n;++i){
    for(int j=i+1;j<=n;++j){
        if(jiao_cha(i,j)){//判断是否区间相交 
            sp[i].push_back(j);
            sp[j].push_back(i);
        }
    }
}
for(int i=1;i<=n;++i){
    if(clr[i]==0){
        if(!pt(i)){
            flag=0;//标记无解 
            break;
        }
    }
}
if(flag){
    for(int i=1;i<=n;++i){
        cout<<(clr[i]==1?'G':'S');
    }
}else{
    cout<<'*';
}
return 0;
}

    求管理大大过一下，辛苦啦！qwq