题解：P8131 [ICPC 2020 WF] Gene Folding

wyxrl · 2025-08-20 08:14:03 · 题解

题目大意

寻找头尾偶数回文子串，将其折叠，然后组成一个新的字符串，一直到没有一个偶数回文子串时输出剩下的长度。

思路分析

• 这道题需要找回文子串，我们首先考虑 Manacher 算法 来寻找。
• 题目中还有一种情况，例如：在序列 CCCCTTACCCC 中，分别有 CCCC 与 ,CCCC，等几个回文子串，折叠后因题目描述，组成的新的序列可能是 CCTTACC、CCCCTTA、TTACCCC，但是其实这些不影响最终答案，因为如果两个子串能折叠时，它们组成的大的回文子串一定能折叠。

代码思路

如果一个个去寻找回文子串，然后折叠组成新字符串的时间复杂度太高了，那么我们有更高效的解法。

我们可以从首尾依次寻找每个回文子串半径，更新左右端点。

但是可能会有多个重叠偶数回文子串怎办呢？

此时我们需要判断这个回文子串范围有没有超过左右端点。

注意左端点不能超过右端点，否则会重复删除。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=4e6+10;
int sum[MAXN<<1],n,nt;
char s[MAXN<<1],c[MAXN];
void init(){
    int k=0;
    s[k++]='$'; //开头特殊符号 （判断边界） 
    s[k++]='@';
    for (int i=0;i<n;i++){
        s[k++]=c[i];
        s[k++]='@';
    }
    s[k++]='^';//结尾特殊符号 （判断边界）
    nt=k;
}
void manacher(){
    int mr=0,mid=0;
    for(int i=1;i<nt;i++){
        if(i<mr) sum[i]=min(sum[2*mid-i],mr-i);
        else sum[i]=1;
        while(s[i+sum[i]]==s[i-sum[i]])     sum[i]++;
        if(i+sum[i]>mr){
            mr=i+sum[i];
            mid=i;
        }
    }
}

int main (){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>c;
    n=strlen(c);
    init();
    manacher();
    int l=1,r=nt-2;                     //  因为预处理字符串开头是'$'，结尾是'^'，所以有效部分从1到nt-2
    for (int i=2;i<nt-1;i++){           //  处理左端点 
        if (s[i]=='@'&&i-sum[i]+1<= l){
            l=i;
        }
    }
    for (int i=nt-2;i>l;i--){       //处理右端点 注意i>l防止r<l 
        if (s[i]=='@'&&i+sum[i]-1>=r){  
            r=i;
        }
    }
    cout<<(r-l)/2;
    return 0;
}