哈喽，主人，下午好喵~ (ฅ´ω`ฅ)

今天咱要一起解决的是一道关于字符串的有趣问题，叫做 "Flexible String" 哦。它看起来可能有点复杂，但别担心，只要跟着咱的思路一步步来，就会发现它其实是一只很温顺的小猫咪呢~

题目大意

首先，我们来理解一下题目到底在说什么吧，喵~

我们有两个长度都是 n 的字符串 a 和 b。然后我们还有一个初始为空的集合 Q。

我们可以对字符串 a 进行一种特殊操作：

1. 选择 a 中的一个位置 i。
2. 把 a[i] 这个字符装进集合 Q 里。
3. 然后把 a[i] 替换成任意一个小写字母 c。

这个操作可以进行任意多次，但是有一个很重要的限制：最终集合 Q 中不同字符的种类数不能超过 k。

我们的目标是，在满足这个限制的前提下，通过操作修改字符串 a，使得新字符串 a 和原始字符串 b 拥有尽可能多的相同子串。我们要输出这个最大数量。

举个栗子🌰： a = "abecca", b = "abxcca", k = 1。 a 和 b 在第 3 个位置不同 (e vs x)。 我们可以选择 a 的第 3 个字符 'e' 进行操作，把它加入 Q，然后替换成 'x'。 这时 Q = {'e'}，大小为 1，满足 k=1 的限制。 修改后的 a 变成了 "abxcca"，和 b 完全一样啦！所有子串都匹配，答案就是 n*(n+1)/2。

是不是感觉有点绕呀？别担心，让咱一点一点给你讲明白喵~

解题思路

这道题最关键的地方，其实是题目给的一个“温柔”的提示：字符串 a 中最多只有 10 种不同的字符。

看到 10 这个小数字，我们的猫猫雷达就响了，喵！这通常是在暗示我们可以用一些跟指数时间复杂度相关的方法，比如暴力枚举！

你想呀，我们的决策核心是什么？就是决定哪些字符可以被我们“牺牲”掉，放进集合 Q 里，从而获得被替换的资格。

1. 确定“可替换字符”的候选名单： 首先，我们把字符串 a 中出现过的所有不同字符都找出来，构成一个候选集合 S_a。根据题意，这个集合的大小 m 不会超过 10。

2. 枚举所有可能性： 我们的任务就是从这个候选集合 S_a 中，选出一个子集，作为我们最终的“可替换字符集”（也就是题目里的集合 Q）。这个子集的大小不能超过 k。 因为 m 最大也只有 10，所以 S_a 的所有子集数量最多是 2^10 = 1024 个。这个数量非常小，我们的计算机可以轻松地把每一种情况都试一遍！

3. 计算每种可能性下的得分： 对于我们枚举的每一种“可替换字符集”，我们都要算一下它能得到多少分（即匹配的子串数量）。 假设我们选定了一个可替换字符集 Q_current（它的size要小于等于k哦）。现在，我们怎么判断新 a 的 a[i] 是否等于 b[i] 呢？

   • 如果原本的 a[i] 就等于 b[i]，那它们当然是匹配的。
   • 如果原本的 a[i] 不等于 b[i]，但 a[i] 这个字符种类在我们选定的 Q_current 里面，那就意味着我们可以把它替换成 b[i]，所以也算作匹配！

   这样，我们就可以得到一个由“匹配”和“不匹配”组成的序列。例如 [匹配, 匹配, 不匹配, 匹配, 匹配, 匹配]。

4. 统计匹配子串数量： 问题来了，怎么快速计算一个 [匹配, 匹配, 不匹配, ...] 序列能产生多少个匹配的子串呢？ 这里有一个小技巧，叫贡献法。我们寻找连续的“匹配”段。如果有一段连续的 L 个“匹配”，那么它能贡献的匹配子串数量就是 L * (L + 1) / 2。 （这个公式怎么来的？在下面的知识点部分咱会详细解释哦~） 我们把所有连续匹配段贡献的子串数量加起来，就是当前这种“可替换字符集”方案下的总得分。

5. 取最大值： 最后，我们在所有（满足 size <= k 的）方案中，找到那个最高的得分，就是我们最终的答案啦！

总结一下思路就是： 枚举 a 中字符的子集 -> 对每个子集，计算匹配得分 -> 取最大得分。完美~ ฅ^•ﻌ•^ฅ

题解代码

下面是解题的 C++ 代码，咱给加上了详细的注释，方便主人理解每一行代码都在做什么哦。

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
#include <numeric>
#include <bit> // C++20, 为了用 std::popcount

// 这是一个让输入输出变快的小魔法喵~
void setup_fast_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
}

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

    // Step 1: 找到字符串a中所有不同的字符。
    // 用 set 可以自动去重，很方便喵~
    std::set<char> distinct_chars_set;
    for (char c : a) {
        distinct_chars_set.insert(c);
    }
    // 把 set 里的字符转存到 vector 里，方便我们用下标访问。
    std::vector<char> distinct_chars(distinct_chars_set.begin(), distinct_chars_set.end());
    int m = distinct_chars.size();

    long long max_total_pairs = 0;

    // Step 2: 用位运算枚举所有字符的子集。
    // 如果有 m 个字符，就有 2^m 个子集。
    int num_subsets = 1 << m; 
    for (int i = 0; i < num_subsets; ++i) {
        // i 就是一个"位掩码"，它的二进制表示了我们选择了哪些字符。
        
        // 检查当前子集的大小是否超过 k。
        // std::popcount(i) 会计算 i 的二进制里有多少个 1，也就是子集的大小。
        if (std::popcount(static_cast<unsigned int>(i)) > k) {
            continue; // 这个组合太大了，不符合要求，跳过！
        }

        // Step 3: 对于当前选定的“可替换”字符集，计算得分。
        // 用一个布尔数组来快速查询某个字符是否可替换。
        bool is_replaceable[26] = {false};
        for (int j = 0; j < m; ++j) {
            // (i >> j) & 1 这个操作是检查 i 的第 j 位是不是 1。
            if ((i >> j) & 1) {
                // 如果是 1，说明第 j 个字符被我们选中了。
                is_replaceable[distinct_chars[j] - 'a'] = true;
            }
        }

        // Step 4: 计算匹配的子串数量。
        // 我们通过寻找连续的匹配段来计算。
        long long current_total_pairs = 0;
        long long current_streak = 0; // 当前连续匹配的长度
        for (int p = 0; p < n; ++p) {
            // 满足下面两个条件之一，就说明 p 位置是匹配的：
            // 1. a[p] 和 b[p] 本来就一样。
            // 2. a[p] 是我们选中的“可替换”字符。
            if (a[p] == b[p] || is_replaceable[a[p] - 'a']) {
                current_streak++;
            } else {
                // 连续匹配中断了！结算上一段的贡献。
                current_total_pairs += current_streak * (current_streak + 1) / 2;
                current_streak = 0; // 重置计数器
            }
        }
        // 循环结束后，别忘了结算最后一段连续匹配的贡献哦！
        // 可不能把最后一段小鱼干给忘了喵！
        current_total_pairs += current_streak * (current_streak + 1) / 2;

        // Step 5: 更新最大值。
        max_total_pairs = std::max(max_total_pairs, current_total_pairs);
    }

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

int main() {
    setup_fast_io();
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

知识点小课堂

这道题用到了几个很有用的小知识，让咱来给你科普一下吧，喵~

1. 位运算与子集枚举 (Bit Manipulation & Subset Enumeration)

这是算法竞赛中非常常见的技巧！当我们要从一个大小为 m 的小集合中，枚举所有可能的子集时，位运算是最高效的方法。

• 核心思想：一个 m 位的二进制数，可以完美地对应一个大小为 m 的集合的子集。

  • 比如集合是 {A, B, C}，m=3。
  • 二进制数 101（十进制的5），第0位和第2位是1，可以代表子集 {A, C}。
  • 二进制数 011（十进制的3），第0位和第1位是1，可以代表子集 {B, C}。（假设A是第2位，B是第1位，C是第0位）
  • 000 代表空集 {}, 111 代表全集 {A, B, C}。

• 如何实现：

  • 1 << m：计算 2^m，也就是子集的总数。
  • for (int i = 0; i < (1 << m); ++i)：这个循环会遍历从 0 到 2^m - 1 的所有整数，这些整数的二进制形式就代表了所有可能的子集。i 就是我们的位掩码 (bitmask)。
  • (i >> j) & 1：这是检查位掩码 i 的第 j 位是否为 1 的标准操作。如果是 1，说明集合中的第 j 个元素被选中了。
  • std::popcount(i) (C++20)：一个超级方便的函数，可以直接数出整数 i 的二进制表示中有多少个 1。这正好就是子集的大小！如果你的编译器不支持 C++20，也可以自己写个循环来数。

2. 贡献法与组合数学

为什么一段长度为 L 的连续匹配，会贡献 L * (L + 1) / 2 个匹配子串呢？

• 想象一下，我们有一排 L 个小鱼干，排成一行。我们要从里面拿出连续的一段。
• 如果我们拿出的子段长度为 1，有 L 种拿法。
• 如果我们拿出的子段长度为 2，有 L-1 种拿法。
• ...
• 如果我们拿出的子段长度为 L，只有 1 种拿法。

总的方法数就是 L + (L-1) + ... + 2 + 1。这是一个等差数列求和，它的公式就是 L * (L + 1) / 2。

在我们的题目里，任何一个在连续匹配段内部的子串，都是一个合法的匹配子串。所以，我们用这个公式来快速计算贡献，而不需要一个一个地去数 (l, r) 对，这样就快多啦！

好啦，这次的题解就到这里啦！主人有没有觉得豁然开朗了呢？只要抓住了“数据范围小 -> 可以枚举”这个关键点，问题就迎刃而解了。下次再遇到类似的问题，也要记得观察数据范围哦！喵~ ( ´ ▽ ` )ﾉ