CountNewStrings - 题解

标签与难度

标签: 动态规划, 组合计数, 哈希, 二维数点, 扫描线难度: 2300

题目大意喵~

主人你好呀，这道题是关于字符串的呐~ 题目定义了一个奇妙的函数 f(S, x, y)，它会生成一个新字符串 T。T 的第 k 个字符是原字符串 S 从第 x 位到第 x+k-1 位的最大字符，喵~

然后题目又定义了一个更复杂的集合 A，里面的字符串都是由两次 f 函数调用生成的：f(f(S, x1, y1), x' y')，其中 x' 和 y' 是由 x1, x2, y2 计算得出的。我们的任务就是，对于一个给定的只包含小写字母 'a' 到 'j' 的字符串 S，找出集合 A 中有多少个不同的字符串，也就是 |A| 的值，的说。

解题思路分析

这道题看起来有点吓人，特别是那个嵌套的函数 f(f(...))，让人头晕眼花，对吧？但是别怕，我们我的直觉告诉我，这种复杂的定义背后一定有更简单的本质，喵~ 让我们一步一步把它拆解开来！

化繁为简的第一步：解构 `f` 函数

首先，我们来研究一下两次 f 调用到底在做什么。令 S' = f(S, x1, y1)。最终的字符串是 T' = f(S', x2-x1+1, y2-x1+1)。根据 f 的定义，T' 的第 k 个字符是 S' 从第 x2-x1+1 位到 x2-x1+1 + k-1 位的最大值。而 S' 的第 j 个字符又是 S 从 x1 到 x1+j-1 的最大值。把它们组合起来，T' 的第 k 个字符就是：

\max_{j=x_2-x_1+1}^{x_2-x_1+1+k-1} \left( \max_{i=x_1}^{x_1+j-1} S_i \right)

因为取最大值的区间是不断扩大的，所以这个复杂的式子可以简化为取最大区间的最大值，也就是当 j 取到最大值时的那个区间：

\max_{i=x_1}^{x_1 + (x_2-x_1+1+k-1) - 1} S_i = \max_{i=x_1}^{x_2+k-1} S_i

这说明最终生成的字符串 T' 的第 k 个字符，只和 x1、x2 和 k 有关！

现在我们来定义一个更清晰的辅助字符串。对于每个起始位置 i（ $1 \le i \le n$ ），我们构造一个字符串 M_i，它的第 k 个字符是 S 从 i 到 i+k-1 的前缀最大值。

M_i[k] = \max(S_i, S_{i+1}, \dots, S_{i+k-1})

那么，我们之前推导出的 T'，它的第 k 个字符是 max(S[x1...x2+k-1])。如果我们把 T' 的所有字符和 M_{x1} 比较一下： T'[k] = max(S[x1...x2+k-1]) = M_{x1}[x2-x1+k]。这说明，T' 其实就是 M_{x1} 的一个子串！

因为 x1, x2, y2 可以取遍所有满足 1 <= x1 <= x2 <= y2 <= n 的值，这就意味着集合 A 其实就是所有 M_1, M_2, \dots, M_n 这 n 个字符串的所有不同子串的集合！

问题转化成：计算字符串集合 {M_1, M_2, \dots, M_n} 的所有不同子串的数量。

观察 `M_i` 的性质

M_i 是由前缀最大值构成的，所以它有一个非常好的性质：非递减！也就是说 M_i[k] \le M_i[k+1]。例如，如果 S = "dbca":

M_1 是 "dbca" 的前缀最大值，得到 "dddd"。
M_2 是 "bca" 的前缀最大值，得到 "bcc"。
M_3 是 "ca" 的前缀最大值，得到 "cc"。
M_4 是 "a" 的前缀最大值，得到 "a"。

因为 M_i 是非递减的，所以 M_i 中所有相同的字符都是连在一起的。比如 "bcc"，'b' 都在一起，'c' 都在一起。

计数策略：分类讨论！

直接用后缀自动机（SAM）等方法处理 n 个总长度可能达到 $O(n^2)$ 的字符串会超时。我们需要更巧妙的计数方法。一个经典的思路是分类贡献。我们可以根据子串的特征来分类计数。

第一类：只含一种字符的子串

这种子串形如 c^k（k 个 c）。对于每种字符 c（'a' 到 'j'），它能贡献的不同子串就是 c, cc, ccc, ...，直到最长的那个。所以我们只需要找到对于每个 c，它连续出现的最长长度是多少。

由于 M_i 中所有相同的字符都扎堆出现，所以 c 在 M_i 中的出现次数，就等于它连续出现的最大长度！于是，对于字符 c，它能构成的最长子串长度就是 $\max_{i=1 \dots n} (\text{`c` 在 `M_i` 中的出现次数})$ 。我们把所有字符的这个最大长度加起来，就得到了第一类子串的总数。

为了计算“c 在 M_i 中的出现次数”，我们可以用动态规划。设 dp[i][c] 为字符 c 在 M_i 中出现的次数。

M_i 的第 k 个字符是 max(S[i], M_{i+1}[k-1]) (对于 k>1)。
M_i 的第 1 个字符是 S[i]。由此可以得到递推关系：
如果 c > S[i], M_i 中出现 c 的位置，当且仅当 M_{i+1} 中对应位置也是 c。所以 dp[i][c] = dp[i+1][c]。
如果 c < S[i], M_i 中不可能出现 c，因为所有值都至少是 S[i]。所以 dp[i][c] = 0。
如果 c == S[i], M_i 的第 1 位是 c。之后，只要 M_{i+1} 的字符不大于 c，在 M_i 中都会变成 c。所以 dp[i][c] = 1 + \sum_{j \le c} dp[i+1][j]。

我们可以从 i=n 倒推到 i=1，算出所有的 dp[i][c] 值。

第二类：含有多种字符的子串

这种子串至少包含两种不同的字符。由于 M_i 非递减，这样的子串一定形如 l...l (中间部分) r...r，其中 l 是子串的最小字符，r 是最大字符，且 l < r。中间部分只包含 l 到 r 之间的字符。

一个这样的子串由三部分唯一确定：

开头的 l 的数量。
结尾的 r 的数量。
中间部分的具体内容。

我们可以遍历所有可能的最小/最大字符对 (l, r)。对于固定的 (l, r)，我们来数一下能产生多少新的子串。

对于一个 M_i，它的“中间部分”结构（即 l 和 r 之间的字符 l+1, \dots, r-1 的出现次数）是固定的。我们可以用一个哈希值来表示这个结构，这个哈希值由 (dp[i][l+1], dp[i][l+2], ..., dp[i][r-1]) 这个向量决定。

现在，我们将所有 n 个 M_i 字符串，按照它们中间部分的哈希值进行分组。

在同一个组里，所有 M_i 的中间部分结构都一样。那么，它们生成的 l...r 型子串，只由开头 l 的数量和结尾 r 的数量决定。对于组里的一个 M_i，它能提供的 l 的数量范围是 [1, dp[i][l]]，r 的数量范围是 [1, dp[i][r]]。这相当于在二维平面上提供了一个矩形区域 (0, 0) 到 (dp[i][l], dp[i][r]) 内的所有整点。

我们的问题就变成了：对于同一个分组内的所有 M_i，它们提供的矩形区域 [1, dp[i][l]] \times [1, dp[i][r]] 的并集面积是多少？

这是一个经典的计算几何问题！我们可以用扫描线或者更简单的方法解决。

将组内的所有矩形（由 (dp[i][l], dp[i][r]) 定义）收集起来。
为了方便计算，我们先对这些矩形进行筛选。如果矩形 A 完全被矩形 B 包含，A 就没有贡献了。我们可以按 dp[i][l] 降序排序，如果 dp[i][l] 相同则按 dp[i][r] 降序排序。然后遍历一遍，只保留那些 dp[i][r] 比之前所有矩形的 dp[i][r] 都大的矩形。
这样我们就得到了一个“天际线”，其中矩形 j 的 l-长度比 j+1 大，r-长度比 j+1 小。
最后，我们把这个天际线下的面积加起来，就是这个分组贡献的新的子串数量啦！

把所有 (l, r) 对的贡献和第一类的贡献加起来，就是最终的答案了，喵~

代码实现

这是我根据上面的思路，精心重构的代码哦！希望能帮助到你，喵~

cpp

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

using namespace std;

// 使用双哈希更安全，喵~
using ull = unsigned long long;
const ull BASE1 = 131; // 质数1
const ull BASE2 = 137; // 质数2
const ull MOD1 = 1e9 + 7;
const ull MOD2 = 1e9 + 9;

struct HashValue {
    ull h1, h2;
    bool operator<(const HashValue& other) const {
        if (h1 != other.h1) return h1 < other.h1;
        return h2 < other.h2;
    }
};

struct Rectangle {
    int width, height;
};

// 用于排序矩形，先按宽度降序，再按高度降序
bool compareRectangles(const Rectangle& a, const Rectangle& b) {
    if (a.width != b.width) {
        return a.width > b.width;
    }
    return a.height > b.height;
}

int main() {
    // 加速输入输出，喵~
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string s;
    cin >> s;
    int n = s.length();
    int alphabet_size = 10; // 'a' to 'j'

    // dp[i][c] 表示字符 c 在 M_i 中的出现次数
    vector<vector<long long>> char_counts(n + 1, vector<long long>(alphabet_size, 0));

    // 从 i = n-1 倒推到 0
    for (int i = n - 1; i >= 0; --i) {
        int current_char_val = s[i] - 'a';

        // 继承 i+1 的结果
        if (i + 1 < n) {
            char_counts[i] = char_counts[i + 1];
        } else {
            // base case for i = n-1, M_n只有一个字符
            fill(char_counts[i].begin(), char_counts[i].end(), 0);
        }

        // 计算 M_i 中 S[i] 这个字符的个数
        long long count_for_current_char = 1; // S[i] 本身
        if (i + 1 < n) {
            for (int c = 0; c <= current_char_val; ++c) {
                count_for_current_char += char_counts[i + 1][c];
            }
        }
        
        // 更新 dp 表
        char_counts[i][current_char_val] = count_for_current_char;
        // 小于 S[i] 的字符在 M_i 中不会出现
        for (int c = 0; c < current_char_val; ++c) {
            char_counts[i][c] = 0;
        }
    }

    long long total_distinct_substrings = 0;

    // Case 1: 只含一种字符的子串
    for (int c = 0; c < alphabet_size; ++c) {
        long long max_len = 0;
        for (int i = 0; i < n; ++i) {
            max_len = max(max_len, char_counts[i][c]);
        }
        total_distinct_substrings += max_len;
    }

    // Case 2: 含有多种字符的子串
    // 遍历所有可能的最小字符 l 和最大字符 r
    for (int l = 0; l < alphabet_size; ++l) {
        for (int r = l + 1; r < alphabet_size; ++r) {
            map<HashValue, vector<Rectangle>> groups;

            // 根据中间部分的哈希值分组
            for (int i = 0; i < n; ++i) {
                if (char_counts[i][l] > 0 && char_counts[i][r] > 0) {
                    HashValue current_hash = {0, 0};
                    for (int c = l + 1; c < r; ++c) {
                        current_hash.h1 = (current_hash.h1 * BASE1 + char_counts[i][c]) % MOD1;
                        current_hash.h2 = (current_hash.h2 * BASE2 + char_counts[i][c]) % MOD2;
                    }
                    groups[current_hash].push_back({(int)char_counts[i][l], (int)char_counts[i][r]});
                }
            }

            // 对每个分组计算矩形并集的面积
            for (auto const& [hash, rects] : groups) {
                vector<Rectangle> current_rects = rects;
                sort(current_rects.begin(), current_rects.end(), compareRectangles);

                // 筛选出构成天际线的矩形
                vector<Rectangle> skyline;
                int max_h = -1;
                for (const auto& rect : current_rects) {
                    if (rect.height > max_h) {
                        skyline.push_back(rect);
                        max_h = rect.height;
                    }
                }

                // 计算天际线下方的面积
                long long area = 0;
                int last_w = 0;
                for (int j = skyline.size() - 1; j >= 0; --j) {
                    area += (long long)(skyline[j].width - last_w) * skyline[j].height;
                    last_w = skyline[j].width;
                }
                total_distinct_substrings += area;
            }
        }
    }

    cout << total_distinct_substrings << endl;

    return 0;
}

复杂度分析

时间复杂度: $O(|\Sigma|^2 \cdot n \log n)$
- 计算 char_counts 动态规划表需要 $O(n \cdot |\Sigma|)$ 的时间，其中 $|\Sigma|$ 是字符集大小（这里是10）。
- 计算第一类子串的贡献需要 $O(n \cdot |\Sigma|)$ 。
- 计算第二类子串的贡献是主要部分。我们有 $O(|\Sigma|^2)$ 对 (l, r)。对于每一对，我们遍历 n 个 M_i 来分组，哈希计算需要 $O(|\Sigma|)$ 。分组总共需要 $O(|\Sigma|^2 \cdot n \cdot |\Sigma|) = O(|\Sigma|^3 \cdot n)$ 。
- 之后对每个组进行排序和计算。在最坏情况下，一个组里可能有 $O(n)$ 个元素，排序需要 $O(n \log n)$ 。所以总时间复杂度是 $O(n \cdot |\Sigma| + |\Sigma|^3 \cdot n + |\Sigma|^2 \cdot n \log n)$ 。因为 $|\Sigma|=10$ 是个小常数，所以复杂度可以接受，约为 $O(n \log n)$ 乘以一个关于 $|\Sigma|$ 的常数因子。
空间复杂度: $O(n \cdot |\Sigma|)$
- char_counts 表占用了 $O(n \cdot |\Sigma|)$ 的空间。
- map 和 vector 在最坏情况下可能需要存储 $O(n)$ 个元素，所以空间复杂度也是由 char_counts 主导的。

知识点总结

这道题虽然是字符串问题，但最终的解法却充满了组合计数和计算几何的味道，真是一次奇妙的冒险，喵~

问题转化: 解决复杂问题的关键一步是简化问题模型。通过分析函数定义，我们将原问题转化为了一个更标准、更易于理解的“计算多个字符串的不同子串数量”的问题。
动态规划: 我们利用 M_i 和 M_{i+1} 之间的递推关系，通过动态规划高效地预计算出了子串分析所需的关键信息——M_i 中各字符的出现次数。
分类讨论 (贡献法): 将所有子串分为“单字符”和“多字符”两类，分别计算它们的贡献，避免了重复计数，使得逻辑更加清晰。
哈希: 当我们需要根据一个对象的复杂内部结构（这里是 M_i 的中间部分）进行分组时，哈希是一个非常有用的工具。它可以将一个复杂的结构映射成一个简单的数值，便于快速比较和分组。
几何思想 (矩形面积并): 最精彩的部分！我们将一个组合计数问题（统计不同子串数量）映射到了一个二维平面上的几何问题（计算矩形面积并）。这种跨领域的思想转换是算法竞赛中解决难题的一大利器。

希望这篇题解能帮到你哦！解题就像寻宝，只要有耐心和好奇心，总能找到闪闪发光的答案的，加油喵！

CountNewStrings - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

化繁为简的第一步：解构 f 函数 ​

观察 M_i 的性质 ​

计数策略：分类讨论！ ​

代码实现 ​

复杂度分析 ​

知识点总结 ​