2021牛客多校9.F.Train Wreck 构造

😊 | Powered By HeartFireY

Problem Description

题目大意：给定一个括号序列，"(“表示火车进站，”)"表示火车出站。火车具有不同的颜色，颜色的类型由题目给定。每个时刻火车站内的火车颜色可以视为一个序列。现在要求你求一个火车进站的顺序，使得每个时刻的颜色序列都不相同。

实际上就是给定出入栈的序列，然后使每次入栈之后的序列各不相同。首先来看样例 2 2 2​的入栈火车颜色图解

考虑如何构造这些不同的序列。我们可以发现：实际上所有序列构成一个森林，森林的每棵树上存储操作序列。为了使序列满足题意，我们需要使每个非叶子节点的子树的点颜色不同。

那么我们沿着这个思路继续，为了保证每个非叶子节点的子树颜色不同，我们需要在回溯的时候对子节点进行染色。这里引用yezzz.的一组样例并加颜色数据：

11
((())()((())))()(()())
4 4 4 2 1 3 5 5 6 6 4

按照以上括号序列，我们逐个节点建树，首先建到 3 3 3节点后碰到 ′ ) ′ ')' ′)′开始回溯， 3 3 3节点无子节点，因此染色操作直接 p a s s pass pass，然后继续，又碰到一个 ′ ) ′ ')' ′)′，继续回溯到 2 2 2，执行染色操作，将 2 2 2​的子节点染一次色​​。这里染色要特别说明一下，我们在这里根据贪心的思想，从数目最多的颜色开始染色，染到子树全部染色为止。

然后继续遍历，碰到 ′ ′ ( ′ ′ ''('' ′′(′′​，那么继续往下走 . . . ... ...​如此重复这个过程，直到整个森林全部被染色完毕。

那么代码怎么写？我们可以用一个栈暂存建树过程中每一层的节点，染色后出栈；对于染色的过程，将所有颜色出现的次数和颜色代号存入优先队列，染色时根据节点数将颜色依次出队，如果颜色不够那么说明不符合题目要求，输出“NO”，然后再用一个栈暂存出队的节点，减去染色的一次后再存回去。如下：第一棵树的染色步骤如下描述：

Accepted Code

#include 
#define pii pair
using namespace std;

const int N = 1e3 + 10;
int c[N], ans[N], top = 0;

priority_queue q;
vector vec[N];

inline void work(vector a){
    vector tmp;
    for(auto x : a){
        if(q.empty()){
            cout  x; c[x]++;
    }
    for(int i = 1; i