[H. Queries for Number of Palindromes] - 题解

比赛与标签

比赛: CROC-MBTU 2012, Elimination Round (ACM-ICPC) 标签: dp, hashing, strings 难度: *1800

题目大意喵~

主人你好喵~ 这道题是这样的呐：

首先，我们会拿到一个只包含小写英文字母的字符串 s。然后呢，会有 q 次询问。每一次询问会给我们一对数字 l 和 r，代表一个区间的说。

对于每一次询问 (l, r)，我们需要做的事情就是，找出在子字符串 s[l...r] 中，有多少个子串是回文串，然后把这个数量告诉人家，喵~

最后，把所有询问的结果按顺序输出就可以啦！

举个栗子，如果字符串是 caaaba，询问是 (4, 6)，那么对应的子串就是 aba。aba 的子串里，a (第一个), b, a (第二个), aba 都是回文串，所以总共有 4 个，答案就是 4 啦，的说喵~

思路分析喵~

主人，看到这道题有好多好多的询问（q 可以到 10^6 这么多！），但是字符串长度 n 又不是特别大（最大 5000），本喵的直觉就告诉我，这一定是要我们先做一些预处理，然后才能 O(1) 回答每个询问的，不然肯定会超时的说！

我们的目标是求出任意子串 s[i..j] 中回文子串的数量。这是一个典型的区间问题，很自然地就会想到用动态规划（DP）来解决，呐。

让我们定义一个二维数组 dp[i][j]，表示子串 s[i..j] 中回文子串的总数。这就是我们最终想要的答案！

那么，dp[i][j] 要怎么算出来呢？我们可以试着找找递推关系。一个子串 s[i..j] 里的所有回文串，可以分成两类喵：

那些从 s[i] 开始的回文串。
那些不从 s[i] 开始的回文串。

对于第二类，它们其实就是 s[i+1..j] 这个子串里的所有回文串，对吧？这个数量正好就是 dp[i+1][j]！

那第一类呢？就是那些在 s[i..j] 范围内，并且以 i 为起点的回文串。我们单独把它们的数量算出来，记作 starts_at[i][j]。

这样一来，递推关系就清晰多啦： dp[i][j] = dp[i+1][j] + starts_at[i][j] 这个关系式非常简洁，因为它把 s[i..j] 中的回文串完美地分成了互不重叠的两部分，喵~

现在问题就变成了怎么计算 starts_at[i][j] 和 dp[i+1][j]。dp[i+1][j] 是子问题，我们先来看 starts_at[i][j]。 starts_at[i][j] 是 s[i..j] 中以 i 开头的回文串数量。这不就是一个前缀和（或者说是后缀和？）的概念嘛！ starts_at[i][j] = (以 i 开头的回文串，且结束位置 <= j-1 的数量) + (如果 s[i..j] 本身是回文串，则 +1)。所以，starts_at[i][j] = starts_at[i][j-1] + (s[i..j] 是不是回文串 ? 1 : 0)。

太棒了！现在我们只需要知道对于任意的 i 和 j，s[i..j] 到底是不是回文串。这个问题嘛，也可以用 DP 轻松解决！我们再定义一个布尔类型的二维数组 is_palindrome[i][j]。

长度为 1 的子串 s[i..i] 肯定是回文串。
长度为 2 的子串 s[i..i+1]，当 s[i] == s[i+1] 时是回文串。
对于更长的子串 s[i..j]，它是不是回文串，取决于 s[i] 是否等于 s[j]，并且它去掉首尾字符后的子串 s[i+1..j-1] 是不是回文串。所以递推关系就是：is_palindrome[i][j] = (s[i] == s[j]) && is_palindrome[i+1][j-1]。

好啦，思路完全清晰了！我们的解题三部曲就是：

第一步 (预处理1): 用 O(n^2) 的 DP 计算出 is_palindrome[i][j] 表格，存下所有子串是否为回文串的信息。
第二步 (预处理2): 利用 is_palindrome 表格，通过前缀和的方式，用 O(n^2) 计算出 starts_at[i][j] 表格。
第三步 (预处理3): 利用 starts_at 表格和 dp[i+1][j] 的值，用 O(n^2) 计算出最终的 dp[i][j] 表格。

整个预处理的时间复杂度是 O(n^2)，空间复杂度也是 O(n^2)。对于 n=5000 来说，完全可以接受。之后每次查询 (l, r)，我们只要直接输出 dp[l-1][r-1] 的值就好啦，时间是 O(1) 的说！是不是很优雅呢，喵~

代码实现

cpp

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

// 为了在竞赛中方便一些，本喵把这些变量放在了全局区，喵~
// 在更大的工程里，把它们封装起来会是更好的习惯哦！
std::string s;
int n;
std::vector<std::vector<bool>> is_palindrome; // is_palindrome[i][j] 表示 s[i..j] 是否为回文串
std::vector<std::vector<short>> starts_at;    // starts_at[i][j] 表示 s[i..j] 中以 i 开头的回文串数量
std::vector<std::vector<int>> dp;             // dp[i][j] 表示 s[i..j] 中回文子串的总数，也就是我们的最终答案

void precompute() {
    n = s.length();
    
    // 为DP表格们分配内存，喵~
    // vector<bool> 有特化，会用比特位存储，可以节省空间
    // starts_at 的值不会超过 n，用 short 就够了
    // dp 的值可能会很大，要用 int
    is_palindrome.assign(n, std::vector<bool>(n, false));
    starts_at.assign(n, std::vector<short>(n, 0));
    dp.assign(n, std::vector<int>(n, 0));

    // 第一步：填充 is_palindrome 表格
    // s[i..j] 是回文串的条件是 s[i] == s[j] 并且 s[i+1..j-1] 也是回文串
    // 这里的循环顺序很重要！i 从大到小，j 从小到大，这样可以保证
    // 在计算 is_palindrome[i][j] 时，is_palindrome[i+1][j-1] 已经被算好啦
    for (int i = n - 1; i >= 0; --i) {
        for (int j = i; j < n; ++j) {
            if (i == j) { // 单个字符总是回文
                is_palindrome[i][j] = true;
            } else if (s[i] == s[j]) {
                if (j == i + 1) { // 两个相同字符是回文
                    is_palindrome[i][j] = true;
                } else { // 依赖于内部子串
                    is_palindrome[i][j] = is_palindrome[i + 1][j - 1];
                }
            }
        }
    }

    // 第二步：填充 starts_at 表格
    // starts_at[i][j] 是 s[i..j] 中以 i 开头的回文串数量
    // 这是一个前缀和：starts_at[i][j] = starts_at[i][j-1] + (s[i..j] 是不是回文串)
    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
            short prev_sum = (j > i) ? starts_at[i][j - 1] : 0;
            starts_at[i][j] = prev_sum + (is_palindrome[i][j] ? 1 : 0);
        }
    }

    // 第三步：填充最终的 dp 表格
    // dp[i][j] 是 s[i..j] 中回文子串的总数
    // 递推关系：dp[i][j] = (s[i+1..j]中的回文串数) + (s[i..j]中以i开头的回文串数)
    // 也就是 dp[i][j] = dp[i+1][j] + starts_at[i][j]
    // 这里的循环顺序也很关键！外层 j 从小到大，内层 i 从大到小
    // 这样在计算 dp[i][j] 时，它所依赖的 dp[i+1][j] 已经在同一次外层循环中算好了
    for (int j = 0; j < n; ++j) {
        for (int i = j; i >= 0; --i) {
            if (i == j) {
                dp[i][j] = 1; // 单个字符本身就是1个回文子串
            } else {
                dp[i][j] = dp[i + 1][j] + starts_at[i][j];
            }
        }
    }
}

int main() {
    // 加速一下输入输出，跑得更快喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> s;
    
    // 进行漫长但值得的预处理~
    precompute();

    int q;
    std::cin >> q;
    
    // 开始回答问题！
    bool first_output = true;
    while (q--) {
        int l, r;
        std::cin >> l >> r;
        if (!first_output) {
            std::cout << " ";
        }
        // 题目给的是1-indexed，我们的表格是0-indexed，要转换一下喵
        std::cout << dp[l - 1][r - 1];
        first_output = false;
    }
    std::cout << "\n";

    return 0;
}

复杂度分析

时间复杂度: O(n^2 + q) 的说。
- 预处理部分有三个主要的双重循环，分别用来计算 is_palindrome, starts_at 和 dp 表格。每一个都是 O(n^2) 的。所以总的预处理时间是 O(n^2 + n^2 + n^2) = O(n^2)，这里的 n 是字符串长度。
- 回答询问的部分，我们有 q 次询问，每次询问都只是查询一下预处理好的 dp 表格，是 O(1) 的操作。所以这部分总时间是 O(q)。
- 加起来，总时间复杂度就是 O(n^2 + q) 啦！
空间复杂度: O(n^2) 的说。
- 我们主要用了三个 n x n 的二维数组：is_palindrome, starts_at, dp。所以空间消耗是 O(n^2) 的级别。

知识点总结

解决这个问题，本喵用到了不少好东西呢，总结一下方便主人复习，的说喵~

主要算法思想: 动态规划 (Dynamic Programming)。特别是区间 DP 的思想，通过解决小区间的问题，来一步步构建大区间的答案。
重要数据结构: 二维数组 (2D Array/Vector)，用来存储 DP 状态。这是 DP 问题中最常用的数据结构之一啦。
关键编程技巧:
- 预处理与查询分离: 面对大量查询，先花时间预处理出所有可能的结果，然后快速回答查询，是一种非常重要的优化思想。
- 递推关系设计: 本题的核心在于设计出 dp[i][j] = dp[i+1][j] + starts_at[i][j] 这个巧妙的递推式，它避免了复杂的容斥原理。
- 前缀和思想: starts_at 表格的计算巧妙地运用了前缀和（这里更像是行内的前缀和），把多次查询转化为了简单的加法。
- DP循环顺序: 在写 DP 的时候，一定要注意循环的顺序，确保计算当前状态 dp[i][j] 时，它所依赖的状态（如 dp[i+1][j-1] 或 dp[i+1][j]）已经被计算出来了。
注意事项:
- 索引转换: 题目的输入是 1-based 的，而 C++ 数组是 0-based 的，处理查询时不要忘记 l-1, r-1 哦！
- 数据类型: 注意 dp 数组的值可能会超过 short 的范围，要使用 int 或者 long long 来存储。
扩展应用: 这种“预处理所有子区间的答案”的 DP 方法，可以应用到很多类似的问题上，比如“查询子串中不同字符的数量”、“查询子串中满足某种性质的子序列数量”等等，只要问题的答案可以从更小的子区间递推而来，就可以考虑这种方法喵~

[H. Queries for Number of Palindromes] - 题解 ​

比赛与标签 ​

题目大意喵~ ​

思路分析喵~ ​

代码实现 ​

复杂度分析 ​

知识点总结 ​