CF 100965C

http://www.cnblogs.com/tmzbot/p/5801251.html 其实感觉是个很正常的思路..我还要在套路上学习一个啊..

CF 100451I

给定一个递增数列,求这个数列是否存在某个排列是模n(给定)意义下的等差数列并输出通项.

我们考虑我们要找什么.要是我们能找到这个数列的公差那么我们这个问题就做完了.

我们考虑在数列中随机一个点(c),然后去掉这个数列中已这个点为中心对称的最长一段.这个其实很好做:如果数列中存在(x,y, c-xequiv y-c pmod{n}),那么我们就去掉这两个数. 我们来证明这个是对的: 显然可以除去所有的,然后对于一个数(x),如果(c-(x-c)mod n)不在数列中它肯定不会被除去. 那么我们就这样一步步(递归的)除掉这个序列, 让它每次除掉后结果数列的长度小于等于原长度*(一个设定的比例alpha), 那么就最多递归log层了. 复杂度是O(T(n)), T(n)是除一次的时间.如果ran一定次数都没法除成alpha我们就可以直接断言它不是等差数列了.

这样我们最后在数列长度很小的时候暴力求出那个长度, 最后对于原数列的每个数找一下它的prev就好了.

CF 100451H

维护一个对一个初始为空的双端队列(deque)的操作序列,初始时其中有1e9个空操作.在线,给出动作:

[L] [op] [args] #[保证行L是一个空操作] 在行L插入操作op args, 格式后面详述
[L] - #[保证行L非一个空操作] 删除行L内的操作.
[L] ? [time] #查询从操作1运行到操作time最后双端队列front和back的值

[op] [args] 是一个deque操作,操作名为[op],有参数[args].具体的,

push_front [value]
pop_front
push_back [value]
pop_back

(保证每一个操作都是合法的)

对于每个动作,

如果为[L] [op]或[L] -,输出0 0(为了在线)
如果为[L] ?,输出[front] [back]

输出完记得fflush才能继续读入.

这道题目的思路其实非常经典,我们可以维护一个对操作序列的线段树,其中每一个节点维护这个deque两端的信息(加上哪些或者删去多少),这个信息可以用可持久的treap方便的维护(一点也不).(O(n log^2 n)).这个做法十分杭二机房(大雾),类似的题目见bzoj NOI十连鏼.

然而这个做法实在是太暴力(而且很难写)了.我们考虑,因为题目保证了数据的合法性,即当pop的时候deque一定非空,那我们就无需判断两个端点之间的关系了(反正都是合法的),那么我们就可以两个端点位置分开维护.

考虑左端点的做法,右端点同理

我们首先可以求出运行1-time最后的左端点, 这个很简单只需要区间和.

然后我们要求出这个位置最后的值,即:我们要找到最晚的在time+1之前的push操作使得这个操作加入的位置是给定端点处(无论是push_front或push_back).

这个有点难做的,不妨让我们想一想这个端点位置随时间变化的规律.显然相邻两个相差1((alpha)),但是靠近的两个push操作位置不一定相差1((eta)),但是如果不相差1的话一定是减少的((gamma)).

(alpha)启示了我们可以用二分(线段树上记相对位置min,max), 然而(eta)说不能直接二分(可能会炸), 然后看到(gamma)我们就需要分析一下.

首先我们想办法让查找不会递归到pop里去.这个简单, 设pop的min为intmax,max为intmin即可.(解决(alpha))

然后我们通过(gamma)的性质说明(alpha)的二分对(eta)的情况不会炸.

我们设查找的相对位置是L,递归到这样的一段: max>L, min<L 且不存在合法的push, 那么在这前面为了构造max和min的差,在上一段范围包括这个L(min<L, max>L)但是不存在L的下降序列之前必然有一段上升序列的序列,其中穿插的下降序列都不范围包括L(反证法),然后其中的一个上升序列包括L(从一个<L +1变化到 >L). 那么复杂度最多就是查找两次的复杂度(只会失败一次).

那么就做完了.(O(nlog n))

bzoj3068

想了好几天的一道题..Claris说的不是很明白然后他的代码又极其丑陋,= =..

其实有很多好想(难写)的做法..当然我都枪毙掉了..(比如什么区间加对数组逐个取max值的max还有什么线段树合并之类的..)最终其实还是要观察性质啊..

首先设根.然后我们考虑如何求出每棵子树的重心(带权)..

其实很简单啦..重心P一定具有性质,就是与P相连的每个联通块的权值和都小于等于总权值和的1/2.这个是经典的调整法证明..那么我们在一个节点Q上加一棵子树会让重心向P的方向移动.我们如何维护这个重心呢..?其实很简单啦..就是这棵树的重心一定在根节点或根节点的权值和最大子树中.(反证法,如果不在最重的中说明最重的子树<=1/2,那显然就是在根节点了),那么我们就可以让这个重心先继承最重子树的,然后再往上调整.复杂度的话..可以考虑移动过的节点都不会再被移动到了所以复杂度是对的..

现在的问题就是去掉一棵子树tr后的重心.这个问题还是有点点难的..一个比较自然的想法就是维护对每个节点p,维护max(wtot-wtr-wp,max(w(son(p)))),(...真的能维护么..看起来是可以的..)

然而其实并不用啊..我们先二分第一个w_anc>=1/2(wtot-wtr),那么重心要么是这个点要么在这个点除了n包含tr的子树外最大的子树里..而且一定是一个最小的wp>=1/2(wtot-wtr)..然后我们发现dfs序里dfn[儿子]>dfn[父亲]..然后似乎就直接线段树找一找就好了..