codeforces 557E Ann and Half-Palindrome

题意简述

给定一个字符串（长度不超过5000 且只包含a、b）求满足如下所示的半回文子串中字典序第k大的子串

t_i = t_{|t| - i + 1(|t|为字符串长度)}  

----------------------------------------------------------------------------------

比赛时看到回文串 再看到字典序第k大 满满的后缀数组一类的算法的即视感

考虑到编程复杂度以及自己本来就不熟练 于是直接放弃了

结果比赛完后听说不少人都是直接上trie树后暴力求解 才发现字符串长度不超过5000

然而没注意到只包含a、b 当成了包含所有小写字母以至于脑洞大开

去想什么通过中序遍历来压缩trie树空间之类的（这个只是理论上还不错 还没去实现过）

----------------------------------------------------------------------------------

正解的话 先可以通过DP求出符合要求的子串的左右端点

然后直接在trie树里统计即可

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#define rep(i,n) for(int i=1;i<=n;++i)
#define imax(x,y) (x>y?x:y)
#define imin(x,y) (x<y?x:y)
using namespace std;
const int N=5010;
struct trie
{
    int cnt;
    int nexte[2];
}a[N*N>>1];
bool f[N][N];
char s[N],ans[N];
int k,n,num=0,lans=0;
bool flag=0;
void add_trie(int x,int l,int r)
{
    int y=s[r]-'a';
    if(!a[x].nexte[y])
    a[x].nexte[y]=++num;
    if(f[l][r])
    ++a[a[x].nexte[y]].cnt;
    if(r<n)
        add_trie(a[x].nexte[y],l,r+1);
}
void inquiry_trie(int x)
{
    for(int i=0;i<2;++i)
    if(a[x].nexte[i])
    {
        if(a[a[x].nexte[i]].cnt)
        {
            k-=a[a[x].nexte[i]].cnt;
            a[a[x].nexte[i]].cnt=0;
            if(k<=0)
            {
                flag=1;
                ans[++lans]=i+'a';
                return;
            }
        }
        inquiry_trie(a[x].nexte[i]);
        if(flag)
        {
            ans[++lans]=i+'a';
            return;
        }
    }
}
int main()
{
    scanf("%s%d",s+1,&k);
    n=strlen(s+1);
    rep(i,n)
    {
        f[i][i]=1;
        if(i+1<=n&&s[i]==s[i+1])f[i][i+1]=1;
        if(i+2<=n&&s[i]==s[i+2])f[i][i+2]=1;
        if(i+3<=n&&s[i]==s[i+3])f[i][i+3]=1;
    }
    for(int i=5;i<=n;++i)
    for(int j=1;j+i-1<=n;++j)
    if(s[j]==s[j+i-1]&&f[j+2][j+i-3])
    f[j][j+i-1]=1;
    rep(i,n)
    add_trie(0,i,i);
    inquiry_trie(0);
    for(int i=lans;i;--i)
        printf("%c",ans[i]);
    return 0;
}