爱悠闲 > 分类 >

BZOJ 第9页

BZOJ 3207 花神的嘲讽计划I Hash+可持久化线段树/划分树
题目大意:给定一个数字串,多次求某个区间内有没有一个长度为k的子串 首先对字符串进行哈希 然后问题就转化成了求一个区间内有没有某个数 可持久化线段树即可 其实划分树会更快一些 ※注意事项: 1.n<=200000 我找不到数据范围是眼科大夫去找老阎的关系? 2.哈希值用unsigned long long 铁则 unsigned int 会被卡掉 3.线段树那里直接x+y>>1会爆unsigned
BZOJ 3123 SDOI2013 森林 可持久化线段树+倍增LCA+启发式合并
题目大意:给定一棵森林,每个点有权值,提供两种操作: 1.查询两点间路径上第k小的权值 2.将两个点之间连一条边 保证连接后仍是一座森林 可持久化线段树部分同Count On A Tree 只是这道题加了个连接操作 对于连接操作我们要用到启发式合并 就是把小的那棵树暴力重建 很简单的一个操作但是可以证明是均摊O(nlogn)的 大小我用了并查集 其实记录根就可以了 此外本题的多组数据是在逗比 记住
BZOJ 2653 middle 二分答案+可持久化线段树
题目大意:给定一个长度为n的序列,求当子序列s的左端点在[a,b],右端点在[c,d]时的最大中位数 其中当序列长度为偶数时中位数定义为中间两个数中较大的那个 很难想的一道题 具体题解见 http://blog.csdn.net/acm_cxlove/article/details/8566093 说的很详细 区间处理那里 [b,c]是必选的 [a,b)和(c,d]每段取最大加和 否则re恒>=0
BZOJ 3673 可持久化并查集 by zky 可持久化并查集
题目大意:给定n个集合,提供三种操作: 1.合并a,b所在集合 2.回到第k次操作之后的状态 3.询问a,b是否在同一集合 可持久化并查集0.0 实现方式是用可持久化线段树实现可持久化数组维护可持久化并查集。。。 至于可持久化数组,每条路径上只有叶节点的位置的num域是有意义的,感觉无比浪费0.0 可是不这样还真没法维护0.0 合并时本来应该按照每个节点的深度之和维护,结果手残懒得写,只用siz维
BZOJ 3674 可持久化并查集加强版 可持久化并查集
题目大意:同3673 强制在线 同3673 只不过慢了一些0.0 这道题只写路径压缩比只写启发式合并要快一点点 两个都写就慢的要死0.0 改代码RE的可能是内存不够 #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 200200 using namespace std; struc
BZOJ 2741 【FOTILE模拟赛】L 分块+可持久化Trie树
题目大意:给定一个序列,多次询问[l,r]中最大子序异或和 强制在线 一直RE的同学注意,本题的强制在线如果直接加会爆int导致调用数组下标为负 首先我们有一个转化 维护前缀异或和数组a[] 那么[l,r]中最大子序异或和就是a数组中[l-1,r]中任取两个数的最大异或值 然后分块处理 对于每块的第一个数a[i] 我们依次处理出对于所有的j>=i的[i,j]中的最大异或值 即s[i][j]=max
BZOJ 3166 HEOI2013 Alo 可持久化Trie树
题目大意:给定一个不重复的序列a,在a中任选一个区间,求区间内的次大值与区间内的任意一个其它数的最大的异或值 首先我们枚举次大值 对于一个次大值 它可能选择的另一个数的取值范围为(l,r) 其中l为这个数左侧第二个比它大的数 r为这个数右侧第二个比它大的数 在这个区间内的Trie树中贪心寻找最大值即可 这个区间怎么求呢?我们维护一棵平衡树 将数从大到小将下标加进平衡树 每加进一个下标 比它大的数的
BZOJ 3122 SDOI2013 随机数生成器 数论 EXBSGS
题目大意:给定一个数列X(i+1)=(a*Xi+b)%p 求最小的i>0,使Xi=t 0.0 此题能1A真是太好了 首先讨论特殊情况 若X1=t ans=1 若a=0 ans=b==t?2:-1 若a=1 X1+b*(ans-1)==t (%p) 扩展欧几里得 令 temp=b/(a-1) 则有 (X(i+1)+temp)=a*(Xi+temp) Xans=(X1+temp)*a^(ans-1)-
BZOJ 1293 SCOI2009 生日礼物 堆
题目大意:给定一个数轴上n个点,每个点有一种颜色,一共k种颜色,求一个最短的区间,包含所有k种颜色 卡了一段时间0.0 一开始想二分答案啥的 后来发现数据范围太大写不了0.0 后来去找题解才发现尼玛真巧妙 维护一个堆 将每种颜色的第一个珠子加入堆 然后不断把最左侧的珠子取出,加入该种颜色的下一个 同时更新ans 果然这么大数据范围还是要用堆这种常数小的数据结构啊0.0 我手写了堆却开了STL的qu
BZOJ 2002 HNOI2010 弹飞绵羊 分块
题目大意及LCT版本题解:见 http://blog.csdn.net/popoqqq/article/details/38849471 今天手滑用分块又重写了一遍这道题0.0 分块就是短啊 将弹簧分为√n块 对于每个弹簧 我们记录一下从这个弹簧出发直到弹到块外为止的弹跳次数及落点 查询沿着落点弹到出去为止 修改从块开始到这个点为止修改一遍 这样修改和查询都是O(√n)的 #include<cma