Posted on 2012-04-18 20:26
Mato_No1 閱讀(798)
評論(0) 編輯 收藏 引用 所屬分類:
字符串匹配 、
COCI
相關鏈接今天在回顧以前的題目的時候，禿然發現COCI 2011～2012 #5的后兩題并非神犇題（至少一般人可以捉的）……是我當時想傻掉了囧……
blokovi：
首先很容易發現最優方案必然是從頂到底，先盡量往右邊放，放到某一個轉折點處再盡量往左邊放……
然后就是枚舉這個轉折點，亂算一下就行了，暴力O(N
2)的可以過7個點（本沙茶現場賽時就是用這個的）……
優化：可以從上到下依次枚舉轉折點，設目前的轉折點為i，則在下一次枚舉時（(i+1)為轉折點），把(i+1)往右平移2單位，然后根據那個重心計算公式可以得出，第(i+2)個及以后的必然是整體向右平移(2*m2)/(m1+m2)，其中m1為前i個的質量和，m2為第(i+1)個的質量……在此基礎上維護轉折點前重心位置、轉折點的重心的橫坐標（相對于最上面的那個）以及最下面的那個的重心的橫坐標（相對于最上面的那個）就行了（注意轉折點是第一個或最后一個的特殊情況要單獨處理），時間復雜度O(N)。
poplocavanje：
其實這題只要用AC自動機隨便亂搞一下就行了……Trie上的每個結點維護一個KK，表示該結點所代表的字符串的后綴的最大匹配長度（當然前提條件是該結點是危險的），則：（1）若該結點本來就代表一個待匹配的子串，則KK值為子串長度；（2）若該結點是通過失敗指針上溯到一個危險結點的，則該結點的KK就是上溯到的那個危險結點的KK。然后做一次匹配，記下所有的匹配區間，再求出未被區間覆蓋的總長度（排序+掃描即可，不需任何數據結構）就行了。
注意幾個易疵的地方：
（1）Trie的大小要開到4M才能過（不過再大就要MLE了囧……）；
（2）在建自動機計算KK的時候，如果一個結點本來就是危險的（即上述第1種結點），此過程中又發現它是上述第2種結點，則
不能重新計算KK；
（3）最后求未被區間覆蓋總長度的方法：先記下所有的區間，按照先左端點遞增序后右端點遞增序排序，當中去掉被別的區間覆蓋的區間，然后先看一下排序后的第一個區間和最后一個區間，得出第一個區間之前與最后一個區間之后的未被覆蓋的部分，中間的掃描求解時，如果某區間的左端點大于(前一區間的右端點+1)，則計入中間的空當……不過還有一種方法就是不去掉被別的覆蓋的區間，而是在掃描過程中維護右端點最大值maxr，然后把上面方法中的所有右端點改為maxr即可。
代碼：
blokovi poplocavanje