题解 P1872 【回文串计数】

John_yangliwu · 2021-03-18 20:16:17 · 题解

思路

Step 1

首先求出所有回文子串。

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

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

状态转移方程：

理解：

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

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记录