BZOJ NOI十连测 5thTest
YYY
posted @ 2016年6月21日 17:13
in 算法竞赛
with tags
贪心 FFT 点分治 乱搞 暴力 括号序列 KMP 可持久化线段树 可持久化数据结构
, 1045 阅读
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
-----------------------------------------------------------
为什么从第五次才开始写总结呢?..
因为之前忘了OvO
-----------------------------------------------------------
T1:
题意是给你n个2^16-1以内的正整数,对于所有i输出i前面和他做opt运算后能得到的最大值和这样的数的个数,n<=10^5,opt是bit_and,bit_or,xor中的一种
考场上只做出来了这道题QAQ(结果还把type=0的情况判错了少了20分...)
xor很简单,字典树搞一搞就行了
所以只考虑and和or的情况(其实是一样的...)
众所周知一个二进制数可以看成是一个集合的子集
设f[i][j]表示高8位是i的超集,低8位恰好为j的数的个数
只需要每次询问一下,再添加这个数,维护一下f就行了
添加的时候只需要枚举一下高8位的子集
询问的时候高位贪心,低位暴力
时间复杂度O(n*(2^8))
-----------------------------------------------------------
T2:
不会kmpQAQ
听同学解释了一下题解..
大概是说,不难证明假设从最后一个点开始跳next,一直跳一直跳,最后停下来的位置和长度之差就是答案
然后假设f[i]表示如果添加了一个字符i,一直跳一直跳最后停下来的位置
然后加入一个字符之后f只会改变一个位置
然后用一个可持久化线段树维护一下就好了...
-----------------------------------------------------------
T3:
题意是给你一棵树,每个结点有一个字符(要么是前括号要么是后括号),设r[i]表示点对(a,b)满足:a到b的路径上的括号连起来得到的括号序列可以划分成的最多的合法括号序列恰为i,这样的有序二元组的个数,求r,树的大小<=50000
把前括号视为1,后括号视为-1
一个(不一定合法的)括号序列可以用两个参数(t,w)来表示:t表示当前值,w表示最多可以划分的段数(前缀中t为0的个数)),当然如果一旦有一个前缀的t<0,那么这个括号序列就再也不可能合法了,需要特殊记一下
好,现在树分治
只需要考虑怎么合并两条链
可以对t一样的一起做
然后t显然要和某个-t合在一起(这个-t显然是不合法的,但是是反过来的,所以实际上是+t)
然后他们的代价是w1+w2
这显然就是个卷积
FFT即可
分析时间复杂度,一个t假设他最大的w是w,那么就会消耗掉w个结点,然后多项式的项数不会超过w
所以每一层的复杂度是O(nlog)的
所以总的复杂度是O(n*log*log)
(感觉这算法挺傻的啊...为什么考试的时候没有想出来呢...果然还是自己太菜了...)
-----------------------------------------------------------
评论 (0)
