Codeforces Round 311 Div2 E Ann and Half 回文串 + 字典樹 + DP

問題

給定字符串 s (|s|≤5000)，定義「半回文」：對所有奇數位置 i，s[i] == s[n-i+1]。求所有半回文子串按字典序第 k 個。

兩階段解法

1. DP 預處理所有半回文子串：ok[l][r] 表示 s[l..r] 是否半回文
   • 長度 1,2 直接判斷
   • ok[l][r] = (s[l]==s[r]) && ok[l+2][r-2]（跳過偶數位）
2. 字典樹存儲所有半回文子串：
   • 每個節點存 cnt（以此節點結尾的半回文串數）、sum（子樹總數）
   • 插入每個起位的所有半回文子串
   • DFS 計算 sum
   • 按字典序遍歷找第 k 個

代碼關鍵部分

bool ok[5005][5005];
struct TrieNode {
    int cnt=0, sum=0;
    TrieNode* ch[2]={nullptr,nullptr};
};

void insert(int l, int r, TrieNode* root) {
    TrieNode* p = root;
    for (int i = l; i <= r; ++i) {
        int c = s[i]-'a';
        if (!p->ch[c]) p->ch[c] = new TrieNode();
        p = p->ch[c];
        if (ok[l][i]) { p->cnt++; p->sum++; }
    }
}

void dfs(TrieNode* u) {
    for (int c=0;c<2;++c) if (u->ch[c]) {
        dfs(u->ch[c]);
        u->sum += u->ch[c]->sum;
    }
}

void kth(TrieNode* u, int& k, string& ans) {
    k -= u->cnt;
    if (k <= 0) return;
    for (int c=0;c<2;++c) if (u->ch[c]) {
        if (u->ch[c]->sum >= k) {
            ans += 'a'+c;
            kth(u->ch[c], k, ans);
            return;
        } else k -= u->ch[c]->sum;
    }
}

複雜度

• DP：O(n²) = 2.5e7，邊界通過優化可行
• 字典樹節點數 ≤ 總半回文子串長度和，O(n²)
• 查找第 k 個：O(答案長度)

優化技巧

• DP 只需處理奇數長度或按長度遞增
• 字典樹節點池預分配避免 new 開銷
• 內存限制注意：5000² bool ≈ 25MB，節點池約 2×總長度