摸了，前兩天實(shí)在太多事情，今天把周末沒做出來的題補(bǔ)一下。

D. Fixed Prefix Permutations

現(xiàn)在有 n 個(gè)從 1 - m 的排列，稱為?, 現(xiàn)在定義一個(gè)排列的 beauty 為，這個(gè)排列的最長連續(xù)上升前綴，也就是，如果滿足前 k 個(gè)元素為 1 到 k，但是第 k + 1 個(gè)元素不是 k + 1，那么這個(gè)排列的 beauty 為 k?，F(xiàn)在定義兩個(gè)排列的乘積運(yùn)算，, 得到的排列滿足這樣的性質(zhì)：, 現(xiàn)在給定 n 個(gè)排列，要求，對于每一個(gè)排列?, 求它與輸入中任意排列?, （i 和 j 可以相等）的乘積的最大 beauty 是多少。

思路：

首先需要清除，如果兩個(gè)排列 p, q 的乘積的 beauty? 意味著什么：. 也就是數(shù)字 j 在排列 q 中的?位置。假設(shè)現(xiàn)在給定了乘積中左邊的排列?, 那么求最大的 beauty 的一個(gè)顯然的方式是暴力地遍歷每個(gè)排列?, 對于每個(gè)排列，依次檢查? 中的第??個(gè)元素是不是 k, 從 1 開始找到最大的 k. 遍歷完所有排列后就找到一個(gè)答案。對于一個(gè)排列，這樣做的時(shí)間復(fù)雜度是?，對于 n 個(gè)排列，則是?, 對于? 這樣的數(shù)據(jù)量是不行的。

考慮暴力的做法有什么冗余的地方：假設(shè)當(dāng)前的乘積左排列為 p，乘積右排列為 q，我們需要先檢查，1 是不是在 q 的第?個(gè)位置，然后需要檢查 2 是不是在 q 的第?個(gè)位置，以此類推。但是如果有兩個(gè)排列?, 滿足：k 在??中的位置相同，對于從 1 到 ?的所有自然數(shù) k。那么實(shí)際上對于這兩個(gè)排列的檢查是可以同時(shí)完成的，這有點(diǎn)類似某種意義上的公共前綴。

形象一點(diǎn)來說，如果把每個(gè)排列都映射成一個(gè)字符串 str，str 的第 i 個(gè)字符表示，i 在排列中出現(xiàn)的位置的下標(biāo) （都從 1 ）開始，那么對于滿足上面所說的性質(zhì)的?, 它們映射之后的字符串有公共前綴。而求某個(gè)排列和其他排列乘積的最大 beauty，可以轉(zhuǎn)化為：乘積左排列直接組成的字符串和乘積右排列經(jīng)過上述規(guī)則映射之后得到的字符串的最大公共前綴。

這可以通過 Trie 樹來做，存儲(chǔ) n 個(gè)排列的時(shí)間復(fù)雜度和查詢 n 個(gè)排列的時(shí)間復(fù)雜度都是?, 對于 m 是 10，n 是 50000 這樣的規(guī)模是可以接受的。