agc037_e Reversing and Concatenating
https://atcoder.jp/contests/agc037/tasks/agc037_e
https://img.atcoder.jp/agc037/editorial.pdf
Tutorial
设 (a) 为第一次 (U) 中字典序最小的字符, 设 (L) 为它在 (U) 中最长的连续段长度, 那么最后串的开头就会有 (min { 2^{K - 1} L, N }) 个 (a) .
当 (2^{K - 1}L ge N) 时, 答案就是 (N) 个 (a)
否则, 考虑过程中
- 在第 (i) 步 ((i < K)) , (2^{i - 1}L) 个 (a) 必须在串的末尾.
- 在第 (K) 步, (2^{K - 1}L) 个 (a) 必须在串的开头.
第一步的选择有 (O(n)) 种, 而第一步选择确定后最终的串就确定了.
复杂度 (O(n^2))