P1063 · OFFICIAL SOLUTION

P1063 康神开播了官方题解

Gioush OJ · P1063 康神开播了

【题意简述】

每次可以从当前字符串的左端或右端取出一个字符；若当前串形如 $ABA^R$ ，还可以把 $A$ 加入答案，同时删去左右两侧的 $A$ 与 $A^R$ 。求最终答案的字典序最小值。

【正解】

维护当前尚未处理的区间 $[l,r]$ 。若 $S_l\ne S_r$ ，所有合法操作接下来输出的第一个字符只能从两端产生，因此直接取较小的一端。

下面考虑 $S_l=S_r=x$ 。设左端连续的 $x$ 长度为 $L$ ，右端连续的 $x$ 长度为 $R$ ；越过两段后遇到的字符分别为 $a,b$ 。若整个区间都由 $x$ 构成，最优答案显然是

x^{\lfloor (r-l+1)/2\rfloor+1}.

否则只需比较 $a,b$ 与 $x$ ：

若 $a>x$ 且 $b>x$ ，分别使用前两类操作取完左右两端字符段，共输出 $L+R$ 个 $x$ ；
若 $a<x$ 且 $b<x$ ，输出 $\min(L,R)$ 个 $x$ ，并从两端各删去这么多个 $x$ ；
其余情况下 $a,b$ 分居 $x$ 两侧。若 $a<b$ ，输出左侧的 $L$ 个 $x$ 并删去左段；否则对称地处理右段。

预处理每个位置所在等值段的左右端点，就能在 $\mathcal O(1)$ 时间取得 $L,R,a,b$ 。每次循环至少删去一个字符，所以总复杂度为线性。

【正确性证明】

若两端字符不同，选择较大者会在答案的第一个不同位置立刻变劣，因此取较小端是唯一可能的最优选择。

若两端同为 $x$ ，在遇到非 $x$ 字符前，任意方案产生的前缀都只含 $x$ 。第三种操作中任意长度的 $A$ ，都等价于连续执行 $|A|$ 次 $A$ 为单字符的成对收缩：原操作要求中间的 $B$ 非空，所以逐字符收缩的每一步都合法；反向把这些收缩合并也显然合法。因此这里只需考虑“单端取出一个 $x$ ”和“输出一个 $x$ 并成对删去两端 $x$ ”。方案优劣由输出多少个 $x$ 后第一个实际输出的非 $x$ 字符决定。

当 $a,b>x$ 时，若使用一次成对收缩，可以把它拆成依次从两端各取一个 $x$ ；这样在首次暴露大于 $x$ 的字符前会多得到一个 $x$ ，字典序严格更小。因此最优方案不做成对收缩，而是分别取完两端的 $x$ ，共输出 $L+R$ 个 $x$ ；
当 $a,b<x$ 时，首次暴露小于 $x$ 的字符前至少要输出 $\min(L,R)$ 个 $x$ ，连续成对收缩恰好达到这个下界，所以输出 $\min(L,R)$ 个 $x$ 后从两端各删去相同数量；
当 $a,b$ 分居 $x$ 两侧时，第一个实际输出的非 $x$ 字符必须来自较小的一侧。即使较大侧的字符 $b$ 先成为端点，只要另一端仍为 $x$ ，就有 $x<b$ ，最优方案不会输出 $b$ ；较小侧的 $a$ 成为端点后又有 $a<b$ ，所以首个非 $x$ 输出仍为 $a$ 。若较小字符来自左侧，至少要消耗左侧的 $L$ 个 $x$ ，而每次操作至多消耗一个左端 $x$ ，故至少输出 $L$ 个 $x$ ；全部从左端取出恰好达到下界。期间若成对删去右端 $x$ ，只会提前丢掉仍小于 $b$ 的 $x$ ，不会更优。右侧较小时完全对称。

若当前区间全部由 $x$ 构成，成对收缩能最大程度减少答案长度；但题目要求中间串 $B$ 非空，所以剩两个字符时不能继续收缩。奇数长度最终留下一个字符，偶数长度最终留下两个字符，答案长度均为 $\lfloor (r-l+1)/2\rfloor+1$ 。

四种情况覆盖所有可能。每一步都得到所有合法方案中字典序最小的下一段，删去该段后问题仍与原问题同型；由归纳法，算法得到全局字典序最小答案。

【复杂度】

每个字符至多被预处理和删除各一次，时间复杂度为 $\mathcal O(|S|)$ ，空间复杂度为 $\mathcal O(|S|)$ 。

【参考代码】

1#include <algorithm>2#include <cstdio>3#include <cstring>4#include <string>5 6const int MaxN = 500010;7 8char S[MaxN];9int Left[MaxN], Right[MaxN];10 11int main() {12    int c, T;13    scanf("%d%d", &c, &T);14    while (T--) {15        scanf("%s", S + 1);16        int n = (int)strlen(S + 1);17        Left[1] = 1;18        for (int i = 2; i <= n; ++i)19            Left[i] = S[i] == S[i - 1] ? Left[i - 1] : i;20        Right[n] = n;21        for (int i = n - 1; i >= 1; --i)22            Right[i] = S[i] == S[i + 1] ? Right[i + 1] : i;23 24        std::string Ans;25        int l = 1, r = n;26        while (l <= r) {27            if (S[l] != S[r]) {28                if (S[l] < S[r]) Ans.push_back(S[l++]);29                else Ans.push_back(S[r--]);30                continue;31            }32 33            char x = S[l];34            int p = std::min(Right[l], r);35            int q = std::max(Left[r], l);36            if (p >= q) {37                Ans.append((r - l + 1) / 2 + 1, x);38                break;39            }40 41            int L = p - l + 1, R = r - q + 1;42            char a = S[p + 1], b = S[q - 1];43            if (a > x && b > x) {44                Ans.append(L + R, x);45                l = p + 1;46                r = q - 1;47            } else if (a < x && b < x) {48                int d = std::min(L, R);49                Ans.append(d, x);50                l += d;51                r -= d;52            } else if (a < b) {53                Ans.append(L, x);54                l = p + 1;55            } else {56                Ans.append(R, x);57                r = q - 1;58            }59        }60        printf("%s\n", Ans.c_str());61    }62    return 0;63}