倍增的英语怎么说。

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 \(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\). Pay attention that string \([s\dots f]\) doesn't appear in \(t\). We want the character \(f\) to force the substring extention process to stop.

By using 倍增 with something similar to matrix mutiplication，we can easily obtain \(\rm DP_{i,s,f}\) which means the least length of a row of \(2^i\) strings.Greedily append the strings.

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 the upperbound appears in your trie.

Encounter and Farewell

link

How do you confirm that there is a Spanning tree in the graph? For me that is all you can reach any vertex in the graph from any starting point..