Moe's CF Life

Appearance

D. A and B and Interesting Substrings - 题解 ​

比赛与标签 ​

比赛: Codeforces Round 294 (Div. 2) 标签: data structures, dp, two pointers 难度: *1800

题目大意喵~ ​

主人你好呀~！这道题是关于寻找一种特殊又有趣的子字符串的喵~

是这样的，我们有一个由小写字母组成的字符串 s，还有26个整数，分别代表从 'a' 到 'z' 每个字母的“价值”。

我们的任务是，找出字符串 s 中有多少个“有趣”的子字符串 t。一个子字符串 t 被认为是“有趣”的，需要同时满足下面两个条件哦：

  1. t 的第一个字母和最后一个字母必须相同，而且它的长度必须大于1。比如说，s 从下标 i 到 j 的子串 s[i...j]，必须满足 s[i] == s[j] 并且 i < j。
  2. 这个子字符串 t 中，除了第一个和最后一个字母，中间所有字母的“价值”总和必须等于0。也就是 s[i+1...j-1] 这一段的价值和为0。

我们要做的就是数出所有这样的子字符串的数量，然后告诉A和B，喵~

解题思路的奇妙旅程！ ​

当本喵第一次看到这道题时，尾巴都兴奋地摇起来了！这种计数问题最有趣了，的说！

一个最直接的想法，就是暴力枚举所有可能的子串起点 i 和终点 j。对于每一对 (i, j)，我们检查 s[i] 是否等于 s[j]，然后再计算中间部分的价值和。但字符串长度有 10^5 这么长，这样做的时间复杂度会是 O(N³)，就算优化一下也会是 O(N²)，肯定会超时的啦，呜...

所以，我们需要更聪明的办法，喵！关键就在于那个“中间部分价值和为0”的条件。看到“区间和”，本喵的DNA就动了！这不就是前缀和大显身手的地方嘛？

让我们定义一个前缀和数组 P。P[k] 表示字符串 s 从开头到第 k 个字符（s[0...k]）的价值总和。 那么，子串 s[i+1...j-1] 的价值和就可以表示为 P[j-1] - P[i]。

于是，我们的条件 sum(values of s[i+1...j-1]) = 0 就华丽变身为： P[j-1] - P[i] = 0 也就是： P[j-1] == P[i]

哇！问题一下子变得清晰起来了！我们现在要找的是满足下面两个条件的下标对 (i, j) 的数量：

  1. s[i] == s[j]
  2. P[i] == P[j-1]

这样一来，我们就可以只遍历一次字符串啦！我们可以用一个循环，把 j 从 0 遍历到 n-1。在处理每个 j 的时候，我们去寻找在它之前有多少个 i 能够和它配对。

可是，怎么快速找到满足条件的 i 呢？我们需要一个数据结构来帮我们记住之前遍历过的位置的信息。具体来说，对于每个 j，我们需要知道： 在 0 到 j-1 的范围里，有多少个下标 i，它对应的字符是 s[j]，并且它的前缀和 P[i] 等于我们当前需要的 P[j-1]？

为了实现这个目标，我们可以用一个“按字符分类的计数器”。一个 std::vector<std::map<long long, int>> counts(26) 就非常合适！ counts[c] 是一个 map，它专门记录字符 c 的信息。 map 的 key 是前缀和的值，value 是这个前缀和值出现过的次数。

所以，我们的算法流程就是这样的喵：

  1. 初始化总答案 ans = 0，以及一个变量 prefix_sum 来实时计算前缀和。prefix_sum 在处理 j 之前，它的值就等于 P[j-1]。
  2. 初始化 counts 数组，里面是26个空的 map。
  3. 开始从 j = 0 到 n-1 遍历字符串 s： a. 令当前字符为 c = s[j]。 b. 我们要找的 i 需要满足 P[i] == P[j-1]。此时的 prefix_sum 正好就是 P[j-1] 的值。 c. 我们就在 counts[c - 'a'] 这个 map 里查找键为 prefix_sum 的值。这个值就是到目前为止，我们已经遇到的、字符为 c 且前缀和为 prefix_sum 的 i 的数量。把这个数量加到 ans 上。 d. 查询结束了，现在要把当前位置 j 的信息也记录下来，供后面的 j 查询。首先，更新前缀和，让它包含当前字符的价值：prefix_sum += values[c - 'a']。现在 prefix_sum 的值就是 P[j] 了。 e. 然后，在 counts[c - 'a'] 这个 map 里，将键为 P[j] (也就是更新后的 prefix_sum) 的值加一。counts[c - 'a'][prefix_sum]++。
  4. 循环结束后，ans 就是我们想要的答案啦！是不是很优雅呢，喵~

代码实现喵！ ​

下面就是把这个思路变成现实的代码啦，本喵已经加上了详细的注释，希望能帮到你哟！

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

// 这是解决问题的主函数喵~
void solve() {
    // 首先，读取从'a'到'z'每个字母的价值
    std::vector<long long> values(26);
    for (int i = 0; i < 26; ++i) {
        std::cin >> values[i];
    }
    
    // 然后读取我们的目标字符串 s
    std::string s;
    std::cin >> s;
    
    int n = s.length();
    
    // 我们要计算满足条件的子串 s[i...j] 的数量，条件是：
    // 1. i < j
    // 2. s[i] == s[j]
    // 3. 中间部分 s[i+1...j-1] 的价值和为 0
    //
    // 设 P[k] 为 s[0...k] 的前缀价值和。
    // 那么 s[i+1...j-1] 的价值和就是 P[j-1] - P[i]。
    // 条件3就变成了 P[j-1] - P[i] == 0，也就是 P[j-1] == P[i]。
    //
    // 我们可以用一个循环遍历 j (从 0 到 n-1)，对于每个 j，我们去数有多少个 i < j 满足条件。
    //
    // `counts[c]` 是一个 map，其中：
    //   - key: 是一个前缀和 P
    //   - value: 是这个前缀和 P 在之前的遍历中（对于字符 'a' + c）出现过的次数
    std::vector<std::map<long long, int>> counts(26);
    
    long long ans = 0;
    long long prefix_sum = 0; // 这个变量在处理第 j 个元素之前，存储的是 P[j-1] 的值
    
    // 遍历整个字符串，j 是当前处理的字符的下标
    for (int j = 0; j < n; ++j) {
        int char_idx = s[j] - 'a';
        
        // 对于一个有趣的子串 s[i...j]，需要满足 P[j-1] == P[i]。
        // 在循环开始时，`prefix_sum` 存储的正是 P[j-1]。
        // 我们查找对于当前字符 s[j]，之前有多少个位置 i 满足 s[i] == s[j] 且 P[i] == P[j-1]。
        if (counts[char_idx].count(prefix_sum)) {
            ans += counts[char_idx][prefix_sum];
        }
        
        // 更新 prefix_sum，使其成为 P[j]，为下一次迭代做准备。
        prefix_sum += values[char_idx];
        
        // 记录一下：在位置 j，字符是 s[j]，其对应的前缀和是 P[j]。
        // 这样，当未来的某个 j' 遇到相同的字符时，就可以查到我们现在记录的这个点了！
        counts[char_idx][prefix_sum]++;
    }
    
    std::cout << ans << std::endl;
}

int main() {
    // 使用快速I/O让程序跑得更快一点，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    solve();
    
    return 0;
}

复杂度分析的说 ​

  • 时间复杂度: O(N * log N) 的说。 我们对长度为 N 的字符串只进行了一次遍历。在循环的每一步中，我们都对 std::map 进行了一次查找和一次插入操作。std::map 是基于红黑树实现的，所以它的操作时间复杂度是 O(log K)，其中 K 是 map 中元素的数量。在最坏的情况下，K 可能会接近 N。所以总的时间复杂度就是 O(N * log N) 啦。如果用 std::unordered_map 的话，平均时间复杂度可以达到 O(N) 哦！

  • 空间复杂度: O(N) 的说。 我们用了一个 counts 数组，它包含了26个 map。在最坏的情况下，字符串中每个位置的前缀和都不同，所以这26个 map 中总共会存储 N 个键值对。因此，我们需要的额外空间和字符串的长度 N 是成正比的，也就是 O(N)。

知识点与总结，喵~ ​

这道题真是太棒了，它完美地展示了如何将一个看似复杂的问题变得简单可解，呐！

  1. 核心思想：前缀和 这是解决本题的钥匙！前缀和是处理区间和问题的强大工具，能将 O(N) 的求和操作降到 O(1)，是算法竞赛中必须掌握的基础技巧之一。

  2. 数据结构的选择：Map/哈希表 当我们发现需要根据多个条件（字符种类和前缀和值）来快速计数和查询时，使用 map 或者 unordered_map 是一个非常自然的选择。它帮助我们将“在 j 之前”的信息有效地组织起来。

  3. 问题转化能力 从“中间价值和为0”转化到“P[j-1] == P[i]”，是解题中最重要的一步。学会识别问题模式并将其转化为我们熟悉的模型（比如前缀和、图论、动态规划等），是提升解题能力的关键哦。

  4. 一次遍历（One-Pass）算法 我们的解法只遍历了一遍字符串，边遍历边计算答案。这种“动态规划”或者说“递推”的思想，一边处理当前状态，一边为未来状态更新信息，非常高效，值得学习！

希望这篇题解能对主人有所帮助！要继续加油，在算法的世界里不断探索哦！喵~ >w<

Released under the MIT License.

Copyright © 2024-present Moe