Codeforces 1809D
题意：
构造一个长度为 n n n 的字符串 s s s ，均为小写字母。
给出 k k k 个要求，第 i 个要求为 x i , c i {x_i, c_i} xi,ci，表示对于 s [ 1 , x i ] s[1, x_i] s[1,xi] 这个前缀字符串，有恰好 c i c_i ci 个本质不同的回文子串。
数据范围：
-
1 ≤ n ≤ 2 × 1 0 5 , 1 ≤ k ≤ 20 1\leq n\leq 2\times 10^5, 1\leq k\leq 20 1≤n≤2×105,1≤k≤20
-
3 ≤ x 1 < x 2 < ⋯ < x k = n 3\leq x_1<x_2<\cdots<x_k=n 3≤x1<x2<⋯<xk=n
-
3 ≤ c 1 ≤ c 2 ≤ ⋯ ≤ c k ≤ min 1 0 9 , ( n + 1 ) × n 2 3\leq c_1\leq c_2\leq \dots\leq c_k\leq \min{10^9,\frac{(n+1)\times n}{2}} 3≤c1≤c2≤⋯≤ck≤min109,2(n+1)×n
题解：
首先， k ≤ 20 k\leq 20 k≤20，而小写字母只有 26 个。
考虑每个前缀的回文子串的 min 和 max
- n = 1, palindrome count: min = max = 1 (a)
- n = 2, palindrome count: min = max = 2 (aa, ab)
- n = 3, palindrome count: min = max = 3 (aaa, aab, abb, abc, aba)
- n ≥ 4 n \geq 4 n≥4, palindrome count: min = 4, max = n
如何构造：
- pa[i] 表示前缀中本质不同的回文子串数
- s[1~3] = “abc”
- 如果 pa[i + 1] == pa[i]，则 s[i + 1] = ‘a/b/c’
- 如果 pa[i] => pa[i + 1] => … => pa[j]，pa[k] - pa[k - 1] == 1, k in (i, j]，对于连续的段需要一个字符，故至多 k 个不同字符即可。
证明： p a [ i + 1 ] − p a [ i ] ≤ 1 pa[i + 1] - pa[i] \leq 1 pa[i+1]−pa[i]≤1
如果 p a [ i + 1 ] − p a [ i ] > 1 pa[i + 1] - pa[i] > 1 pa[i+1]−pa[i]>1，则说明：
- 至少存在两个以 s[i + 1] 结尾的子串是回文串
- s[i + 1] 在 s[1~i] 中出现过（如果未出现过，那么 pa[i + 1] = pa[i] + 1）
假设 j < k，且 s[j ~ i + 1] 和 s[k ~ i + 1] 都是回文串，因为 s[i + 1] 出现过，所以串长一定大于 1。
考虑 pos 为所有 s[i + 1] 这个字符在 s[1~i] 的位置，共有 npos 个。
故考虑的为：s[pos[1] ~ i + 1]，s[pos[2] ~ i + 1], …, s[pos[npos] ~ i + 1] 是否为回文串且之前未出现过
这里有一个显然的想法是：如果 s[pos[x] ~ i + 1] 是回文串，则 s[pos[x] ~ pos[x + 1]] 和 s[pos[npos] ~ i + 1] 是一样的，要么都是回文串，要么都不是回文串，所以如果都是回文串的话，则这个回文串必然是在之前出现过，所以不会被计算在内，那么说明对于任意的以 s[i + 1] 结尾的回文串，至多只有一个是新的回文串。
则 p a [ i + 1 ] − p a [ i ] ≤ 1 pa[i + 1] - pa[i] \leq 1 pa[i+1]−pa[i]≤1 得证。
故上述的对于 n ≥ 4 n \geq 4 n≥4, palindrome count: min = 4, max = n，也就可以构造得出了。
代码：
参考代码
