COCI 2011~2012 #5 后两题题解

Posted on 2012-04-18 20:26 Mato_No1 阅读(756) 评论(0)  编辑 收藏 引用 所属分类: 字符串匹配COCI
相关链接
今天在回顾以前的题目的时候,秃然发现COCI 2011~2012 #5的后两题并非神犇题(至少一般人可以捉的)……是我当时想傻掉了囧……

blokovi:
首先很容易发现最优方案必然是从顶到底,先尽量往右边放,放到某一个转折点处再尽量往左边放……
然后就是枚举这个转折点,乱算一下就行了,暴力O(N2)的可以过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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理