程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Codeforces Round #311 (Div. 2) E. Ann and Half-Palindrome (DP+字典樹)

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

編輯：C++入門知識

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

題目地址：傳送門
先用dp求出所有的符合要求的半回文串，標記出來。然後構造字典樹。然後再dfs一遍求出所有節點的子樹和，最後搜一遍就能找出第k個來了。
代碼如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
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;inext[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