Moe's CF Life

Appearance

E. Maximum Questions - 题解 ​

比赛与标签 ​

比赛: Codeforces Round 450 (Div. 2) 标签: data structures, dp, strings 难度: *2100

喵喵，这是什么任务呀？ (题目大意) ​

你好呀，指挥官！今天我们遇到的问题是这样的喵~

我们有一个长度为 n 的字符串 s，里面混杂着 'a', 'b' 和一些捣蛋的 '?' 问号。还有一个长度为 m 的模板串 t，它的模式非常规律，就是 "abab..." 这样交替出现。

我们的任务是：

  1. 把 s 里的 '?' 替换成 'a' 或 'b'。
  2. 在 s 中找出尽可能多的、互不重叠的、能匹配模板串 t 的子串。这个最多的数量就是所谓的 "beauty"。
  3. 在所有能够达到最大 "beauty" 的替换方案中，我们要找到一种替换次数最少的方案。

最后，只要输出这个最少的替换次数就可以啦！听起来是不是很有趣呢？喵~

来和咱一起分析吧，喵~ (解题思路) ​

这个问题要求我们先最大化一个值（beauty），再最小化另一个值（替换次数），这可是动态规划（DP）大显身手的好机会哦！

让咱们一步一步来拆解这个问题吧！

第一步：预处理，让问题变简单！ ​

首先，我们要快速判断 s 中任意一个长度为 m 的子串 s[i...i+m-1] 能不能变成 t。

模板串 t 是 "abab..."，但它在 s 中的具体形式取决于起始位置 i 的奇偶性。

  • 如果 i 是偶数（0-indexed），那么期望的模式是 a, b, a, b, ...
  • 如果 i 是奇数（0-indexed），那么期望的模式是 b, a, b, a, ...

如果每次都去遍历子串来判断，那也太慢啦！这里有个超级棒的技巧——前缀和！

  1. 标记冲突点：我们可以创建两个布尔数组 bad0 和 bad1。

    • bad0[i] = 1 表示 s[i] 与 a, b, a, b... 模式冲突（比如偶数位上不是 'a'）。
    • bad1[i] = 1 表示 s[i] 与 b, a, b, a... 模式冲突（比如偶数位上不是 'b'）。
    • 注意哦，? 是万能的，它从不与任何模式冲突，喵~

  2. 计算前缀和：基于 bad0 和 bad1，我们可以计算出它们的前缀和数组 p0 和 p1。这样，我们就能在 O(1) 时间内知道任意子串 s[i...i+m-1] 中有多少个冲突点啦！

    • p0[i+m] - p0[i] == 0 就意味着子串 s[i...i+m-1] 与 a,b,a,b... 模式完全不冲突。

  3. 计算替换代价：同样地，我们可以用前缀和 pq_arr 来记录 ? 的数量。子串 s[i...i+m-1] 的替换代价就是 pq_arr[i+m] - pq_arr[i]。

通过这些预处理，我们可以为每个可能的起始位置 i，在 O(1) 时间内得出它是否 valid（可以构成 t）以及它的 cost（需要替换多少个 ?）。

第二步：动态规划，寻找最优解！ ​

预处理做完，就轮到 DP 登场啦！我们需要记录两个状态：

  • f[i]: 处理完字符串 s 的前 i 个字符 (s[0...i-1]) 后，能获得的最大 beauty。
  • g[i]: 为了达到 f[i] 这个 beauty，所需要的最小替换次数。

接下来就是激动人心的状态转移了，喵~

当我们计算 f[i] 和 g[i] 时，有两种可能：

  1. 第 i 个字符不作为任何 t 出现的结尾： 这种情况下，我们没有在当前位置做出任何“贡献”，所以最优解就是从前一个位置继承过来的。

    • f[i] = f[i-1]
    • g[i] = g[i-1]

  2. 第 i 个字符恰好是某个 t 出现的结尾： 这种情况只有在 i >= m 时才可能发生。这个 t 的出现会占据子串 s[i-m ... i-1]。

    • 首先，我们要用预处理的结果检查这个子串是否 valid。
    • 如果 valid，那么我们找到了一个新的可能解！这个解是在 s[0...i-m-1] 的最优解基础上，加上这个新的出现。
      • 新的 beauty: cand_f = f[i-m] + 1
      • 新的 cost: cand_g = g[i-m] + cost(s[i-m...i-1])
    • 现在，我们需要比较这个新解和我们已有的解（来自情况1）：
      • 如果 cand_f > f[i]，说明我们找到了一个 beauty 更高的方案！太棒啦！必须更新 f[i] 和 g[i]。
      • 如果 cand_f == f[i]，说明 beauty 一样，那我们就要选 cost 更小的那个，所以 g[i] = min(g[i], cand_g)。

我们从 i=1 到 n 遍历一遍，每次都按上面的逻辑更新 f[i] 和 g[i]。当循环结束时，g[n] 就是我们想要的最终答案——在最大化 beauty 的前提下的最小替换次数！

看咱的代码魔法！ (代码实现) ​

cpp
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); // 加速输入输出，是个好习惯喵~
    cin.tie(NULL);

    int n;
    cin >> n;
    string s;
    cin >> s;
    int m;
    cin >> m;

    // --- 预处理阶段 ---
    // bad0[i] = 1 表示 s[i] 与 "abab..." 模式冲突
    // bad1[i] = 1 表示 s[i] 与 "baba..." 模式冲突
    vector<int> bad0(n, 0), bad1(n, 0);
    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) { // 偶数位（0-indexed）
            if (s[i] == 'b') bad0[i] = 1; // "abab..." 模式需要 'a'
            if (s[i] == 'a') bad1[i] = 1; // "baba..." 模式需要 'b'
        } else { // 奇数位
            if (s[i] == 'a') bad0[i] = 1; // "abab..." 模式需要 'b'
            if (s[i] == 'b') bad1[i] = 1; // "baba..." 模式需要 'a'
        }
    }

    // p0, p1, pq_arr 分别是 bad0, bad1, '?' 的前缀和数组
    vector<int> p0(n + 1, 0), p1(n + 1, 0), pq_arr(n + 1, 0);
    for (int i = 0; i < n; i++) {
        p0[i + 1] = p0[i] + bad0[i];
        p1[i + 1] = p1[i] + bad1[i];
        pq_arr[i + 1] = pq_arr[i] + (s[i] == '?' ? 1 : 0);
    }

    // valid[i] 表示从 i 开始的子串能否构成 t
    // cost_arr[i] 表示从 i 开始的子串构成 t 的代价（'?' 的数量）
    vector<bool> valid(n, false);
    vector<int> cost_arr(n, 0);

    for (int i0 = 0; i0 <= n - m; i0++) {
        // 判断从 i0 开始的子串是否有效
        if (i0 % 2 == 0) { // 起始点是偶数，匹配 "abab..."
            if (p0[i0 + m] - p0[i0] == 0)
                valid[i0] = true;
        } else { // 起始点是奇数，匹配 "baba..."
            if (p1[i0 + m] - p1[i0] == 0)
                valid[i0] = true;
        }
        // 计算代价
        cost_arr[i0] = pq_arr[i0 + m] - pq_arr[i0];
    }

    // --- DP 阶段 ---
    // f[i]: 前 i 个字符的最大 beauty
    // g[i]: 达到 f[i] 的最小 cost
    vector<int> f(n + 1, 0);
    vector<long long> g(n + 1, 0); // cost 可能很大，用 long long 保险一点

    for (int i = 1; i <= n; i++) {
        // 方案1: 不在 i-1 处结束一个 t 的出现，直接继承前一个状态
        f[i] = f[i - 1];
        g[i] = g[i - 1];

        // 方案2: 尝试在 i-1 处结束一个 t 的出现
        if (i >= m) {
            int i0 = i - m; // 这个 t 的起始位置
            if (valid[i0]) { // 如果从 i0 开始的子串是有效的
                // 计算候选的 beauty 和 cost
                int cand_f = f[i0] + 1;
                long long cand_g = g[i0] + cost_arr[i0];
                
                // 更新最优解
                if (cand_f > f[i]) { // 找到了更高的 beauty
                    f[i] = cand_f;
                    g[i] = cand_g;
                } else if (cand_f == f[i] && cand_g < g[i]) { // beauty 相同，但 cost 更小
                    g[i] = cand_g;
                }
            }
        }
    }

    cout << g[n] << endl; // 输出最终答案

    return 0;
}

跑得快不快呀？ (复杂度分析) ​

  • 时间复杂度: O(n) 的说。

    • 预处理 bad 数组是 O(n)。
    • 计算三个前缀和数组都是 O(n)。
    • 计算 valid 和 cost 数组是 O(n)。
    • 最后的 DP 循环也是 O(n)，因为循环体内部都是 O(1) 的操作。
    • 总的来说就是 O(n)，超级快，对不对！

  • 空间复杂度: O(n) 的说。

    • 我们用了好几个长度为 n 或 n+1 的数组 (bad0, bad1, p0, p1, pq_arr, valid, cost_arr, f, g)。所以空间开销是 O(n) 级别的喵~

这次学到了什么喵？ (知识点与总结) ​

这次的冒险让我们收获满满呀！

  1. 双目标优化DP：当题目要求我们“先最大化A，再最小化B”时，一个经典的DP思路就是用一个状态记录A，另一个状态记录B。在状态转移时，优先比较A，A相同时再比较B。

  2. 前缀和大法好：前缀和是处理区间查询问题的神器！它能把 O(m) 的子串检查优化到 O(1)，是让整个算法效率提升到 O(n) 的关键所在。以后遇到类似的问题，一定要先想想能不能用前缀和来预处理，喵~

  3. 问题分解：再复杂的问题，只要能分解成清晰的小步骤（预处理 -> DP状态定义 -> 状态转移），就会变得清晰明了。

总之，只要我们把问题拆解开，用合适的工具（比如DP和前缀和）去解决，就没有什么难题能挡住我们！指挥官，继续加油哦，期待下一次和你一起解题，喵！

Released under the MIT License.

Copyright © 2024-present Moe