题目

CF2125F。

思路

首先，设 ∣s∣=m|s|=m，那么能够凑出的 docker 数量最多是 ⌊m6⌋\lfloor\frac{m}{6}\rfloor，记 mx=⌊m6⌋mx=\lfloor \frac{m}{6}\rfloor，其次求出原先出现 docker 的次数 rawraw。

因此，若 l>mxl>mx，这条 [l,r][l,r] 是无效的，可以直接忽略。类似，若 r≥mxr\ge mx，直接令 r=mxr=mx 即可。

然后，给 [l,r][l,r] 区间 +1+1，这可以通过差分实现，记 cic_i 为加完这些 11 后的值。

处理完所有的 [l,r][l,r] 后，枚举 1∼mx1\sim mx 求出 cic_i 最大值 mxpeoplemxpeople，并且找到那些取最大值的 ii。

如果 i≤rawi\le raw，那么我们需要破坏 raw−iraw-i 个 docker，替换任意一个字母即可，答案用 raw−iraw-i 更新。

如果 i>rawi>raw，显然 ii 最小时，需要的操作次数最小，因为 ii 更大一定可以通过撤销若干次操作得到更小的那个 ii 的操作次数。

考虑一个朴素的 dpdp，设 dpi,jdp_{i,j} 为考虑前 ii 个字符，共有 jj 个 docker 的最小操作次数。

dpi,j=min⁡{dpi−1,j,dpi−6,j−1+costi}dp_{i,j}=\min\{dp_{i-1,j},dp_{i-6,j-1}+cost_i\}

答案是 dpm,idp_{m,i}。然而，这样的复杂度是 O(m2)O(m^2) 的，无法接受，暴力的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
auto bf = [&](int target){
    vector<vector<int>> dp(m+1, vector<int>(target+1));
    for (int j = 1; j <= target; j++) {
        dp[0][j] = dp[1][j] = dp[2][j] = dp[3][j] = dp[4][j] = dp[5][j] = INF;
    }
    for (int i = 6; i <= m; i++) {
        for (int j = 1; j <= target; j++) {
            dp[i][j] = min(dp[i-1][j], dp[i-6][j-1] + diff(i));
        }
    }
    return dp[m][target];
};

~经过打表发现~，f(x)=dpm,xf(x)=dp_{m,x} 是一个下凸的函数。证明可以看官方题解。

如果这样的话，可以通过 WQS 二分处理。

具体地说，由于 (x,f(x))(x,f(x)) 是一个下凸包，那么斜率为 kk 的切线切凸包于 (x,f(x))(x,f(x))，那么一定有 b=f(x)−kxb=f(x)-kx 最小。

这里求出最小的 f(x)−kxf(x)-kx，就是把上面的 dpdp 稍加转化的过程，其实把每一个 costi←costi−kcost_i\gets cost_i-k 即可。

于是，在 dpdp 的过程中，我们不需要记录第二维 jj，而是用 dpi′=min⁡jdpi,jdp_{i}'=\min_{j}dp_{i,j}，并且记录对应的 jj 为 cnticnt_i，也就是最后的 xx 值。

由于 dpi,0=0,0≤i≤5dp_{i,0}=0,0\le i\le 5，并且 dpi,j=+∞,j≥1dp_{i,j}=+\infty, j\ge 1，所以令 dp0∼5′=0,cnt0∼5=0dp_{0\sim 5}'=0,cnt_{0\sim 5}=0。

然后，转移有：

dpi′=min⁡{dpi−1′dpi−6′+costi−kdp'_i=\min\begin{cases} dp'_{i-1}\\ dp'_{i-6}+cost_i-k \end{cases}

并且第一种情况 cnti=cnti−1cnt_i=cnt_{i-1}，第二种情况 cnti=cnti−6+1cnt_i=cnt_{i-6}+1，并且如果两个式子相等，尽量取下面那个。这样的话，如果多点共线，我们永远会取最大的那个 xx。

于是当二分出的 x≥targetx\ge target 时，我们认为这个 midmid 有可能是答案的 kk；否则一定不是答案的 kk。

由于答案在直线 y=kx+by=kx+b 上，那么直接把 targettarget 带入这条直线即可。

实现

实现上有一个细节，那就是当二分结束时，最后一次调用的 check(mid) 的 mid 可能并非答案对应的 kk，所以需要再调用一次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>
using namespace std;

#define int long long
const int INF = 1e18;

int solve() {
    string s;
    int n;
    cin >> s >> n;
    int m = s.size();
    s = ' ' + s;

    auto diff = [&](int i) -> int {
        return (s[i-5] != 'd') + (s[i-4] != 'o') + (s[i-3] != 'c')
            + (s[i-2] != 'k') + (s[i-1] != 'e') + (s[i] != 'r');
    };

    int raw = 0, mx = m/6;
    for (int i = 6; i <= m; i++) {
        if (!diff(i)) raw++;
    }
    vector<int> c(mx+2);

    for (int i = 1, l, r; i <= n; i++) {
        cin >> l >> r;
        if (l > mx) continue;
        c[l]++;
        c[min(mx, r)+1]--;
    }

    int mxpeople = 0;
    for (int i = 1; i <= mx; i++) mxpeople = max(mxpeople, c[i] += c[i-1]);
    if (mxpeople == 0) return 0;

    auto check = [&](int mid) -> pair<int, int> {
        vector<int> dp(m+1);
        vector<int> cnt(m+1);
        for (int i = 6; i <= m; i++) {
            int cost = diff(i) - mid;
            if (dp[i-6] + cost <= dp[i-1]) {
                dp[i] = dp[i-6] + cost;
                cnt[i] = cnt[i-6] + 1;
            }
            else {
                dp[i] = dp[i-1];
                cnt[i] = cnt[i-1];
            }
        }
        return {dp[m], cnt[m]};
    };

    auto wqs = [&](int target) {
        int l = -m-1, r = m+1;
        int b, x;
        while (l < r) {
            int mid = (l+r) >> 1;
            tie(b, x) = check(mid);
            if (x >= target) r = mid;
            else l = mid + 1;
        }
        // 注意最后可能并不以 check(mid) 结束, 所以需要重新调用一下
        tie(b, x) = check(r);
        return r * target + b;
    };

    int ans = INF;
    for (int i = 1; i <= mx; i++) {
        if (c[i] != mxpeople) continue;
        if (i <= raw) ans = min(ans, raw - i);
        else {
            ans = min(ans, wqs(i));
            break;
        }
    }

    return ans;
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T;
    cin >> T;
    while (T--) cout << solve() << '\n';
    return 0;
}