Mato is No.1

相關(guān)鏈接
今天在回顧以前的題目的時候，禿然發(fā)現(xiàn)COCI 2011～2012 #5的后兩題并非神犇題（至少一般人可以捉的）……是我當(dāng)時想傻掉了囧……

blokovi：
首先很容易發(fā)現(xiàn)最優(yōu)方案必然是從頂?shù)降祝缺M量往右邊放，放到某一個轉(zhuǎn)折點處再盡量往左邊放……
然后就是枚舉這個轉(zhuǎn)折點，亂算一下就行了，暴力O(N²)的可以過7個點（本沙茶現(xiàn)場賽時就是用這個的）……
優(yōu)化：可以從上到下依次枚舉轉(zhuǎn)折點，設(shè)目前的轉(zhuǎn)折點為i，則在下一次枚舉時（(i+1)為轉(zhuǎn)折點），把(i+1)往右平移2單位，然后根據(jù)那個重心計算公式可以得出，第(i+2)個及以后的必然是整體向右平移(2*m2)/(m1+m2)，其中m1為前i個的質(zhì)量和，m2為第(i+1)個的質(zhì)量……在此基礎(chǔ)上維護(hù)轉(zhuǎn)折點前重心位置、轉(zhuǎn)折點的重心的橫坐標(biāo)（相對于最上面的那個）以及最下面的那個的重心的橫坐標(biāo)（相對于最上面的那個）就行了（注意轉(zhuǎn)折點是第一個或最后一個的特殊情況要單獨處理），時間復(fù)雜度O(N)。

poplocavanje：
其實這題只要用AC自動機隨便亂搞一下就行了……Trie上的每個結(jié)點維護(hù)一個KK，表示該結(jié)點所代表的字符串的后綴的最大匹配長度（當(dāng)然前提條件是該結(jié)點是危險的），則：（1）若該結(jié)點本來就代表一個待匹配的子串，則KK值為子串長度；（2）若該結(jié)點是通過失敗指針上溯到一個危險結(jié)點的，則該結(jié)點的KK就是上溯到的那個危險結(jié)點的KK。然后做一次匹配，記下所有的匹配區(qū)間，再求出未被區(qū)間覆蓋的總長度（排序+掃描即可，不需任何數(shù)據(jù)結(jié)構(gòu)）就行了。

注意幾個易疵的地方：
（1）Trie的大小要開到4M才能過（不過再大就要MLE了囧……）；
（2）在建自動機計算KK的時候，如果一個結(jié)點本來就是危險的（即上述第1種結(jié)點），此過程中又發(fā)現(xiàn)它是上述第2種結(jié)點，則不能重新計算KK；
（3）最后求未被區(qū)間覆蓋總長度的方法：先記下所有的區(qū)間，按照先左端點遞增序后右端點遞增序排序，當(dāng)中去掉被別的區(qū)間覆蓋的區(qū)間，然后先看一下排序后的第一個區(qū)間和最后一個區(qū)間，得出第一個區(qū)間之前與最后一個區(qū)間之后的未被覆蓋的部分，中間的掃描求解時，如果某區(qū)間的左端點大于(前一區(qū)間的右端點+1)，則計入中間的空當(dāng)……不過還有一種方法就是不去掉被別的覆蓋的區(qū)間，而是在掃描過程中維護(hù)右端點最大值maxr，然后把上面方法中的所有右端點改為maxr即可。

代碼：
blokovi poplocavanje