Moe's CF Life

Appearance

F. Yet Another Substring Reverse - 题解 ​

比赛与标签 ​

比赛: Codeforces Round 590 (Div. 3) 标签: bitmasks, dp 难度: *2200

喵喵，题目说什么呀？ ​

你好呀，指挥官！今天我们遇到的这道题，是要处理一个只包含前20个小写字母（'a' 到 't'）的字符串s的说。

我们可以对这个字符串做一次特殊操作（也可以不做哦）：选择任意一个子串 s[l...r] 并把它翻转过来。

我们的目标是，在最多进行一次翻转操作后，让字符串中含有不重复字符的最长子串变得尽可能长！一个子串含有不重复字符，意思就是里面每个字母都只出现一次，比如说 "abcdef" 就是，但 "abacaba" 就不是了，因为它有好几个 'a' 和 'b' 呢，喵~

简单来说，就是通过一次翻转，创造出最长的、没有重复字母的子串，然后告诉咱它的长度是多少，呐。

来和咱一起想办法喵！ ​

看到这个问题，第一反应可能会觉得这个“翻转”操作好复杂呀，要枚举所有可能的翻转区间吗？那样肯定会超时的说！(つд⊂)

别急别急，让咱换个思路来想一想。我们的最终目标是得到一个没有重复字符的子串。这个子串，不管我们怎么翻转，它都是由原字符串s里的某些字符组成的。这个翻转操作，本质上是把原来不相邻的两段子串“拼接”在了一起。

举个栗子：s = A...B...C，我们把中间的 B 翻转成 B'，字符串就变成了 A...B'...C。一个最长的无重复字符子串，可能完全在 A 中，也可能横跨 A 和 B'，或者 B' 和 C。

最关键的洞察在这里喵！任何一次翻转操作，最终形成的最长无重复字符子串，都可以看作是原字符串中两个不相交的、且字符集也互不相交的子串拼接而成的结果。

比如说，我们在原字符串里找到了两个无重复字符的子串 S1 和 S2，它们的字符集合分别是 mask1 和 mask2，并且 mask1 和 mask2 没有共同的字符。那我们总能通过一次翻转，把它们俩凑到一起，形成一个更长的、无重复字符的子串，长度就是 |S1| + |S2|。

所以问题就转化成了一个更清晰的目标： 在原字符串 s 中，找出两个字符集不相交的无重复字符子串，使它们的长度之和最大化。

既然只有20种字符，这简直是在向我们招手，快用位运算状态压缩DP呀！我们可以用一个20位的二进制数（也就是 mask）来表示一个字符集合，第 i 位是1就代表包含第 i 个字母（'a'+i）。

我们的解题计划分为三步走，喵~

第一步：预处理 - 收集所有的小碎片喵 ​

我们先创建一个 dp 数组，dp[mask] 用来存储信息。首先，我们让 dp[mask] 表示：在原字符串中，所有字符集恰好为 mask 的无重复字符子串中，最长的那个长度是多少。

怎么计算呢？很简单！ 我们遍历字符串 s 的每一个位置 i 作为起点，然后向右扩展。

  • 维护一个 current_mask，记录当前子串的字符集。
  • 每遇到一个新字符，就更新 current_mask。如果这个字符已经存在于 current_mask 中了，说明重复了，就停止从 i 开始的这次扩展。
  • 在扩展的每一步，我们都用当前子串的长度（也就是 popcount(current_mask)）去更新 dp[current_mask]。
cpp
// 伪代码演示
dp[1 << 20] = {0};
for i = 0 to s.length() - 1:
  current_mask = 0
  for j = i to s.length() - 1:
    char_bit = 1 << (s[j] - 'a')
    if (current_mask & char_bit) break; // 出现重复字符，溜了溜了
    current_mask |= char_bit
    dp[current_mask] = popcount(current_mask) // 更新dp值

第二步：子集DP - 让碎片们变得更强力！ ​

现在 dp[mask] 存的是字符集恰好为 mask 的最大长度。但我们可能需要的是字符集为 mask 的一个子集的最大长度。比如说，dp[011] (表示{"b", "c"}) 的最优解，可能其实是来自一个字符集为 001 ({"c"}) 的子串。

所以我们需要更新 dp 数组的定义！让 dp[mask] 表示：所有字符集是 mask 的子集的无重复字符子串中，最长的那个长度是多少。

这可以用一种叫做子集DP (SOS DP, Sum Over Subsets DP) 的技巧来高效实现。 我们遍历每一个维度（也就是每一个比特位 b）： 对于所有 mask，如果 mask 的第 b 位是1，那么 mask 的最优解，要么是来自它自己（不包含字符 b 的部分），要么是继承自 mask 去掉 b 之后的那个子集 mask ^ (1 << b)。 所以状态转移方程就是：dp[mask] = max(dp[mask], dp[mask ^ (1 << b)])。

cpp
// 伪代码演示
for b = 0 to 19: // 遍历所有比特位
  for mask = 0 to (1 << 20) - 1:
    if (mask & (1 << b)): // 如果mask包含这个比特位
      dp[mask] = max(dp[mask], dp[mask ^ (1 << b)])

做完这一步，dp[mask] 就变得非常强大了！它知道了所有是它子集的字符组合能达到的最大长度。

第三步：寻找最佳组合 - 合体！最强形态！ ​

万事俱备，只欠东风！我们现在要找两个不相交的字符集 mask1 和 mask2，让 dp[mask1] + dp[mask2] 最大。

直接枚举 mask1 和 mask2 太慢啦 ((2^20)^2)。但是， благодаря我们第二步的努力，事情变得简单了！ 对于任何一个 mask，要找一个和它不相交的 mask'，mask' 的字符集必然是 mask 补集的一个子集。 mask 的补集是什么呢？就是 full_mask ^ mask，其中 full_mask 是所有位都为1的掩码 (1 << 20) - 1。

而一个字符集是 full_mask ^ mask 的子集的最大长度，不就是我们刚刚算出来的 dp[full_mask ^ mask] 吗？太棒了喵！

所以，我们只需要遍历所有可能的 mask，计算 dp[mask] + dp[full_mask ^ mask]，然后取它们中的最大值，就是我们的最终答案啦！

看咱的代码魔法吧！ ​

cpp
#include <iostream>
#include <vector>
#include <string>   // 为了 string
#include <algorithm> // 为了 max

// 使用C++标准库的函数会让代码更清晰喵~
using namespace std;

int main() {
    // 关掉同步可以跑得更快哦！
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string s;
    cin >> s;
    int n = s.size();

    // dp[mask] 将存储字符集为 mask 的子集所能构成的最长无重复子串长度
    vector<int> dp(1 << 20, 0);

    // Step 1: 预处理，计算每个精确mask的最大长度
    for (int i = 0; i < n; i++) {
        int mask = 0;
        for (int j = i; j < n; j++) {
            int b = s[j] - 'a';
            // 如果这个字符已经出现过了，就不能再往后扩展了
            if (mask & (1 << b)) 
                break;
            // 把新字符加入到mask中
            mask |= (1 << b);
            // __builtin_popcount 是一个神奇的函数，可以快速计算一个数二进制表示中1的个数
            dp[mask] = max(dp[mask], __builtin_popcount(mask));
        }
    }

    // Step 2: 子集DP (SOS DP)，将信息从子集传递到超集
    for (int b = 0; b < 20; b++) { // 遍历每一位
        for (int mask = 0; mask < (1 << 20); mask++) {
            // 如果 mask 的第 b 位是 1
            if (mask & (1 << b)) {
                // mask 的最优解可能来自它的子集 mask ^ (1 << b)
                dp[mask] = max(dp[mask], dp[mask ^ (1 << b)]);
            }
        }
    }

    // Step 3: 寻找最佳组合
    int ans = 0;
    // 全集mask，即前20个字母都包含
    int full_mask = (1 << 20) - 1;
    
    // 如果不进行翻转，答案就是所有单个子串的最大长度
    // 这一步其实可以合并到下面的循环里，因为当 mask = 0 时，dp[0]=0, dp[full_mask]就是单个子串的最大长度
    if (dp[full_mask] > 0) {
        ans = dp[full_mask];
    }

    for (int mask = 0; mask < (1 << 20); mask++) {
        // 如果dp[mask]存在（即原串中有这个字符集的子串）
        if (dp[mask] > 0) {
            // 找到它的补集
            int other_mask = full_mask ^ mask;
            // 答案就是 mask 的最优解和其补集的最优解之和
            ans = max(ans, dp[mask] + dp[other_mask]);
        }
    }

    cout << ans << endl;
    return 0;
}

跑得快不快呀？ ​

  • 时间复杂度: O(N * C + C * 2^C) 的说。

    • 预处理部分是 O(N * C)，其中 N 是字符串长度 (<= 10^6)，C 是字符集大小 (20)。因为从每个位置出发，最多向右扩展 C 个字符就会遇到重复。
    • 子集DP部分是 O(C * 2^C)，也就是 20 * 2^20，大约是 2千万。
    • 最后找答案是 O(2^C)，大约是 1百万。
    • 总的计算量在可以接受的范围内，不会超时的说！

  • 空间复杂度: O(2^C) 的说。

    • 我们主要用了一个 dp 数组，大小是 2^20，也就是 1048576。一个 int 4个字节，总共大约 4MB，完全没问题！

这次学到了什么喵？ ​

这道题真的非常有趣，它教会了我们几件重要的事情呐：

  1. 问题转化：学会把一个看起来很棘手的操作问题（比如翻转），转化成一个更经典的组合或集合问题。这是成为算法大师的关键一步哦！
  2. 位运算大法好 (Bitmask DP)：当题目中涉及到小规模的集合问题时（比如这里的20个字符），一定要想到用位运算来做状态压缩！它既高效又优雅，是处理子集问题的利器。
  3. 子集DP (SOS DP)：这是一个非常强大的技巧！当你需要快速计算一个集合所有子集的信息时，不要犹豫，用它就对啦！O(C * 2^C) 的效率远胜于朴素的 O(3^C)。
  4. 互补思想：最后一步通过遍历 mask 并查找其补集 complement 来寻找最优解，是一个非常聪明的思路，它完美地利用了我们DP预处理的结果。

希望这篇题解能帮到你，如果还有不懂的地方，随时可以再来问咱哦！一起加油，变得更强吧，喵~ (ฅ'ω'ฅ)

Released under the MIT License.

Copyright © 2024-present Moe