BestCoder#37
ZJOI2015DAY2

CF除草记

SkyDec posted @ 2015年4月15日 18:35 in 杂乱无章 , 863 阅读

再不刷题就要从TG水平掉回PJ水平了

upd 4.23:做不动了,弃坑弃坑

before 4.15

【477D】Dreamoon and Binary:直接n^2 DP。。中途判断可以用SA搞

【480D】Parcels:对于每个点,用背包跑一遍,于是复杂度就是n^2*S

【480E】Parking Lot:考虑倒过来做,本来删点变成了加点,维护每个格子的right:最多往右多长,每次加点只影响n个点,然后暴力判一下每个点是否可以在新答案的左边界就好了,判断时相当于询问该点向上最多连续有几个点right大于等于新答案,是经典的线段树问题。复杂度O(nklogn)

【482C】Game with Strings:考虑一个位置集S,我们算出哪些字符串当判断到S时还不能唯一确认,这个可以m*2^m预处理。然后枚举第一次确认答案时的位置集S,再枚举最后一次选的位置c(c [tex]\in[/tex] S)。那么能将S作为答案的字符串肯定满足:位置集S可以唯一确认,而S-c不能唯一确认,位运算搞出来就好了

【482D】Random Function and Tree:考虑对于1个点,我们DP出他的子树中偶数个点被染和奇数个点被染的方案数,怎么DP呢?先背包一遍,这样对于一种方案有两种方式:从第一个儿子开始,从最后一个儿子开始。这样或许会影响每个儿子的颜色,于是答案*2。但是这样会有重复,于是要减去那些无论正着来还是倒着来颜色都相同的方法,如果染的点为偶数个:则每个儿子都是染偶数个点。否则每个儿子都是染奇数个点。于是直接背包就好了。。


upd:4.15

【482E】ELCA:对于一个点x,以他为LCA的点对数为size[x]^2-sigma(size[son[x]]^2),于是维护下size,虚儿子size和,虚儿子size^2和之类的,用动态树维护就好了

【484D】Kindergarten:写了个线段树水过去了。。标算好像是O(n)的,基本思想就是对于最终方案,每一段的极值肯定在两侧,否则可以再分,于是就可以直接搞了

【484E】Sign on Fence:二分+可持久化线段树


 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter