倍增的英语怎么说。
Tasks below are finished yesterday in Yuhui Che's room(When he was watching ugly girls.). I'll write the solution in this blog because the coding work was accomplished just now.
CF461E
No Binary Search.
If letters in \(\{A,B,C,D\}\) do not appear in the given string \(t\),they can't appear in the target string \(s\).
To minimize the operation number,one could just find the longest prefix of \(s\) appeared in \(t\) and delete it in \(s\). Repeat such process until the \(s\) is empty.
If we want this extending process to stop, DFS on a trie is all you need. Set \(dp_{s,f}\) be the least length of a string that does not appear in \(t\) and begins with character \(s\) and ends with character \(t\).
It's obvious that by choosing proper characters,we can force the length of the longest prefix mentioned above is always smaller than \(\log_4{|t|}+1\). So do not let the substrings of \(t\) with a length longer than that appears in your trie.