「Nhk R2」自胡蹿 - 题解

标签与难度

标签: 字符串, 回文串, 双指针, 枚举, 贪心 难度: 1700

题目大意喵~

主人你好呀~ 这道题是这样的：我们有一个字符串 s 和一个目标长度 k。我们可以对字符串 s 进行一种特殊操作：选择任意一个位置 i，然后把 s[i] 这个字符复制一份，插入到 s[i] 和 s[i+1] 之间。我们的任务是，用最少的操作次数，让字符串 s 中出现一个长度至少为 k 的回文子串。要多少次操作才能做到呢？喵~

举个栗子：s = "abc", k = 4。 如果我们选择 i=2（也就是字符 'b'），操作后字符串变成 "abbc"。这就用了一次操作。 我们的目标就是找到最省力的办法，让字符串里藏一个长长的大回文！

解题思路分析

这道题看起来是在字符串上操作，但让我来分析一下操作的本质，问题就会变得清晰起来，喵！

操作的本质是什么？

操作是在位置 i 和 i+1 之间插入一个 s[i] 的复制。这实际上就是把字符串的总长度增加 1。如果我们想把一个字符 c 变成 ccccc，就需要 4 次操作。 所以，每进行一次操作，我们就会往字符串里添加一个新字符。

我们的目标是用最少的操作次数得到一个长度至少为 k 的回文串。假设我们最后得到的回文串长度是 L（L >= k），而这个回文串在原字符串中对应的部分总共有 L_initial 个字符，那么我们需要添加 L - L_initial 个字符。因为每次操作只增加一个字符，所以最少的操作次数就是 L - L_initial。

为了让操作次数最少，我们应该在 L >= k 的前提下，让 L - L_initial 尽可能小。一个简单的贪心策略是，我们只造一个长度刚好为 k 的回文串（如果 k 可以达到的话），这样 L 就固定为 k 了。于是问题就转化成了：

最小化 k - L_initial <=> 最大化 L_initial

L_initial 是什么呢？它是在原字符串中，能够构成一个回文串的那些字符的总数。

如何最大化 L_initial？

一个回文串是围绕一个中心对称的。这个中心可以是一个字符（比如 racecar 的中心是 e），也可以是两个相同的字符（比如 abba 的中心是 bb）。在我们的问题里，这个中心可以是一个连续相同字符组成的块。

比如，原字符串 s = a bbb c b a，我们可以把它看成是 (a) (bbb) (c) (b) (a) 这些块组成的。 如果我们以 c 为中心，向两边看，左边是 bbb，右边是 b。它们的字符相同！都是 'b'。 再往外，左边是 a，右边是 a。也相同！

所以，a bbb c b a 这个结构天然就是一个“回文结构”。这些块里的所有字符都可以用来构成我们最终的回文串。它们的总长度是 1 (a) + 3 (bbb) + 1 (c) + 1 (b) + 1 (a) = 7。这就是我们能免费得到的最大长度 L_initial。

为什么这些字符都能用上呢？因为我们可以通过操作来“补齐”字符。比如 bbb 和 b，我们可以在 b 上操作两次，把它变成 bbb，这样左右就对称了。这些操作的代价，正好就是我们最终需要的总字符数 k 和我们已经拥有的字符数 L_initial 的差值。

核心洞察，喵！ 无论我们怎么操作，每一次操作都是给某个字符块增加一个字符。所以，要得到一个长度为 k 的最终回文串，而我们已经从原始块中凑了 L_initial 个字符，我们净需要增加的字符数就是 k - L_initial。每一次操作恰好增加一个字符，所以最少操作数就是 k - L_initial！

所以，我们的问题就变成了：在原字符串中，找到一个可以形成回文的块序列，使其包含的总字符数 L_initial 最大！

算法实现：双指针大法！

我们可以枚举所有可能的回文中心，然后从中心向两边扩展，计算出以它为中心能得到的最大 L_initial。

一个回文串的中心有两种情况：

1. 奇数长度回文串：中心是一个字符块，比如 a(ccc)a。
2. 偶数长度回文串：中心是两个相邻的相同字符块，比如 ab(cc)ba。

我们可以用双指针来解决这两种情况：

1. 枚举奇数中心：

   • 遍历字符串中的每一个字符 s[i]，把它所在的连续字符块作为回文中心。
   • 用两个指针 l 和 r 指向这个中心块的左右边界。
   • 然后不断将 l 左移，r 右移，检查 s[l] 和 s[r] 是否相等。
   • 如果相等，说明它们可以构成回文。我们就把 l 左移到它所在块的左边界，r 右移到它所在块的右边界，把这些块都包含进来。
   • 重复这个过程，直到指针越界或者 s[l] 与 s[r] 不等。
   • 此时 r - l + 1 就是以 s[i] 为中心能得到的最大 L_initial。

2. 枚举偶数中心：

   • 遍历字符串中所有相邻的位置 (i, i+1)。
   • 如果 s[i] == s[i+1]，那么它们所在的两个（或一个）块就可以作为回文中心。
   • 同样用双指针 l 和 r 指向这个中心结构（s[i] 所在块的左边界和 s[i+1] 所在块的右边界）。
   • 然后像奇数情况一样，向外扩展。
   • 计算出 L_initial。

我们把所有可能中心算出来的 L_initial 取一个最大值，记为 max_L_initial。 如果 max_L_initial >= k，说明我们不需要任何操作，答案是 0。 否则，最终答案就是 k - max_L_initial。

这样，通过枚举所有中心并用双指针扩展，我们就能找到最优解啦，喵~

代码实现

这是我根据上面的思路，精心为你准备的 C++ 代码哦！注释超详细的，快来看看吧~

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

using namespace std;

void solve() {
    int n;
    long long k;
    cin >> n >> k;
    string s;
    cin >> s;

    long long max_len = 0;

    // --- Case 1: Odd length palindromes (centered on a block) ---
    // We iterate through each character 'i' and consider its block as the center.
    for (int i = 0; i < n; ++i) {
        // Find the boundaries of the central block containing s[i]
        int l = i, r = i;
        while (l > 0 && s[l - 1] == s[i]) {
            l--;
        }
        while (r < n - 1 && s[r + 1] == s[i]) {
            r++;
        }

        // Now, expand outwards from this block s[l...r]
        int current_l = l;
        int current_r = r;
        while (current_l > 0 && current_r < n - 1) {
            if (s[current_l - 1] != s[current_r + 1]) {
                break; // Mismatch, can't expand further
            }
            
            // It's a match! Expand to include the entire blocks.
            char match_char = s[current_l - 1];
            int next_l = current_l - 1;
            int next_r = current_r + 1;

            while (next_l > 0 && s[next_l - 1] == match_char) {
                next_l--;
            }
            while (next_r < n - 1 && s[next_r + 1] == match_char) {
                next_r++;
            }
            
            current_l = next_l;
            current_r = next_r;
        }
        max_len = max(max_len, (long long)current_r - current_l + 1);
    }

    // --- Case 2: Even length palindromes (centered between two blocks) ---
    // We iterate through each adjacent pair (i, i+1) as a potential center.
    for (int i = 0; i < n - 1; ++i) {
        if (s[i] != s[i+1]) {
            continue; // Must be same character to form a palindrome center
        }

        // Find the boundaries of the central blocks around (i, i+1)
        int l = i, r = i + 1;
        while (l > 0 && s[l - 1] == s[i]) {
            l--;
        }
        while (r < n - 1 && s[r + 1] == s[i+1]) {
            r++;
        }

        // Now, expand outwards from this block s[l...r]
        int current_l = l;
        int current_r = r;
        while (current_l > 0 && current_r < n - 1) {
            if (s[current_l - 1] != s[current_r + 1]) {
                break; // Mismatch
            }

            // It's a match! Expand to include the entire blocks.
            char match_char = s[current_l - 1];
            int next_l = current_l - 1;
            int next_r = current_r + 1;
            
            while (next_l > 0 && s[next_l - 1] == match_char) {
                next_l--;
            }
            while (next_r < n - 1 && s[next_r + 1] == match_char) {
                next_r++;
            }
            
            current_l = next_l;
            current_r = next_r;
        }
        max_len = max(max_len, (long long)current_r - current_l + 1);
    }
    
    if (max_len >= k) {
        cout << 0 << endl;
    } else {
        cout << k - max_len << endl;
    }
}

int main() {
    // Fast I/O for my speedy paws!
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

复杂度分析

• 时间复杂度: $O(N^2)$ 我们有两个主要的循环，一个用于奇数中心，一个用于偶数中心。在每个循环中，我们最多会迭代 $N$ 个可能的中心。对于每个中心，我们使用双指针向外扩展。虽然内部有 while 循环，但 l 指针只会向左移动，r 指针只会向右移动，在一次中心扩展中，它们最多各自扫描完整 个字符串一次。所以每次中心检查的复杂度是 $O(N)$。因此，总的时间复杂度是 $O(N \times N) = O(N^2)$，对于一般的题目限制来说，这个速度足够快啦，喵~

• 空间复杂度: $O(1)$ 我们只用到了几个变量来存储指针位置和长度，没有使用额外的、随输入大小 N 变化的存储空间。所以空间复杂度是常数级别的，非常优秀的说！

知识点总结

这道题真有趣，它把一个操作问题巧妙地转化成了一个寻找最优子结构的问题。我们来总结一下学到了什么吧！

1. 问题转化: 很多时候，题目的操作看起来很复杂，但分析其本质（比如每次操作增加一个字符），就能把问题简化成一个更经典的模型。在这里，就是把“最少操作”转化成了“最大化初始长度”。
2. 贪心思想: 我们贪心地认为，只需要构造一个长度恰好为 k 的回文串，并且总是利用最廉价的方式（即使用原字符串中已有的字符）来构造。
3. 回文串与双指针: 寻找回文串的经典方法就是“中心扩展法”。这道题是它的一个变体，我们扩展的单位不是单个字符，而是连续相同字符组成的“块”。
4. 枚举与分类讨论: 全面地解决问题需要考虑所有情况。这里我们把回文串分为奇数中心和偶数中心两种情况来枚举，确保没有遗漏任何可能性。

希望这篇题解能帮助到你，如果还有不明白的地方，随时可以再来问我哦！一起加油，攻克更多算法难题，喵~！