NOIP集训-11.3总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
绍一的题..居然考了两道数据结构..
----------------------------------------------------------------------
狮子:SuperOjP994
发现如果所有狮子都不住口，那么狮子死亡的序列是一定的，显然最后的答案是这个序列的某个前缀
首先时间卡在最后一个死掉狮子的后面，然后从后向前推
如果一个狮子被另一个吃了，且吃它的狮子在时间以内（也就是会死掉）那么这个狮子只要不吃它就不用死，因此这个狮子一定不会吃它，于是可以把时间卡到它前面
这样不断地向前推，最后时间会停留在某个位置，排序输出时间之前的所有狮子就行了
----------------------------------------------------------------------
国际象棋:SuperOjP995
40%可以状压DP
100%不会...
----------------------------------------------------------------------
高地:SuperOjP996
写了个nlog^2的算法，卡一卡常数过掉了：
给每个点一个升降值，如果一个点比它左边的点高，那么他的升降值是1，如果它比它左边的点低，那么他的升降值是-1，否则是0
显然一个高地是升降值为这样的一个序列:1 0 0 0 .. 0 0 -1
所以，答案就是相邻的两个(1,-1)对（跳过中间的零）的长度累加
可以用一个线段树来维护这样的信息
每一次修改只会导致修改的两个端点的升降值改变，因此是单点修改
每个节点储存这个区间内的答案
现在考虑如何合并两个区间：
显然只需要求出跨过了这个区间的答案（也就是跨过了mid）
只需要左边离mid最近的一个非0点，右边离mid+1最近的一个非0点,如果左边是1，右边是-1，那么答案就累加这两个点的距离，否则不累加
----------------------------------------------------------------------
评论 (0)
