CF335B 题解

getchar_unlocked · 2025-02-16 18:12:54 · 题解

题目传送门

思路

首先考虑如何计算最长回文子序列的长度。不难想到可以作区间 DP，f_{l,r} 表示区间 [l,r] 中的最长回文子序列的长度。易得出转移式：

然而 n\le5\times10^4，无法通过。其实题目中要求，当最长回文子序列的长度 \ge100 时，输出一个长度为 100 的子序列即可。所以当 n\ge2575 时，必然有一种字母出现过 100 或更多次（抽屉定理），找到这个字母并输出 100 次即可。

剩下的情况输出时可以 dfs。dfs 中分为两种情况：

• 如果 s_l=s_r 且 f_{l,r}=f_{l+1,r-1}+2：这说明 [l,r] 是由 [l+1,r-1] 转移而来的，一定能使答案序列最长，故输出 s_l 后，\operatorname{dfs}(l+1,r-1)，再输出 s_r。
• 否则找到一个满足 s_l=s_{r-1} 或者 s_{l+1}=s_r 的条件 dfs。如果都不满足就随便 dfs 一个。

然而这样做仍然存在问题，因为答案子序列的长度可能 \ge100。故在 dfs 中增加一维 C，表示还可以拼接多少个字符。到终止时，若 C=0，返回一个空串；否则 C=1，返回 s_l 或 s_r 中任意一个，因为回文串中间的字符不影响结果。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=5e4+10,M=2.6e3+10;
char s[N];
int dp[M][M],tong[128];
string dfs(int l,int r,int cnt){
    if(!cnt)
        return "";
    if(cnt==1)
        return string(1,s[l]);
    if(s[l]==s[r]&&dp[l][r]==dp[l+1][r-1]+2)
        return s[l]+dfs(l+1,r-1,cnt-2)+s[r];
    if(dp[l][r]==dp[l][r-1])
        return dfs(l,r-1,cnt);
    return dfs(l+1,r,cnt);
}
int main(){
    scanf("%s",s+1);
    int n=strlen(s+1);
    if(n<=2574){
        for(int i=1;i<=n;++i)
            dp[i][i]=1;
        for(int len=2;len<=n;++len)
            for(int l=1;l+len-1<=n;++l){
                int r=l+len-1;
                if(s[l]==s[r])
                    dp[l][r]=dp[l+1][r-1]+2;
                else dp[l][r]=max(dp[l+1][r],dp[l][r-1]);
            }
        string ans=dfs(1,n,min(100,dp[1][n]));
        for(char ch:ans)
            printf("%c",ch);
        printf("\n");
        return 0;
    }
    for(int i=1;i<=n;++i)
        ++tong[s[i]];
    for(char i='a';i<='z';++i)
        if(tong[i]>=100){
            for(int j=1;j<=100;++j)
                printf("%c",i);
            printf("\n");
            return 0;
        }
    return 0;
}