P4789 [BalkanOI 2018] Zalmoxis 题解

· · 题解

题目大意分析

题目描述说的一坨。简单分析一下可以将题目理解为在一个长为 n 序列中加入 k 个数，只要有两个相邻的数相等就将它们合成一个数，设这两个数是 x，合并后变为 x+1。最后我们希望加完 k 个数之后使这个序列合并成 [30]。

AC之路（思路讲解）

这个题目一眼构造题，但是怎么构造正确序列呢？

不难看出这道题可以用单调栈构造。因为我们发现，如果有一个数无法合并，且左边和它紧邻的数和右边和它紧邻的数都比他大，这个数就没法合并了（还是很好看出来的）。我们可以假设自己只能在序列末放数，维护一个单调递减的栈，那就好维护啦（而且题目保证有解，我们只需要维护而不是纠错）。

既然我们设在序列末尾插入数，我们不妨设在以 i 结尾时的序列末尾插入数，插入的数使用 vector 维护。

单调栈里只剩一个数了，但没到 30，此时我们只需要不断往后加数给它凑到 30，所以 i=n 时特判！

它要求插入 k 个数？那也没关系，我们可以使用递归把我们加入的数拆开输出，直到插够 k 个数为止。

AC代码

写的一坨，将就看吧（其实我还有更丑的代码）。

#include<cstdio>
#include<vector>
#define LF putchar(10)
#define SP putchar(32)
const int N = 1e6 + 5;
template<typename T>void read(T& x) {
    x = 0;
    char ch = getchar();
    while (ch < 48 || ch > 57)ch = getchar();
    while (ch > 47 && ch < 58)x = (x << 3) + (x << 1) + (ch & 15), ch = getchar();
}
template<typename T, typename... Args>void read(T& x, Args&... args) {
    read(x);
    read(args...);
}
template<typename T>void write(T x) {
    if (x < 0) {
        putchar(45);
        x = -x;
    }
    if (x > 9)write(x / 10);
    putchar(x % 10 | 48);
}
int n, m, tp, sum;
int a[N], stk[N];
std::vector<int> G[N];
void f(int x) {
    if (x == 0) {
        putchar(48);
        SP;
    } else if (sum < m) {
        sum++;
        f(x - 1);
        f(x - 1);
    } else {
        write(x);
        SP;
    }
}
int main() {
    read(n, m);
    for (int i = 1; i <= n; i++) {
        read(a[i]);
        if (tp && a[i] == stk[tp]) {
            stk[tp]++;
            while (tp > 1 && stk[tp] == stk[tp - 1])
                stk[--tp]++;
        } else if (tp && a[i] > stk[tp]) {
            G[i - 1].push_back(stk[tp]);
            stk[tp]++;
            while (tp > 1 && stk[tp] == stk[tp - 1])
                stk[--tp]++;
            while (a[i] > stk[tp]) {
                G[i - 1].push_back(stk[tp]++);
                while (tp > 1 && stk[tp] == stk[tp - 1])
                    stk[--tp]++;
            }
            stk[++tp] = a[i];
            while (tp > 1 && stk[tp] == stk[tp - 1])
                stk[--tp]++;
        } else
            stk[++tp] = a[i];
        if (i == n) {
            while (stk[tp] < 30) {
                while (tp > 1 && stk[tp] != stk[tp - 1] || (tp == 1 && stk[tp] < 30))
                    G[n].push_back(stk[tp]++);
                while (tp > 1 && stk[tp] == stk[tp - 1])
                    stk[--tp]++;
            }
        }
    }
    for (int i = 1; i <= n; i++)
        sum += G[i].size();
    for (int i = 1; i <= n; i++) {
        write(a[i]);
        SP;
        if (G[i].size())
            for (int p : G[i])
                f(p);
    }
    return 0;
}