Codeforces Round #311 (Div. 2) E. Ann and Half-Palindrome (DP+字典树)

本文主要是介绍Codeforces Round #311 (Div. 2) E. Ann and Half-Palindrome (DP+字典树)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目地址：传送门
先用dp求出所有的符合要求的半回文串，标记出来。然后构造字典树。然后再dfs一遍求出所有节点的子树和，最后搜一遍就能找出第k个来了。
代码如下：

#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
#include <time.h>
using namespace std;
#define LL __int64
#define pi acos(-1.0)
//#pragma comment(linker, "/STACK:1024000000")
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const double eqs=1e-9;
const int MAXN=400000+10;
int ok[5001][5001];
int k, cnt;
char s[6000], str[6000];
struct node
{int flag, sum;node *next[2];
};
node *newnode()
{int i;node *p=new node;for(i=0;i<2;i++){p->next[i]=NULL;}p->flag=0;p->sum=0;return p;
}
void Insert(int st, int len, node *root)
{int i, x;node *p=root;for(i=st;i<len;i++){x=s[i]-'a';if(p->next[x]==NULL)p->next[x]=newnode();p=p->next[x];if(ok[st][i]) {p->flag++;p->sum++;}}
}
void dfs(node *u)
{for(int i=0;i<2;i++){if(u->next[i]!=NULL){dfs(u->next[i]);u->sum+=u->next[i]->sum;}}
}
void seach(node *root)
{node *p=root;while(1){k-=p->flag;if(k<=0){return ;}if(p->next[0]!=NULL){if(p->next[0]->sum>=k){str[cnt]='a';p=p->next[0];cnt++;continue ;}else k-=p->next[0]->sum;}str[cnt]='b';p=p->next[1];cnt++;}
}
int main()
{int i, j, len, h;while(scanf("%s",s)!=EOF){scanf("%d",&k);len=strlen(s);memset(ok,0,sizeof(ok));for(i=0;i<len;i++){ok[i][i]=1;if(i<len-1&&s[i]==s[i+1]) ok[i][i+1]=1;if(i<len-2&&s[i]==s[i+2]) ok[i][i+2]=1;if(i<len-3&&s[i]==s[i+3]) ok[i][i+3]=1;}for(i=5;i<=len;i++){for(j=0;j<len-i+1;j++){h=j+i-1;if(s[j]==s[h]&&ok[j+2][h-2]) ok[j][h]=1;}}node *root;root=newnode();for(i=0;i<len;i++){Insert(i, len, root);}dfs(root);cnt=0;seach(root);for(i=0;i<cnt;i++){printf("%c",str[i]);}puts("");}return 0;
}