题目题解

问题理解

给定字符串 $s$ 和 $n$ 个人，第 $i$ 个人的理解区间为 $[l_i, r_i]$，要求 $s$ 中 "docker" 作为连续子串的出现次数在该区间内。
可以修改 $s$ 中的字符，求最少修改次数，使得最多的人能理解报告。

---

第一步：最大可满足人数

设 $t = \text{"docker"}$，长度 $6$，且字符互不相同，因此 $t$ 的出现不会重叠。
设 $m = \lfloor |s|/6 \rfloor$ 为理论最大出现次数。

对于每个人，将其区间与 $[0, m]$ 取交，得到实际可接受的次数范围。
统计每个次数 $c$ 有多少人能接受，得到数组 $dx[c]$。
设 $mx = \max dx[c]$ 为最大可满足人数。

我们的目标是：使最终出现次数 $k$ 满足 $dx[k] = mx$，并最小化修改次数。

---

第二步：分类讨论

设原字符串中 $t$ 的出现次数为 $cur$。

• 若 $k \le cur$：只需删除一些已有的 $t$（通过破坏它们），每个删除需修改 $6$ 个字符，但我们可以选择只修改部分字符使其不再是 $t$。实际上，每个已有 $t$ 可通过修改 $1$ 个字符破坏（因为 $t$ 的字符互不相同，改一个即可）。因此，从 $cur$ 降到 $k$ 需要修改 $cur - k$ 个字符。

• 若 $k > cur$：需要新增一些 $t$，这需要修改某些位置使其变成 $t$。这是一个最小代价问题。

---

第三步：新增 $t$ 的最小代价

设 $dif[i]$ 表示将 $s[i..i+5]$ 变成 $t$ 所需的最少修改次数（即不同字符个数）。
我们想选择 $k - cur$ 个互不重叠的长度为 $6$ 的区间，使得它们的 $dif$ 之和最小。

这是一个经典的选择 $x$ 个互不重叠区间的最小代价问题，可用 DP 解决。

定义 $dp[i][j]$ 表示考虑前 $i$ 个字符，选择了 $j$ 个 $t$ 的最小修改次数。
转移：

• 不选以 $i$ 结尾的区间：$dp[i][j] = dp[i-1][j]$
• 选以 $i$ 结尾的区间（要求 $i \ge 6$）：$dp[i][j] = \min(dp[i][j], dp[i-6][j-1] + dif[i-5])$

直接做是 $O(n \cdot m)$，不可行。

---

第四步：凸优化（Aliens Trick）

观察 $g(x) = dp[n][x]$，即选择 $x$ 个区间的最小代价。
可以证明 $g(x)$ 是凸函数（差分非递减）。
因此可用二分斜率 $d$，将 DP 转化为：

$$dp'[i] = \min(dp'[i-1], dp'[i-6] + dif[i-5] + d)$$

同时记录选择的区间个数。
通过调整 $d$，我们可以控制选择的区间数量，最终得到 $g(k)$ 的值。

这被称为 Lagrange 乘子法 或 Aliens Trick。

---

第五步：整体算法

1. 预处理 $dif[i]$ 和 $cur$（原 $t$ 的出现次数）。
2. 统计 $dx[c]$，找到最大可满足人数 $mx$ 及对应的 $k$。
3. 若 $k \le cur$，答案为 $cur - k$（破坏已有 $t$）。
4. 否则，用凸优化求 $g(k)$（新增 $k - cur$ 个 $t$ 的最小代价），加上破坏已有 $t$ 的代价（$cur - k$ 为负，即不破坏，实际是 $0$，因为 $k > cur$ 时不需要破坏），总代价即为 $g(k)$。

---

第六步：时间复杂度

• 预处理：$O(|s|)$。
• 二分斜率：$O(\log C)$ 次 DP，每次 DP $O(|s|)$。
• 总复杂度 $O(|s| \log C)$，满足 $|s| \le 5\times 10^5$。

---

代码实现

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e8;
const string T = "docker";

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        int n = s.size();
        int mx = n / 6;  // 最大可能出现次数
        
        int m;
        cin >> m;
        vector<int> dx(mx + 2, 0);
        for (int i = 0; i < m; i++) {
            int l, r;
            cin >> l >> r;
            r = min(r, mx);
            if (l > r) continue;
            dx[l]++;
            dx[r + 1]--;
        }
        for (int i = 1; i <= mx + 1; i++) {
            dx[i] += dx[i - 1];
        }
        
        // 计算 dif[i]：将 s[i..i+5] 变成 T 的最小修改次数
        vector<int> dif(max(0, n - 5));
        int cur = 0;
        for (int i = 0; i + 5 < n; i++) {
            int cnt = 0;
            for (int j = 0; j < 6; j++) {
                cnt += (s[i + j] != T[j]);
            }
            dif[i] = cnt;
            if (cnt == 0) cur++;
        }
        
        int mxcnt = *max_element(dx.begin(), dx.end());
        int k = -1;
        int ans = INF;
        
        // 情况1：k <= cur
        for (int i = 0; i <= mx; i++) {
            if (dx[i] != mxcnt) continue;
            if (i <= cur) {
                ans = min(ans, cur - i);
                continue;
            }
            k = i;
            break;
        }
        
        if (k == -1) {
            cout << ans << "\n";
            continue;
        }
        
        // 情况2：k > cur，用凸优化求 g(k)
        auto calc = [&](int d) {
            vector<pair<long long, int>> dp(n + 1, {1e18, -1});
            dp[0] = {0, 0};
            for (int i = 0; i < n; i++) {
                // 不选以 i 结尾的区间
                dp[i + 1] = min(dp[i + 1], dp[i]);
                // 选以 i 结尾的区间
                if (i + 6 <= n) {
                    auto nd = dp[i];
                    nd.first += dif[i] + d;
                    nd.second--;
                    dp[i + 6] = min(dp[i + 6], nd);
                }
            }
            return dp[n];
        };
        
        int l = -INF, r = 0, sv = INF;
        while (l <= r) {
            int mid = (l + r) / 2;
            auto [val, cnt] = calc(mid);
            if (-cnt >= k) {
                sv = val - 1LL * k * mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        ans = min(ans, sv);
        
        cout << ans << "\n";
    }
    
    return 0;
}

---

验证样例

输入：

2
dockerdockerxxxxxx
3
3 3
2 4
1 5
ljglsjfkdieufj
5
1 5
3 3
2 4
3 7
2 9

输出：

6
11

与题目输出一致。

---

总结

本题的关键在于：

1. 将问题分为“破坏已有 $t$”和“新增 $t$”两种情况。
2. 新增 $t$ 是一个带权区间选择问题，可用凸优化（Aliens Trick）在 $O(n \log C)$ 内求解。