zerollt-CSDN博客

原创【模板】二逼平衡树（树套树）【树状数组套线段树】

题目描述被各种毒瘤线段树虐过后突然感觉这道卡了我一万年的树套树很水（就一道模板题，不想讲了）代码#include<iostream>#include<cstdio>#include<algorithm>#include<cstdlib>#include<cstring>using namespace std;c...

2018-04-15 18:01:14 479 1

原创 [NOI2014]动物园【kmp】

题目描述每次写kmp都要调一万年这题主要两个数组next[]next[]next[ ]和num[]num[]num[] num[i]num[i]num[i]表示以iii结尾的前缀所能匹配的数量(可重叠的)代码#include<iostream>#include<cstdio>#include<cstring>#include<cst...

2018-04-07 20:17:06 226

原创 [SDOI2014]旅行【树链剖分+主席树】

题目描述最喜欢这种细节少少的组合型问题了，感觉被树套树虐过之后其他数据结构都简单了这题就是简单的树链剖分+主席树，好像只要会就不是很容易写错信仰每一种宗教的单独建一颗线段树就好了代码#include<iostream>#include<cstdio>#include<algorithm>#include<cstdlib>#...

2018-03-09 20:51:06 168

原创 [SDOI2011]染色【树链剖分】

[SDOI2011]染色线段树部分还要带两个成员lc(该区间最左边的结点颜色)和rc(该区间最右边的结点颜色) ，其他应该都是裸的树链剖分我被卡死是在询问的时候，最后top[u]==top[v]的时候，要判断两边的color和之前的两条链的顶端是不是一样(我把之前两条链的顶端记反了)代码#include#include#include#include#include#

2018-02-07 19:14:58 163

原创 [ZJOI2008]树的统计【树链剖分】

[ZJOI2008]树的统计感觉树剖是我打过要调最少的数据结构了询问就一直顺着链走就好代码#include#include#include#include#include#define ll long long #define lo o#define ro o#define mid ((l+r)>>1)using namespace std;const ll

2018-02-01 20:48:39 146

原创 [HAOI2015]树上操作【树链剖分】

[HAOI2015]树上操作卡我的居然是线段树，orz，尝试了各种lazy标记终于A了这道题好像比树链剖分的模板题还简单其实感觉树剖并不难理解，核心就是两次dfs,第一次分轻重链，第二次处理各种与编号有关的东西，处理完之后以某一结点u为根的子树就是id[u]~id[u]+siz[u]-1的节点，u到这条链的顶点的节点就是id[top[u]]~id[u]这些点，所以就很好处理了对于本

2018-02-01 17:53:28 137

原创 [USACO15JAN]草鉴定Grass Cownoisseur 【Tarjan+搜索】

[USACO15JAN]草鉴定Grass Cownoisseur缩点后从正向和反向搜一遍得到两批点，1能到达的点和能到1的点，处理出到达这些点最多可以经过的点数，再枚举能连上边的点求一求就好了代码#include#include#include#include#include#includeusing namespace std;const int N=100010;

2018-01-29 20:59:39 363

原创 [SHOI2009]Booking 会场预约【Treap】

[SHOI2009]Booking 会场预约写题半小时，调试一万年系列Treap里面包含各种神奇的成分，然后在找重合区间的时候顺便删掉，要不会TLE代码#include#include#include#include#includeusing namespace std;struct node{ node* ch[2]; int low, high, s,

2018-01-26 21:30:58 133

原创 [NOIP2007] 矩阵取数游戏【记忆化搜索+高精】

题目其实感觉这题重点不是dp而是高精因为只能取队首尾的数字，所以用dp[i][j]表示取剩下的i~j的数所能得到的最大值dp[i][j]=max(dp[i+1][j]+2^(m-j+i)*num[i],dp[i][j-1]+2^(m-j+i)*num[j]);代码#include<iostream>#include<cstdio>#include<algorithm>#include<cstd

2017-12-24 12:06:54 230

原创 [Flokirie的测试赛]Roy&October之取石子【sg函数】

题目SG函数->博弈论随记(SG函数) 看完之后还一脸蒙蔽的话可以尝试一下这篇论文算法合集之《由感性认识到理性认识——透析一类搏弈游戏的解答过程》这道题大概是打表找出规律，当然弄懂这类Nim游戏才是最重要的经历了一天的学习终于懂了，然而感觉头发都要掉光了代码（打表和最终输出都在里面）#include<iostream>#include<cstdio>#include<algorithm>

2017-12-23 21:13:19 274 1

题目很明显的背包问题，向上飞可以点无限次，所以是完全背包，向下掉只可能掉一次，所以是01背包。又因为不能在掉落之后再上升，所以要先算完全背包我开始用的是递推，75分（TLE5个点…），对于每一列能够到达的点，推出下一行所能到达的点（所以就重复计算了很多次，完全没有用到背包的思想）接着开始考虑背包，对于一列i的纵坐标j,f[i][j]表示到达这个点需要点击的最小次数,那么f[i][j]=min{f[i

2017-12-22 18:35:30 313

原创 NOIP2015 过河【递推（dp）+离散化】

题目描述题目状态转移方程f[i]=min{f[i-j]+map[i]|s<=j<=t};f[i]表示到达距离i会踩到最少的石子，map[i]表示此处是否有石子因为石子个数比较少，而独木桥的长度比较长，所以要稍微离散化一下，又因为1~10的最小公倍数为2520，如果从i出发，如果i到i+2520中间没有石子的话f[i~i+2520]的值都是相同的，就可以把这一段路去掉代码#include<io

2017-12-19 14:12:40 232

原创 [HNOI2012]永无乡 SBT+启发式合并

题目描述题目我也不知道启发式合并到底是什么东西好吧，启发式合并就是把小的集合往大的集合合并，学并查集的时候不是有把小树根的父亲设为大树根的操作吗，这大概就是启发式合并的一个典例对于这道题，我的做法是把小SBT的所有结点从小到大全部加入到大SBT中（本来打了个Treap，懒得旋转了，就改成了SBT，还好没有极限数据卡我），大概把并查集的操作省略了代码#include<iostream>#in

2017-12-17 12:16:34 176

原创 NOIP2015 运输计划二分答案+Tarjan LCA+树上差分

题目描述题目需要的最短时间，明显二分判断答案是否可行只要把超过答案的路径都记下来，找到一条所有超过的答案路径都经过的边，尝试删掉它，如果最长的路减去它小于答案，那么此答案就是可行的解至于统计所有路径都经过的边，差分统计一下就好经过running的折磨，感觉transport突然变简单了代码#include<iostream>#include<cstdio>#include<cstri

2017-12-16 21:50:38 258

原创 NOIP2016 天天爱跑步 TarjanLCA+树上差分

题目描述题目这题的差分和一般的树上差分写法差好远，参考了dalao的题解还磨了好久才写出来主要要注意的有以下几点： 1.起点s和终点t千万不要弄错（被它卡了半天的我QAQ） 2.记深度为d的起点的总数为cnt[d]：对于一条向上走的路，在起点处cnt[d]++,搜到终点的时候cnt[d]–；向下走的路，终点处cnt[d]++,起点处cnt[d]–给这道题的细节处理跪了ORZ，磨了三天才终于A

2017-12-15 21:09:01 291

原创 Luogu P3398 仓鼠找sugar 倍增LCA

题目描述题目差不多是裸的LCA吧只要处理好两条相交路径之间的关系就好了如果两条路径相交，那么一条路径的LCA一定在另一条路径上那么需要满足dep[lca1] >= dep[lca2]lca(lca1,s) == lca1 || lca(lca1,t) == lca1代码#include<iostream>#include<cstdio>#include<cstdlib>#in

2017-12-11 18:58:31 242

原创 [JLOI2014]松鼠的新家倍增LCA+树上差分

题目描述题目本来想写一道Tarjan的，结果发现这题倍增比较好写这题主要要搞懂树上差分这东西（NOIP前这东西卡了我好久）大概要注意的就是对于除了出发点以外的所有点都是重复算了的，所以最后要有-1操作代码#include<iostream>#include<cstdio>#include<cstdlib>#include<algorithm>#include<cstring>u

2017-12-11 18:08:18 173

原创 [USACO5.3]校园网Network of Schools Tarjan缩点

题目描述题目对于任务A，即求缩点后入度为0的点的个数对于任务B，要使整个图连通，则入度0的点需要拓展一条入边，出度0的点需要拓展一条出边，那么需要拓展的最少边数即为max(入度0点数，出度0点数)；特别的，当本来整个图连通时，不需要拓展代码#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#in

2017-12-08 21:52:03 174

原创 [HAOI2006]受欢迎的牛 Tarjan缩点

题目描述题目数据结构暂时先告一段落，那些复杂的数据结构对于现在的我来说太麻烦了，写了也没有意义，所以等以后代码力强一点的时候再回去把暂时放弃的数据结构学完接着进入图论的学习最短路已经很熟了，就不必再回去学了而之前只是囫囵吞枣地学了一遍各种Tarjan算法，所以我打算多刷点题巩固一下这题是关于缩点的问题强连通视频学习对本题如果只存在1个强连通分量，那么所有牛都是受欢迎的如果存

2017-12-08 19:45:37 168

原创 [CQOI2015]任务查询系统主席树

题目描述感觉再写数据结构我要折寿了以时间为版本，优先级为价值建立主席树对于一个任务，我们只要在任务开始的时候把它加进去，再在任务结束之后把它删除，其他时候只要继承上一个时间段的就好了，所以应该是很好实现的，差分然后求前缀和就好跑得很慢内存很大的代码（懒得优化了）#include<iostream>#include<algorithm>#include<cstdio>#include<cst

2017-12-06 18:14:41 187

原创【模板】可持久化数组（可持久化线段树/平衡树）

题目描述题目模板模板线段与它的历史版本新的版本只要在历史版本上修改一条路就好了继续打指针指针真的好用（题目说可以是可持续化的线段树/平衡树，我在考虑要不要学着写一波可持久化的平衡树）代码（可持久化线段树）#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#include<algor

2017-12-05 13:53:50 280

原创【模板】可持久化线段树 1（主席树）

题目背景这是个非常经典的主席树入门题——静态区间第K小数据已经过加强，请使用主席树。同时请注意常数优化题目描述如题，给定N个正整数构成的序列，将对于指定的闭区间查询其区间内的第K小值。输入输出格式输入格式：第一行包含两个正整数N、M，分别表示序列的长度和查询的个数。第二行包含N个正整数，表示这个序列各项的数字。接下来M行每行包含三个整数 l,r,k , 表示查询区间[l,r]内的第k

2017-12-04 20:12:02 221

原创 [JSOI2008]最大数maxnumber 线段树

1012: [JSOI2008]最大数maxnumberDescription　　现在请求你维护一个数列，要求提供以下两种操作：1、查询操作。语法：Q L 功能：查询当前数列中末尾L 个数中的最大的数，并输出这个数的值。限制：L不超过当前数列的长度。2、插入操作。语法：A n 功能：将n加上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数

2017-12-04 13:55:47 176

原创 [ZJOI2006]书架 Treap

题目描述小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸引力了，所以她看完后常常会忘记原来是放在书柜的什么位置。不过小T的记忆力是非常好的，所以每次放书的时候至少能够将那本书放在拿出来时的位置附近，比如说她拿的时候这本书上面有X本书，那么放回去时这本书上

2017-12-02 14:24:33 261

原创 NOIP2017 列队线段树（指针版）+vector

题目描述Sylvia 是一个热爱学习的女♂孩子。前段时间，Sylvia 参加了学校的军训。众所周知，军训的时候需要站方阵。Sylvia 所在的方阵中有 n×m名学生，方阵的行数为 n，列数为 m。为了便于管理，教官在训练开始时，按照从前到后，从左到右的顺序给方阵中的学生从 1 到 n×m 编上了号码（参见后面的样例）。即：初始时，第 i 行第 j 列的学生的编号是(i−1)×m+j。然而在练习方

2017-12-01 19:51:25 415

原创郁闷的出纳员 Treap

题目描述OIER公司是一家大型专业化软件公司，有着数以万计的员工。作为一名出纳员，我的任务之一便是统计每位员工的工资。这本来是一份不错的工作，但是令人郁闷的是，我们的老板反复无常，经常调整员工的工资。如果他心情好，就可能把每位员工的工资加上一个相同的量。反之，如果心情不好，就可能把他们的工资扣除一个相同的量。我真不知道除了调工资他还做什么其它事情。工资的频繁调整很让员工反感，尤其是集体扣除工资的时候

2017-11-30 13:06:42 224

原创 P3391 【模板】文艺平衡树（Splay）

题目背景这是一道经典的Splay模板题——文艺平衡树。题目描述您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1输入输出格式输入格式：第一行为n,m n表示初始序列有n个数，这个序列依次是 (1,2,⋯n−1,n) m表示翻转操作次数接下来m行每行两个数 [

2017-11-27 20:11:26 309

原创 [HNOI2004]宠物收养场 Treap

题目描述凡凡开了一间宠物收养场。收养场提供两种服务：收养被主人遗弃的宠物和让新的主人领养这些宠物。每个领养者都希望领养到自己满意的宠物，凡凡根据领养者的要求通过他自己发明的一个特殊的公式，得出该领养者希望领养的宠物的特点值a（a是一个正整数，a<2^31），而他也给每个处在收养场的宠物一个特点值。这样他就能够很方便的处理整个领养宠物的过程了，宠物收养场总是会有两种情况发生：被遗弃的宠物过多或者是想要

2017-11-26 14:14:40 223

原创【模板】普通平衡树 Treap

题目描述您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作： 1.插入x数 2.删除x数(若有多个相同的数，因只删除一个) 3.查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数，因输出最小的排名) 4.查询排名为x的数 5.求x的前驱(前驱定义为小于x，且最大的数) 6.求x的后继(后继定义为大于x，且最小的数)输入输出格式输入格式：第一行

2017-11-24 18:23:17 270

zerollt的代码堆积地

原创这个博客弃置了！