自动搬运

查看原文

来自洛谷，原作者为

	John_yangliwu 锻者，自锥也

搬运于2025-08-24 21:31:18，当前版本为作者最后更新于2021-03-18 20:16:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

Step 1

首先求出所有回文子串。

注意到 $|SS|\le2000$，我们可以用 $O(n^2)$ 的 DP 求解。

定义 bool 类型数组 $dp$，$dp[i][j]$ 表示 $SS[i\sim j]$ 是否为回文子串。

状态转移方程：

$dp[i][j]=\begin{cases}true\ \ \ \ \ \ \ (dp[i+1][j-1]=true,\ SS[i]=SS[j])\\false \ \ \ \ \ (other\ cases)\end{cases}$

理解：

一段子串为回文，当且仅当其首尾相同，且抹去首尾剩下部分也是回文。

Step 2

其次，求出互不相干的回文子串数量。只要对每个回文子串，求出首位在其末位后的回文子串数量，再求和就可以了。

所以我们开一个桶 $cnt$，首先让 $cnt[i]$ 表示首位为 $i$ 的回文子串数量，其次，对其求后缀和。此时 $cnt[i]$ 表示末尾在 $i$ 之后的回文子串数量。最后统计 $\sum\limits^{size}_{i=1}cnt[palin[i].second+1]$ 即可。其中 $size$ 为回文子串数量，$palin$ 是 pair<int, int> 类型数组，$first$ 和 $second$ 分别代表回文子串的首位与末位。

Tips

要开 long long。

代码

#include <iostream>
#include <cstring>
#include <vector>
#define ll long long
using namespace std;

const int N = 2005;
bool dp[N][N];
ll cnt[N];
vector<pair<int, int> > palin;

int main() {
    string str; cin >> str;
    memset(dp, true, sizeof(dp));
	
    //枚举回文子串长度
    for(int len = 1; len <= str.length(); len++) {
        //枚举左端点
        for(int l = 0; l + len - 1 < str.length(); l++) {
            int r = l + len - 1;//右端点
            //不符合要求
            if(!dp[l + 1][r - 1] || str[l] != str[r]) {
                dp[l][r] = false; continue;
            }
            //发现回文子串
            palin.push_back({l, r}); 
            //更新以 l 为首位的回文子串数量
            cnt[l]++;
        }
    }

    ll res = 0;
    //求后缀和
    for(int i = str.length() - 1; i >= 0; i--)
        cnt[i] += cnt[i + 1];

    //最终统计，求与 palin[i] 不相干的回文子串数量
    for(int i = 0; i < palin.size(); i++)
        res += cnt[palin[i].second + 1];
    cout << res << endl;
    return 0;
}

AC记录

$\large\text{THE\ \ END}$