6
19
2016
0

【NOI模拟赛#4 T2】Zbox loves stack

题意:

有n个栈,要求支持如下操作:
*.把第l个栈到第r个栈都压入一个元素x
*.把第l个栈到第r个栈都弹出栈顶(若栈为空则无视)
*.询问第s个栈的第k个元素是多少(栈顶为第一个元素)

神(he)奇(he)的数据范围= =:(时限4s)

对于10%的数据,n<=5000,q<=5000
对于30%的数据,n<=100000,q<=30000
对于另外10%的数据,保证没有t=1的操作
对于另外10%的数据,所有t=0的操作满足l=r
对于另外10%的数据,所有t=1的操作满足l=r
对于另外10%的数据,所有t=2的操作满足k=1
对于另外10%的数据,保证不会输出"Error"
对于100%的数据,n<=1000000,q<=100000,所有输入的数在[0,2^31-1]之间

Category: 树套树 | Tags:
6
18
2016
0

【NOI模拟赛#3 T2】【主席树套线段树】【倍增】线段树Segment

题意:

Tag:

线段树维护区间并

可持久化线段树计算“前一个覆盖到这个端点的操作”

预处理倍增数组快速完成遍历

6
18
2016
0

【NOI模拟赛#3 T1】【期望计算】哈夫曼树Huffman

题意:

给出n个数,每次随机选择数组中两个不同位置的数

6
17
2016
0

【NOI模拟赛】【后缀平衡树】幻想Fantasy

题意:

一个字符串,尾部插入或删除字符,询问一个区间出现给定字符串的次数。

对于100%的数据Max<=200000,q<=500000,Len<=5000000

6
17
2016
0

【省队集训】【FFT】【常数优化】圆

题意:

给出一个01矩阵,求最大的圆,使其内部0的个数不超过K。

Category: FFT | Tags: 卷积 乱搞 技巧
6
17
2016
0

【新姿势】再谈快速傅里叶变换(FFT)

之前学过但一直没有用它来写过题(太弱),这次再来复习一下~

快速傅里叶变换能够快速计算卷积。

离散傅里叶变换(DFT)可以求循环卷积,N,M为两类的个数,当循环卷积长度L>=N+M-1,就可以做线性卷积了。

快速傅里叶变换就是加速这一过程的。

Category: FFT | Tags: 学习笔记 卷积
6
16
2016
0

【bzoj1783】【Usaco2010 Jan】【博弈】Taking Turns

题意:

一排数,两个人轮流取数,保证取的位置递增,每个人要使自己取的数的和尽量大,求两个人都在最优策略下取的和各是多少。

Category: 树套树 | Tags:

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com