爱悠闲 > 分类 >

BZOJ 第16页

BZOJ 3289 Mato的文件管理 莫队算法+树状数组
题目大意:给定一个序列,多次询问区间内逆序对的数量 总算是明白城市旅行是如何RE的了……尼玛BZOJ坑爹 ostream输出流过大居然会RE!输出时顺手用了cout结果各种RE不止……原来是这样 建议各位在死活RE就是找不到原因的时候检查一下是否大输出用了cout 这题用莫队可以很简单搞掉 逆序对用树状数组就可以维护 一会去想想强制在线怎么搞 #include <cmath> #include <
BZOJ 3744 Gty的妹子序列 分块+树状数组+可持久化线段树
题目大意:给定一个序列,多次求区间内逆序对个数 强制在线 让我们呐喊一声:出题人卡常数丧心病狂! 再来一次:出题人卡常数丧心病狂!!!! 不强制在线的直接莫队就能搞 强制在线我是跪了QTZ 首先看这数据范围肯定O(n√nlogn)了  我们分块 令cnt[i][j]为从第i块的开头起到第j个点这段区间的逆序对数 这个用树状数组就可以O(n√nlogn)搞出来 我一开始直接用可持久化线段树搞这部分
BZOJ 1806 IOI2007 Miners 矿工配餐 动态规划
题目大意:将一个123序列拆分为两个子序列,定义每个数的贡献值为以这个数结尾的长度最大为3的子串中不同数的数量,求贡献值和的最大值 令f[i][a1][a2][b1][b2]为前i个数分成两组,第一组以a1 a2结尾,第二组以b1 b2结尾的最大贡献值 转移啥的自己YY吧 记得开滚动数组 尼玛写错个参数都要调半天…… #include<cstdio> #include<cstring> #incl
BZOJ 3065 带插入区间K小值 替罪羊树套线段树
题目大意:带插入、修改的区间k小值 我也作死去学了下替罪羊树(OTZ HZWER)……之前在想平衡树套不了线段树看到这题直接秒收弗拉格啊 普通的平衡树由于有旋转操作 所以如果每旋转一次都重建一次平衡树妥妥TLE 但是替罪羊树就没什么问题 因为替罪羊树没有旋转 如果一个节点的某个儿子的size超过了本身size的55%~80% 就暴力重建这棵子树 这个节点就被称作替罪羊节点 个人对“替罪羊”的理解就
BZOJ 1968 AHOI2005 COMMON 约数研究 线性筛
题目大意:求n以内所有数的约数个数和 100W,n√n别想了 线性筛可以处理,对于每个数记录最小质因数的次数 令factoral[i]为i的因数个数 cnt[i]为i的最小质因数的次数 若i为质数 则factoral[i]=2 cnt[i]=1 若i%prime[j]!=0 则factoral[prime[j]*i]=factorial[i]*2 cnt[prime[j]*i]=1 若i%prim
BZOJ 1251 序列终结者 Splay
题目大意:维护一种数据结构,支持下列操作: 1.将一个区间加上一个数 2.将一个区间翻转 3.询问一段区间的最大值 Splay裸题 OTZ题干…… #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 50500 using namespace std; struct abcd
BZOJ 3438 小M的作物 最大权闭合图
题目大意:给定一些元素,需要放在两个集合里,每个元素放在集合A里的贡献为a[i],放在集合B里的贡献为b[i] 其中还有一些子集 若一个子集的所有元素都在A集合里会获得贡献值c1[i],都放在B集合里会获得贡献值c2[i] 首先我们先把所有的元素都放在集合A中 获得所有的a[i]和c1[i] 然后考虑最大权闭合子图 一个点如果不选就放在A集合中 选就放在B集合中 一个点如果选 那么就要扣除相应的a
BZOJ 3439 Kpm的MC密码 Trie树+可持久化线段树
题目大意:给定n个字符串,对于每个字符串求以这个字符串为后缀的字符串中第k小的编号 首先将字符串反转 那么就变成了对于每个字符串求以这个字符串为前缀的字符串中第k小的编号 然后考虑对字符串排序 那么对于每个字符串以它为前缀的字符串一定是连续的 那么就转化成了区间第k小 这个用可持久化线段树可以解决 排序自然不能直接排 既然是字符串 考虑Trie树+DFS即可 注意字符串有重复的 小心 #inclu
BZOJ 2431 HAOI2009 逆序对数列 递推
题目大意:求1~n的所有排列中有多少种逆序对为k的方案数 令f[i][j]为前i个数的排列中逆序对数为j的方案数 那么我们将第i个数插入1~i-1的排列中 可以产生0~i-1个逆序对 于是有 f[i][j]=Σf[i-1][k] (j-i+1<=k<=j) 维护前缀和即可 #include<cstdio> #include<cstring> #include<iostream> #include<
BZOJ 3747 POI2015 Kinoman 线段树
题目大意:有m个点,每个点有个权值,现在有这m个点组成的长度为n的序列,求一个区间,这个区间内只出现一次的点的权值和最大 想了半天的一道题居然被神犇说成是水题……我也是醉了 枚举左端点 对于每个左端点求右端点 这个用线段树维护最大值 考虑每个数对答案的贡献 记录一个数组next表示这个位置上的点下一次出现的位置 那么这个点贡献的作用范围就是[i,next[i]-1] 如果没有next就是[i,n]