今天帥哥總召要出任務,以下是他詢問大家對字串的看法:
小 A 說:在我看來學會 AC 自動機就夠了,名字有 AC 到處都 AC!
小 S 說:真的嗎?聽說 Suffix array 可以解決
小 O 說:不會啊,字串很簡單啊。 KMP 就是在討論前綴跟前綴的後綴的關係、 Z value 就是在討論前綴跟後綴的前綴的關係、Manacher's algorithm 就是在討論子字串的子字串跟回文的關係!
小 W 說:有道理,所以題目裡出現兩次前綴和一次後綴就用 KMP ,出現回文就用 Manacher's algorithm!
小 M 說:在我看來大家都忽略了一個最強的算法,不管甚麼題目用 Trie 直接 Trie Trie 看就會過了!
小 T 說:也不用那麼麻煩,看到題目直接迴圈掃過去就可以了,反正輸入的字串長度都是有限大,通通都是常數!
小 C 說:現在的題目怎麼都那麼難懂,要是直接告訴我要怎麼做就好了!
帥哥總召要回答的任務如下:
現在一共有
一個二元組
接著給出一個長度限制
測試資料第一行包含兩個正整數
接下來一共有
請一共輸出
IOICamp 2021 Day4 pF
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0 | 範例測資 | 0 |
2 | 0~32 | 無額外限制 | 100 |