D2. RGB Substring (hard version) - 题解

比赛与标签

比赛: Codeforces Round 575 (Div. 3) 标签: data structures, dp, implementation, two pointers 难度: *1600

题目大意喵~

主人你好呀！这道题目是说，我们有一个由 'R', 'G', 'B' 三种字符组成的字符串 s，还有一个整数 k 呐。我们的任务是，用最少的修改次数，让字符串 s 中包含一个长度为 k 的子串，这个子串同时也是无限循环字符串 "RGBRGBRGB..." 的一个子串。

举个栗子，"RGBRG" 和 "GBR" 都是 "RGBRGBRGB..." 的子串，但 "RGR" 就不是啦。我们需要对每个查询都找到这个最少的修改次数，喵~

解题思路分析喵~

这道题的核心，就是要找到一个最“匹配”的窗口！让我们一步步来拆解这个问题吧，喵~

1. 目标是什么呀？

我们的目标是让 s 的某个长度为 k 的子串，变成 "RGBRGBRGB..." 的子串。 无限字符串 "RGBRGBRGB..." 有一个非常明显的规律，就是以 "RGB" 为周期循环。这意味着，任何一个合法的目标子串，都必须遵循这个 3-周期 的规律。

那么，长度为 k 的目标子串有几种可能呢？其实只有三种基本模式，喵~

• 模式一：从 'R' 开始，形如 "RGBRGB..."
• 模式二：从 'G' 开始，形如 "GBRGBR..."
• 模式三：从 'B' 开始，形如 "BRGBRG..."

任何一个长度为 k 的合法子串，都必然是这三种模式之一的开头部分。比如 k=5，目标串就只能是 "RGBRG", "GBRGB", "BRGBR" 这三种。

2. 如何找到最优解呢？

题目要求的是对 s 的 某个 子串进行修改，使得修改次数最少。这意味着我们需要检查 s 中 所有 长度为 k 的子串，看看把它变成上述三种模式之一，哪种情况需要的修改次数最少。

一个直观但有点慢的方法是：

1. 遍历 s 的所有起始位置 i (从 0 到 n-k)，形成一个长度为 k 的窗口 s[i...i+k-1]。
2. 对于每个窗口，分别计算它变成模式一、模式二、模式三所需要的修改次数。
3. 在所有这些修改次数中，取一个最小值。

这个方法的时间复杂度是 O((n-k) * k * 3)，对于这道题的数据范围 (n 最大 2*10^5) 来说，是会超时的说！( TДT)

3. 滑动窗口大法好！

当我们需要对连续的子数组/子串进行计算时，一个非常强大的优化技巧就是滑动窗口！

我们可以固定一种目标模式（比如模式一 "RGBRGB..."），然后计算 s 中所有窗口匹配它的最小代价。

1. 初始化：先计算第一个窗口 s[0...k-1] 和目标模式的差异。比如说，我们遍历这个窗口，如果 s[j] 不等于目标模式中第 j 个位置应有的字符，就把修改次数 changes 加一。这个初始代价就是我们第一个窗口的代价。
2. 滑动：现在，我们想计算第二个窗口 s[1...k] 的代价。和第一个窗口相比，它移除了最左边的字符 s[0]，并加入了最右边的新字符 s[k]。
   • 移出：检查刚刚离开窗口的 s[0]。如果它之前是不匹配目标模式的（我们为它付出了1点修改代价），那么现在它离开了，我们就可以把 changes 减一，因为它不再是这个窗口的问题啦。
   • 移入：检查新进入窗口的 s[k]。如果它不匹配目标模式中对应位置的字符，我们就需要为它付出1点修改代价，所以把 changes 加一。
3. 通过这种方式，我们每次移动窗口，只需要 O(1) 的时间就可以更新修改次数！我们一路滑过去，记录下所有窗口中出现过的最小修改次数。

对三种模式（"RGB...", "GBR...", "BRG..."）分别执行一次滑动窗口，我们就可以在 O(n) 的时间内找到全局的最小修改次数了！是不是很高效呀？喵~

总结一下最终的算法：

1. 设定一个全局最小修改次数 min_total_changes，初始值为 k (这是最坏情况)。
2. 对三种目标模式（可以用一个 0, 1, 2 的偏移量来代表）分别进行一次滑动窗口计算。
3. 在每次滑动中，更新当前模式下的最小修改次数，并用它来更新全局的 min_total_changes。
4. 最后输出 min_total_changes 就好啦！

代码实现喵~

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

void solve() {
    int n, k;
    std::cin >> n >> k;
    std::string s;
    std::cin >> s;

    // 最小修改次数，初始化为一个安全的最大值 k
    // 因为一个长度为 k 的窗口，最多也只需要修改 k 次
    int min_total_changes = k;

    // 目标模式是 "RGB" 循环。我们可以有三种不同的起始模式
    // 1. "RGBRGB..."
    // 2. "GBRGBR..."
    // 3. "BRGBRG..."
    char pattern[] = "RGB";

    // 我们遍历这三种可能的模式
    // 'start_offset' 决定了我们当前正在和哪种模式进行比较
    // start_offset = 0 对应 "RGB..."
    // start_offset = 1 对应 "GBR..."
    // start_offset = 2 对应 "BRG..."
    for (int start_offset = 0; start_offset < 3; ++start_offset) {
        int current_changes = 0;

        // 首先，计算第一个窗口 s[0...k-1] 的修改代价
        for (int i = 0; i < k; ++i) {
            // s[i] 的目标字符取决于它的绝对位置 'i' 和模式的偏移 'start_offset'
            // 在无限模式串中，索引为 i 且偏移为 start_offset 的字符是 pattern[(i + start_offset) % 3]
            if (s[i] != pattern[(i + start_offset) % 3]) {
                current_changes++;
            }
        }
        min_total_changes = std::min(min_total_changes, current_changes);

        // 使用滑动窗口来计算其他所有窗口的最小代价
        // 窗口从索引 'i' 开始
        for (int i = 1; i <= n - k; ++i) {
            // 更新代价：减去离开窗口的字符 s[i-1] 的贡献
            // 如果 s[i-1] 之前是需要修改的，现在它走了，代价就减少 1
            if (s[i - 1] != pattern[((i - 1) + start_offset) % 3]) {
                current_changes--;
            }
            
            // 加上新进入窗口的字符 s[i+k-1] 的贡献
            // 如果 s[i+k-1] 是需要修改的，代价就增加 1
            if (s[i + k - 1] != pattern[((i + k - 1) + start_offset) % 3]) {
                current_changes++;
            }
            
            // 更新全局的最小修改次数
            min_total_changes = std::min(min_total_changes, current_changes);
        }
    }

    std::cout << min_total_changes << "\n";
}

int main() {
    // 快速 I/O，让程序跑得更快喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int q;
    std::cin >> q;
    while (q--) {
        solve();
    }

    return 0;
}

复杂度分析的说

• 时间复杂度: O(n) 的说。对于每一个查询，我们有一个外层循环，固定运行 3 次（对应三种模式）。在循环内部，我们先用 O(k) 的时间计算第一个窗口的代价，然后用 O(n-k) 的时间进行滑动。所以对于一种模式，总时间是 O(k + n - k) = O(n)。三种模式加起来就是 O(3 * n)，也就是 O(n) 啦。因为题目保证了所有查询的 n 的总和不超过 2 * 10^5，所以总的计算时间是完全可以接受的！
• 空间复杂度: O(n) 的说。我们主要需要空间来存储输入的字符串 s，所以空间复杂度和字符串长度 n 成正比。

知识点与总结喵~

这道题真是一道非常经典的滑动窗口入门好题呢！通过它我们可以学到：

1. 模式识别: 解决问题的第一步是看穿问题的本质！无限字符串 "RGBRGBRGB..." 的周期性是解题的关键。一旦意识到只有三种基本模式，问题就清晰多啦。
2. 滑动窗口优化: 当遇到求解连续子串/子数组的最优值问题时，一定要想想能不能用滑动窗口！它能将 O(N*K) 的暴力解法优化到 O(N)，是算法竞赛中非常重要的思想。
3. 模运算的妙用: 使用 (i + offset) % 3 这样的表达式来处理循环/周期性的问题，非常简洁和优雅，是编程中的一个小技巧哦！

希望这篇题解能帮助到你，喵~ 如果你理解了滑动窗口的思想，以后遇到类似的题目就都能迎刃而解啦！加油，主人！(๑•̀ㅂ•́)و✧