Codeforces Round #311 (Div. 2) A,B,C,D,E - c++编程基础

tf(3 %lld , w); return 0; }

E. Ann and Half-Palindrome

题意：首先题目定义了一个半回文串：一个串是半回文串，当且仅当，这个中间轴左边的奇数位置上的字符与其对称位置上的字符相同，题目给出一个串s，和整数k让你求出s的所有半回文子串中字典序第k大的串，s的长度是5000。

思路：这道题目做起来也可谓是波折满满啊，一开始听刘神说是暴力，就自己敲了一个最最暴力的做法，尼玛啊O（n^3）的方法你怕不怕，然后一算肯定超时啊，就在想怎么来优化，感觉枚举子串的地方没有什么可优化的了，就在想判回文的地方有没有什么可以更快的方法，没想出来（还是太弱了），然后刘神告诉我说用区间dp的思想随便预处理一下就行了，顿时恍然大悟，马上又去改了一发，发现超内存 ->___->,然后刘神有告诉我说用动态字典树啊，然后我就去改了字典树，发现T了~~~~，一看刘神的姿势才发现字典树的插入是O（n）的，但是他没插入一个就相当于插入了所有的以插入串开头的前缀子串，所以在枚举子串的时候只有枚举头就行了~~~，又改了一发最后才过...

其中字典树的每个节点都多维护一个域用来存，其子树中有多少个半回文串，之后找第K大的串就用类似平衡树上dfs查找某个节点的思想不断的查找左右子树就行了，其中还有一些小的细节需要注意~~~

code：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #define clr(x, y) memset(x, y, sizeof x) #define inf 1000000000 using namespace std; string s; int k; vector
        
          vv; int dp[5005][5005]; int dfs(int i, int j) { if (i == j) return dp[i][j] = 1; if (j < i) return dp[i][j] = 1; if (dp[i][j] != -1) return dp[i][j]; if (dfs(i+2,j-2) && s[i] == s[j]) return dp[i][j] = 1; return dp[i][j] = 0; } class Trie { public: int flag; int num; Trie* next[2]; Trie() { flag=0; num=0; next[0] = next[1] = 0; } } * root; int dfs(Trie * p) { if (!p) return 0; p->num += p->flag; p->num += dfs(p->next[0]); p->num += dfs(p->next[1]); return p->num; } string solve(Trie * p, int k) { Trie * lson = p->next[0], *rson = p->next[1];; int lnum, rnum; if (lson == 0) lnum = 0; else lnum = lson->num; if (rson == 0) rnum = 0; else rnum = rson->num; if (p->flag >= k) return ; else if (lnum + p->flag >= k) return a + solve(lson,k-p->flag); else return b + solve(rson, k - lnum - p->flag); } void Trie_insert(int st, int ed) { Trie* p= root; for(int i = st; i < ed; i++) { int index; if (s[i] == 'a') index = 0; else index = 1; if(!p->next[index]){ p->next[index]=new Trie; } p=p->next[index]; if (dfs(st,i)) p->flag++; } } int main() { cin>>s>>k; int len = s.length(); clr(dp, -1); root = new Trie(); for (int i = 0; i < len; i++) { Trie_insert(i, len); } dfs(root); cout<< solve(root,k) <
         
          ?
          补完了一场题目，给自己加个油~~
          ?

Codeforces Round #311 (Div. 2) A,B,C,D,E(二)