NOIP集训-11.3总结

绍一的题..居然考了两道数据结构..
----------------------------------------------------------------------
 
狮子: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,那么答案就累加这两个点的距离,否则不累加
----------------------------------------------------------------------