AGC029C - Lexicographic constraints

记录我心路历程吧，这道小水题暴露出我很多问题。

给定 \(n\) 个字符串长度 \(a_i\) ，求字符集最小多大，才能构造出按字典序比较 \(s_1 < s_2 < \dots < s_n\)。

当 \(a_i < a_{i+1}\) 时，显然全补 \(0\) 就行。否则，是一个高精度 \(+1\)。二分字符集大小，判断行不行。

以下是我做题过程。

首先，除了二分部分，全部推出来了。但是加法的细节写烂了，各种没判。

然后没有特判字符集为 \(1\) 的情况，硬是跑了 1e9 差点T。（最后改改还是T了）

然后考虑贪心的过程，写了一个错的。在字符不够的时候新开一个，实际上会导致前面的浪费。

blog 写到最后发现还是一道sb题，就当水了一个 blog 吧。

#include <bits/stdc++.h>
const int MAXN = 500010;

int n, st[MAXN], col[MAXN], top;
void add() {
    if (st[top] > 1 && st[top - 1] != st[top] - 1) {
        st[top + 1] = st[top];
        col[top + 1] = col[top];
        --st[top]; ++top;
    }
    ++col[top];
}
int A[MAXN];
bool judge(int cnt) {
    int lst = 0;
    memset(st, 0, top + 1 << 2);
    memset(col, 0, top + 1 << 2);
    top = 0;
    for (int i = 1, t; i <= n; ++i) {
        t = A[i];
        if (lst < t) {
            if (!top || col[top] != 0) st[++top] = t, col[top] = 0;
            else st[top] = t;
        } else {
            int k = -1;
            while (st[top] > t) k = col[top], --top;
            if (st[top] != t) st[++top] = t, col[top] = k;
            if (cnt > 1) {
                add();
                while (top && col[top] >= cnt) {
                    int at = st[top]; --top;
                    if (st[top] + 1 != at)
                        st[++top] = at - 1;
                    add();
                }
            } else top = 0, col[0] = 1;
            if (col[0]) return false;
            if (st[top] != t) st[++top] = t, col[top] = 0;
        }
        lst = t;
    }
    return true;
}
int main() {
    std::ios_base::sync_with_stdio(false), std::cin.tie(0);
    std::cin >> n;
    for (int i = 1; i <= n; ++i) std::cin >> A[i];
    int l = 1, r = n, ans = 0;
    while (l <= r) {
        int mid = l + r >> 1;
        if (judge(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    std::cout << ans << std::endl;
    return 0;
}

AGC029C - Lexicographic constraints

原文：https://www.cnblogs.com/daklqw/p/11754056.html