爱悠闲 > 分类 >

BZOJ 第3页

BZOJ 1269 文本编辑器 Splay
题目大意:维护一个文本编辑器,支持下列操作: 1.将光标移动到某一位置 2.在光标后插入一段字符串 3.删除光标后的一段字符 4.翻转光标后的一段字符 5.输出光标后的一个字符 6.光标-- 7.光标++ Splay中比较水的一道题,标记只有区间翻转,也不用维护区间总值,唯独需要注意的就是插入的时候fa要记得赋值,不然就会像本蒟蒻一样调半天,,, 这题要注意的是Insert操作的读入 首先读入第一
BZOJ 1507 NOI2003 Editor Splay
题目大意: 1.将光标移动到某一位置 2.在光标后插入一段字符串 3.删除光标后的一段字符 4.输出光标后的一段字符 5.光标-- 6.光标++ 和1269很像的一道题,不过弱多了 几个问题需要注意: 1.插入的字符串中间居然会有回车!!没办法了,只能逐个字符进行读入,一旦读到'\n'或者'\r'就重新读入 2.题目描述中说Delete和Get操作后面一定会有足够的字符 纯属放P 连样例都没有足够
BZOJ 3110 ZJOI2013 K大数查询 树套树
题目大意: 有n个位置,m个操作,提供下列两种操作: 1.在[x,y]区间内每个位置插入一个z 2.查询[x,y]区间内的第k大 注意是第k大不是第k小 来一段《树套树之歌》吧: 树套树 树套树 树套树套树 树套树树套树套树 树套树套树套树套树 树套树树套树套树 树套树套树套树套树套树 BGM:《邮递马车》 树套树摆在这里 关键是怎么套 我一开始想的是权值线段树在内层 结果外层的话树状数区间修改+
BZOJ 2120 数颜色 暴力
题目大意:给定一个序列,提供两种操作: 1.查询[l,r]区间内有多少不同的数字 2.单点修改 n,m<=1W 树套树?主席树?啥都不需要!这题暴力才2s,不要想复杂了!妥妥水过! 数字离散化一下!标记用时间戳代替!675B秒切!不是一般爽! 。。。好吧如果觉得这样没啥意思可以试试树状数组套bitset 应该会快一些 总之50%达成 假期进度:66.7% 死ね #include<cstdio> #
BZOJ 1588 HNOI2002 营业额统计 裸Treap
题目大意:。。。题目描述不全看这里好了 给定一个序列 对于每个元素我们定义该数的最小波动值为这个数与前面所有数的差中的最小值(第一个数的最小波动值为第一个数本身) 求最小波动值之和 找最近的数只需要找前驱和后继就行了 平衡树的基本操作 不多说了 然后—— 此题多组数据!!尼玛!!看题目描述这也是单组数据啊!!什么**情况?? 而且多组数据尼玛也就算了!!输入数据还不全!!如果读到EOF需要按照0处
BZOJ 1040 ZJOI2008 骑士 树形DP
题目大意:给定一个基环树林,每个点上有权值,要求选择一个权值和最大的点集,要求点集中的任意两个点之间不能直接相连 最大点独立集……考虑到n<=100W,网络流铁定跑不了,于是我们考虑树形DP 对于每棵基环树,我们找到环上的一条边,设边上的两端点分别为u和v,f[i]为以i为根的子树在取i点的情况下的最大权值,g[i]为不取,于是我们有以下做法: 1.断掉这条边 2.u不取,v任意,我们以u为根跑一
BZOJ 1014 JSOI2008 火星人prefix Splay+Hash+二分
题目大意:给定一个字符串,提供下列操作: 1.查询从x开始的后缀和从y开始的后缀的最长公共前缀长度 2.将x位置的字符修改为y 3.在x位置的字符后面插入字符y 看到这题一开始我先懵住了。。。这啥。。我第一时间想到的是后缀数据结构 但是不会写 而且后缀数据结构也不支持修改操作 后来无奈找了题解才知道是Hash+二分。。。 太强大了 Hash+二分打爆一切啊 用Splay维护这个字符串的修改和插入操
BZOJ 3732 Network Kruskal+倍增LCA
题目大意:给定一个n个点m条边的无向连通图,k次询问两点之间所有路径中最长边的最小值 NOIP2013 货车运输,几乎就是原题。。。只不过最小边最大改成了最大边最小。。。 首先看到最大值最小第一反应二分答案 但是二分答案O(kmlogn)明显做不了 这里我们考虑最小生成树 先生成一棵最小生成树,然后每次询问利用倍增LCA求出路径上的最大权值即可 本蒟蒻居然把LCA写挂了。。。 而且样例还过了。。。
BZOJ 2048 2009国家集训队 书堆 数学算法
题目大意:经典的物理上的桌边堆书问题,初中物理老师曾经还讲过,不过只记住了结论。。。没关系,简单证明一下就好 首先我们设由上至下第i本书比它下面那本书多伸出去的长度为a[i],前缀和为s[i],那么我们要求的就是s[n] 为了简化问题我们设一本书的长度为1 假设n=1 a[1]=1/2,毫无疑义 然后考虑两本书 两本书的时候,重心明显在距下面那本书左端点的3/4处,故a[2]=1-3/4=1/4
BZOJ 3505 CQOI2014 数三角形 组合数学
题目大意: 给定一个m*n的方格,求上面有多少个格点三角形 m,n<=1000 枚举O(m^3*n^3),铁定超时 我们选择补集法 首先我们任意选择三个不重复的点构成三角形 用组合数算出这一值 然后刨除三点一线的点即可 枚举三点之中在两边的点的横纵坐标之差,中间点的位置数为GCD(x,y)-1,统计答案即可 注意初始计算组合数时可能会爆int #include<cstdio> #include<c