爱悠闲 > 分类 >

BZOJ 第10页

BZOJ 2821 作诗(Poetize) 分块
题目大意:给定一个序列 多次求区间中多少个数出现次数为偶数次 强制在线 很神的一道分块的题……记得刚进BZ坑的时候看到这道题50秒特别惊奇0.0 然后我就作死去交了个死循环0.0 看了很多题解 都没看懂 最后还是把零碎的思想硬拼到一起才写完0.0 我们首先分块 然后预处理一些东西 首先是从第i块到第j块的答案 这个我们从第i块第一个点开始向右扫 开一个数组记录每个数的出现次数 扫到一个数就更改一下
BZOJ 2141 排队 分块+树状数组
题目大意:给定一个序列,m次交换两个数,求初始逆序对数及每次交换后的逆序对数 首先离散化,分块,对于每块建立一个树状数组,保存这个块中的所有元素 然后对于每个询问(x,y) (x<y) 两侧的数是没有影响的,区间(x,y)的数a[i]讨论如下: a[i]<a[x] --ans a[i]>a[x] ++ans a[i]<a[y] ++ans a[i]>a[y] --ans 然后对于块中的树状数组处理
BZOJ 3343 教主的魔法 分块
题目大意:给定一个序列,提供两种操作: 1.区间加上一个数 2.询问区间中有多少大于等于C的数 n<=100W,树套树不用想了,Q<=3000,分块走起~ 将原数组复制一份副本,副本中每一块排序 对于每次修改,中间块的部分打标记,两边修改后重建 对于每次查询,中间块的部分二分答案,两边暴力枚举 别忘考虑标记 #include<cmath> #include<cstdio> #include<cst
BZOJ 1042 HAOI2008 背包+容斥原理
题目大意:给定4种硬币的面值,多次询问这个限定这四种硬币的个数时达到某一价值的方案数 十分巧妙的一个题……蒟蒻表示打死也想不到容斥原理0.0 首先先求出不限定硬币的方案数 然后利用容斥原理 ans=不限定硬币的方案数-(硬币1超出的方案数+硬币2超出的方案数+硬币3超出的方案数+硬币4超出的方案数)+(硬币1和硬币2都超出的方案数+……)-(硬币123都超出的方案数+……)+四种硬币都超出的方案数
BZOJ 1085 SCOI2005 骑士精神 IDA*
题目大意:给定一个棋盘,每个棋子都是骑士,问能否在15步之内移动为特定排布 此题采用IDA* 估价函数为:当前棋盘与目标棋盘不同的位置数量-1 易知一个棋盘最少需要这么多的步数才能达成目标棋盘 若当前步数+估价函数大于最大深度 则剪枝 优先搜索懒得写0.0 这样就能切掉就行 #include<cstdio> #include<cstring> #include<iostream> #include
BZOJ 3333 排队计划 树状数组+线段树
题目大意:给定一个序列,每次选择一个位置,把这个位置之后所有小于等于这个数的数抽出来,排序,再插回去,求每次操作后的逆序对数 首先我们每一次操作 对于这个位置前面的数 由于排序的数与前面的数位置关系不变 所以这些数的逆序对不会变化 对于这个位置后面比这个数大的数 由于改变位置的数都比这些数小 所以这些数的逆序对不会变化 说到底就是排序的数的逆序对数改变了 以这些数开始的逆序对没有了 于是就好办了
BZOJ 3589 动态树 树链剖分+容斥原理
题目大意:给定一棵以1为根的有根树,每个节点有点权,提供两种操作: 1.以某个节点为根的子树所有节点权值+x 2.求一些链的并集的点权和,其中这些链都是由某个节点出发指向根 首先子树修改,链上查询,树链剖分的WT~ 然后这些链上的每个点的点权都只能被加一次,肯定不能打标记,由于k<=5,我们考虑容斥原理 总权值=单链-两两之交+三链之交…… 状压枚举即可 两条链的交集求法如下: 1.求两条链底的L
BZOJ 2242 SDOI2011 计算器 快速幂+扩展欧几里得+BSGS
题目大意:……简洁明了自己看 第一问快速幂 第二问扩展欧几里得 第三问BSGS 顺便一开始没看到p是质数0.0 去弄了EXBSGS的模板0.0 懒得改了 #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 1001001 using namespace
BZOJ 2733 HNOI2012 永无乡 Treap+启发式合并
题目大意:给定一个无向图以及n个点的排名,多次连接一条边,多次求某个点所在联通块中排名第k小的点的编号 初始对于每个点建立一棵只有一个节点的Treap,然后每次连接两个点,利用并查集找到两个点的根节点,将size较小的Treap暴力拆解插入大的中,然后将小的并查集合并到大的中 今天下午各种脑残,一个小小的Treap改了不下10遍0.0 快去喝脑白金0.0 #include<cstdio> #inc
BZOJ 2809 APIO2012 dispatching Treap+启发式合并 / 可并堆
题目大意:给定一棵树,选定一棵子树中的一些点,薪水和不能超过m,求点的数量*子树根节点的领导能力的最大值 考虑对于每个节点,我们维护一种数据结构,在其中贪心寻找薪金小的雇佣。 每个节点暴力重建一定不行,我们考虑可并数据结构,每个节点将子节点的信息直接合并即可 可以用启发式合并的Treap,也可以用可并堆 今天特意去学了这玩应0.0 先写了左偏树 然后又写了下随机堆…… 后者速度上更快一些 不过建议