P11447题解

Azure_F · 2024-12-21 17:50:39 · 题解

Update 24/12/25：被 Hack 了，更新下代码。

本题关键在于 \max\{S\}。

显然一个划分成的某个区间 [l, r] 内如果包含 x 个 \max\{S\} 且 S _ r = \max\{S\}，则 f\!\left(S _ {[l, r]}\right) = \max\{S\}\times x。

因为一个划分成的区间内 \max\{S\} 数量的减小会带来其他划分成的区间内 \max\{S\} 数量的增大。所以我们希望尽可能每个区间内的 \max\{S\} 数量相同，即 \max\{S\}\times\left\lceil\frac{\operatorname{cnt}(\max\{S\})}{k}\right\rceil 一定是 \max f(a _ i) 的前缀。

然后讨论 k 能否整除 \operatorname{cnt}(\max\{S\})，如果不可以，刚才所述即为答案；否则，说明最后一个 \max\{S\} 后面还有别的字符会加到答案的末尾。此时暴力计算即可。

不难发现暴力地求一个区间 [l, r] 内字典序最大的子序列的方法如下：

• 找到该区间里的最大值第一次出现的位置 p，将 S _ p 加入答案，然后把区间范围设为 [S, r]；
• 然后照此重复执行，直至 S > r。

记得特判 \operatorname{cnt}(\max\{S\}) < k 的情况，此时答案即为 \max\{S\}。

代码（赛时代码，很多地方可能写得都不是很优秀）：

#include<iostream>
#include<string>
#include<algorithm>
#include<climits>

const int N = 2e5 + 1;
int n, k; std::string s;

int x, y; char tree[N << 2];
char build(int i = 1, int l = 1, int r = n) {
    if(l == r) return tree[i] = s[l];

    int mid = (l + r) >> 1;
    return tree[i] = std::max(build(i << 1, l, mid), build((i << 1) + 1, mid + 1, r));
}
char query(int i = 1, int l = 1, int r = n) {
    if(x > r || y < l) return CHAR_MIN;
    if(x <= l && r <= y) return tree[i];

    int mid = (l + r) >> 1;
    return std::max(query(i << 1, l, mid), query((i << 1) + 1, mid + 1, r));
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0), std::cout.tie(0);

    std::cin >> n >> k >> s; s = " " + s;

    build(); x = 1, y = n; char maxc = query();
    int cntmax = 0, maxlastpos = 0;
    for(int i = n; i >= 1; --i) {
        if(s[i] == maxc) {
            ++cntmax;
            if(!maxlastpos) maxlastpos = i;
        }
    }

    if(cntmax < k) std::cout << maxc;
    else {
        int len = cntmax / k + (cntmax % k ? 1 : 0);
        while(len--) std::cout << maxc;
        if(cntmax % k == 0 && maxlastpos != n) {
            x = maxlastpos + 1, y = n;
            while(x <= y) {
                char get = query(); std::cout << get;
                for(int i = x; i <= y; ++i) {
                    if(s[i] == get) { x = i + 1; break; }
                    else if(i == y) x = n + 1;
                }
            }
        }
    }

    return 0;
}