Posted on 2012-04-18 20:26
Mato_No1 阅读(768)
评论(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