Evolution__-CSDN博客

原创 [Treap] LA5031 Graph and Queries

题意&思路其实蓝书上面已经说的很清楚了，就是给一个图，每一个点都有一个值，然后不断地删除某条边，修改某个点的值，然后查某个联通块里的第k大。做法就是静态处理，反过来做。因为如果是删除的话，有可能会导致一棵Treap要分裂，然后这显然很不好处理，相比起来往一棵Treap当中插入另一个显然更好，那当然是反过来做更好。那么用并查集来确定某个点所处于的块。合并的时候启发式合并，为什么说是启发式合

2017-08-24 19:31:04 251

原创 [Treap]poj2985 The k-th Largest Group

题意给出N只猫，然后有两种操作，分别是把两只猫所在的组合并，另一个是查询第k大的小组的猫的数量思路其实这道题目有很多种做法，但是查询第k大当然是用平衡树是最好的。那么在这里用并查集来记录每一个猫的小组，然后在Treap中插入每一个小组的数量。修改的时候就把原来的两个删去，然后再插入合并之后的值。但是这种方法会超时……可能是Treap写得不好的原因。那么很容易想到优化，因为输入保证查询的是在范围内

2017-08-22 22:06:57 278

原创 [Treap] poj 1442 Black Box

题意给出一个队列，然后对于u(i)u(i)，查询从第一个到u(i)u(i)的这一串当中的第i个数思路基本就是Treap的裸题，然后静态处理，因为u(i)u(i)是有序的，所以可以按照顺序来查询，然后基本就是套Treap的模板了代码依旧是谜一般的RE，去掉了srand就AC了……至今都不知道是为什么#include <ctime>#include <cstdio>#include <cstdli

2017-08-19 20:45:13 263

原创 [Treap] poj2761 Feed the dogs

题意给出一个序列，然后给出不同的提问。提问就是查询在这个序列的某一个区间的第k大思路这题按道理来说应该是主席树的模板题，但是在网上看到其实用Treap也可以静态地处理，所以在这里就说说这种Treap的静态处理方法吧。首先所有的区间都是互不包含的，尽管有可能会相交。那么可以先按照顺序先排序，然后从左往右往treap中加入元素，然后查询第k大，接着到下一个区间就把多的删掉，没有的加进去。

2017-08-18 21:18:34 215

原创 [平衡树]Treap实现Rank Tree

引入在之前的介绍Treap中，只有实现一般的BST的功能，相当于是一个STL的set，但是STL的set过度封装，所以对Treap稍加修改还可以实现一些其他的功能。比如说Rank Tree（名次树）基本概念Rank Tree在这里是建立在Treap的基础上写的。主要功能包含了Treap的所有功能，以及查询某一个排名是哪个数字（kth操作），以及查询某一个数字的排名（rank操作）实现对于Trea

2017-08-15 22:16:16 453

原创 [平衡树]Tree(BST) + Heap = Treap

引入首先其实平衡树就是BST，即二叉查找树，然后尽量使这棵BST保持平衡。我们知道BST容易退化，所以就有人发明了AVL树和红黑树，虽然这两种树的运行速度很快=_=，但是代码很复杂，插入删除旋转情况有很多种，才保证了它的平衡，所以后来又出现了Treap这种平衡树。虽然Treap比较简单，但是时间上却要稍稍差一点，而且有极小到几乎没有的可能（但是还是有）会退化，但显然在平时也已经够用了，所

2017-08-10 21:03:13 326

原创 [双连通分量]poj3694 Network

题意就是给出一个图，然后不断地给它加边，问有多少条桥思路首先这题其实和poj1679有点像为什么这么说呢，因为只要先求一次桥，然后就把双连通分量缩点，然后每一次连的边就可以相当于是求LCA，然后暴力LCA时经过的桥就不是桥了。然后看了网上一些题解发现连缩点都不用，可以直接用原来的点来做LCA。因为反向边必然不是桥，所以只有树边会是桥。所以沿着树边做LCA的过程其实就可以把缩点略过了←_←

2017-08-10 19:17:04 203

原创 [双连通分量]LA5135 Mining your own business

题意给出一个连通图，求在这个图中，至少给多少个点染色，使得在删除了任意一个点后，每个连通分量里都有一个染色的点，并且求方案数。思路首先先求一次双连通分量，然后用贪心的思想发现，如果把割点染色，显然一旦割点被删就会有多个连通分量中没有染色点，所以给割点染色是不好的。那么只要将一个双连通分量中的一个非割点染色，那么就算割点被删，它也能自成一体，如果所有的双连通分量都是这样，即使这个点被

2017-08-08 20:34:41 206

原创 [双连通分量]LA3523 Knights of the Round Table

可以说是第一次写蓝书上的题←_←也是第一次去做LA题库上的题，所以是用VJ交的2333。题意有很多个骑士，有些骑士相互憎恨，然后可以举办圆桌会议，允许3个及以上的奇数个骑士参加，相互憎恨的骑士不能相邻地坐，问有多少名骑士一个会议都不能参加。思路首先先把原来的问题转化成一个图的问题。把骑士都看做结点，然后建立一个无向图，如果两个骑士可以相邻，也就是不相互憎恨，就连一条无向边。相当于是把憎恨的关系看

2017-08-02 20:12:44 254

原创 [双连通分量]poj1679 Road Construction

题意给出一个连通的无向图，求至少增加多少条边让这个图变成边双连通图思路其实题目意思很清晰很明白，但是怎么操作才是重点。那么首先先想想怎么把整个图简化一下，先求一次边双连通分量。因为边双连通分量本来就是个边双连通图，那么这里面无论怎样增边，都是无意义的，那么就可以把它缩成一个点。将所有的边双连通分量都缩成一个点之后，原图变成了一棵树。那么，如何让一棵树变成一个双连通图，是一个问题。

2017-07-31 22:26:35 203

原创 [双连通分量] tarjan算法

在前面说的话其实这个借鉴了网上的一些教程/总结，但是主要还是看lrj的蓝书并有部分引用以及自己的一些理解而成的，仅仅是为了给自己或他人总结用的，而不希望用于任何其他的用途亦或是被说抄袭。引入首先先来看几个概念割点（割顶、关节点），在一个无向图中，如果删除了某一个点，能使连通分量的个数增加，那么称这个点为割点特殊的情况：对于一个连通图，割点就是在删除以后能让原图不再连通的点桥，在一个无向

2017-07-26 20:09:50 1742

原创数组+链表 = [骗分]块状链表

前言众所周知，对于一个一维的数组，或是一个字符串，我们可以使用两种办法：数组或链表两种方法来储存。但是，看了国家集训队2008年苏煜的论文之后，就知道了一种神奇的骗分方式：数组+链表形成的块状链表。先来看看块状链表和两种方式的对比方式修改查询链表 O(N)O(N) O(1)O(1) 数组 O(1)O(1) O(N)O(N) 块状链表 O(N−−√

2017-01-15 20:43:13 545

原创 NOIp2016酱油记

今年NOIpNOIp的题目似乎不算很难，但是应该是自己太久没有大量敲代码，水分的能力大大降低。不过还好，对于非浙江这些变态的地区，还能恰好水到1=……对于压线这种事，还没有出现在我身上…… 不过似乎也没有什么区别了，只是多了15分而已……

2016-12-22 21:22:20 332

原创 [对罗穗骞论文的一点理解]后缀数组——倍增算法

基本定义首先先来看几个定义：字符串的大小比较从第一位开始，按照字典序比较大小，如果相同则比较后一位，否则按照当前这一位的比较结果确定结果，如果比较的时候这一位已经超出其中一个串的长度，则比较它们的长度，长的一个串比较大，如果长度相等，那么它们也相等。后缀数组用SA\text {SA}表示，它是一个一位数组，保存的是所有后缀的排序，每一位表示的就是按照大小排序的这个后缀是从哪一位

2016-08-14 16:35:16 876

原创 [网络流]SPOJ962 Intergalactic Map

题意有一个无向图，求是否能够不重复经过一个点地从1走到2再走到3思路首先，可以想到利用网络流来求解，建图的时候，把每一个点拆成两个点，之间连一条容量为1的弧然后根据原图将每一条弧加入到网络中，注意是像Pi→P′jP_i → P'_j来加边但是要注意一点，因为是从1走到2再走到3，显然这是很难做的，那么可以换一个思路，假设不是从1走到2再走到3，而是从2开始，不重复经过一个点，走到1和3 这

2016-08-13 08:14:55 286

原创夏令营第一周总结

开营测试感觉这将会是夏令营考得最好的,因为当时出的题基本都是在暴力的基础上加一些算法和技巧就能A的题，然后我写了很多的暴力，接着就得了很高的分……状态压缩DP之前学过，然后学得也不是太难接受，接着做的题目除了一道很难的题以外都已经A了。主要就是效率不高，对这种写法不熟，错了调程序的时候很痛苦，明明知道这种做法是对的，可就是找不到哪一个细节错误，基本上每一题都要调很长时间才能勉强做出来，

2016-08-11 19:50:16 404

原创 [网络流]poj2391 Ombrophobic Bovines

题意有很多的雨棚，每个雨棚现在有aia_i头奶牛，每个雨棚可以装bib_i头奶牛给出各个雨棚之间的距离，求出能够让所有奶牛都在雨棚之中的最小时间，如果不能满足输出-1思路可以先用floyd求所有点对之间的最短距离，然后二分时间，如果当前的限制下能够让所有的奶牛都有雨棚，那么r←midr ← mid，否则l←mid+1l ← mid + 1 求是否能让所有的奶牛都在雨棚中可以用以下

2016-08-10 14:51:07 216

原创字符串匹配-扩展KMP(Extend-KMP)

首先还是来看看问题：给出一个长为N的字符串S，再给出一个长为M的字符串T 求S的所有后缀中和T的最长公共前缀显然可以想到暴力的做法，枚举S所有的后缀，然后和T做匹配，时间复杂度为O(NM)O(NM) 显然，这个方法和之前的暴力一样，都处理了太多的重复操作，那么可以用类似KMP的方法来处理吗？答案是肯定的，也就是Extend-KMP算法

2016-08-08 11:13:27 3994 8

原创最长回文子串-manacher算法

像kmp一样，先来看一道题目给出一个长度为n的字符串S，求S的子串T，令T反转后T`与T完全相等，求T最大的长度。首先，可以想到用暴力做，枚举所有的子串，然后判断，时间复杂度为O(N3)O(N^3) 第二，可以发现，如果子串S[1..5]是一个回文串，那么S[2..4]自然也是一个回文串。利用这个性质，可以枚举所有串的回文中心，然后从中间向两边去查找、判断。最后的时间复杂度为

2016-08-08 07:27:49 183

原创字符串匹配 KMP算法

首先先来看一个问题，给出两个字符串，S和T 问T在S中出现了多少次，不允许重复，但允许相互有相同部分。首先想到的肯定是暴力，可以想到，从S的第一个字符开始，看是否和T相等，然后向后移，统计有多少个相等，那么时间就是O(n×m)\text O(n\times m) 当然，这个速度是非常慢的，如果两个串的长度很长，或者有多组数据，自然就超时了。显然，在匹配的时候，如果遇到不相等的情况，移到下

2016-08-06 21:32:51 337

原创夏令营-开营测试

第一题-音阶（ljestvica）题意：给出一个只包含“A”, “B”, “C”, “D”, “E”, “F”, “G”, “|”的序列，每一个“|”都隔开了一个音节，每一个音节的第一个字符代表的是重音。 main tones在A小调中就是A、D、E，在C大调中就是C、F、G。判断这首曲子是用A小调写的还是用C大调写的。可以数在重音中是A小调的main tones多还是C大调的m

2016-08-05 08:00:32 254

原创最大流-最小割定理&poj3469 Dual Core CPU

对于最大流问题中，经常会涉及到一个叫做最小割的部分，那么，首先先来看看最小割是什么。在一个图G(V,E)中，通过去掉一些边的方式，使得节点u与节点v不连通，这就是节点u和节点v的一个割。在G之中，有一些路径联通s，t，如果去掉一些边使s，t不连通，那么这个割的办法就是一个s-t割。每一个割的容量就是这个割集中所有边的容量之和。讲完这些基础理论，自然容易猜到最小割就是在图G中，容量最

2016-07-30 20:25:40 480

原创 [网络流]最大流算法 Dinic

最近做了几道题，发现用Ek算法会超时，而事实上，Ek算法使用的机会并不多，更多的是用Dinic和ISAP算法。所以特地找了一段时间来学习、理解和编Dinic算法。类似之前的储存方法，但稍作修改，代码如下：struct Edge { int from, to, cap, flow;};这样储存的是一条边。在做题的过程中，发现一个技巧（也算是技巧吧），出现无向边时，不需要加两条边

2016-07-29 21:30:39 4686 1

原创 [网络流]poj2112 Optimal Milking

题意：有K头奶牛和C台挤奶机，每台挤奶机最多供M头奶牛使用，给出奶牛与挤奶机之间的距离（邻接矩阵），求走得最多的奶牛最少要走多少才能保证每一个奶牛都能找到挤奶机。思路：首先给出的距离必然不是最短路，那么要让求的时候尽可能简单，使用Floyd算一下最短路。然后求最大值最小，想到用二分的办法，让求解区间成为[l,r），最后返回r即为答案。可以想到，l = 0是必然不成立，而r =

2016-07-21 19:29:36 245

原创 [网络流]poj3281 Dining

题意：有N头奶牛，D种食物和K种饮料，每头奶牛有自己喜欢的食物和饮料，每种食物和饮料只能被一头奶牛选，一头奶牛只能选一种食物和饮料，求最多会有多少头奶牛既能吃到自己喜欢的食物又能喝到喜欢的饮料。思路：这种题目就是赤裸裸的最大流。建立一个源点，从源点开始，连接每一种食物，容量为1，每种食物连接喜欢这种食物的奶牛，容量为1，每头奶牛连接它喜欢的饮料，所有饮料连接汇点，做一次最大流。

2016-07-20 19:58:35 264

原创 [网络流]poj1149 PIGS

题意：一个农场有M个猪圈，每个猪圈里有很多猪，现在有N个顾客，每个顾客可以拿到一些猪圈的钥匙来买猪，买完之后会关上门，顾客是严格按照顺序来的，不会出现顾客A和顾客B同时在农场的情况。顾客打开门之后，这个猪圈里的猪可以任意换到其他的打开着的猪圈中，求最多能卖多少只猪。思路：这样的网络流题目，必然要构图。从源点开始，向每个猪圈的第一个顾客连一条边，容量为这个猪圈的猪的数量。接着后面来的

2016-07-19 20:41:23 283

原创 [网络流]poj1698 Alice's chance

题目大意：Alice要去拍电影，要拍很多场电影，每部电影在一周中只有其中的几天可以拍，需要拍D天，最多必须在W周之内完成，Alice每天只能拍一场电影，如果Alice可以满足所有电影的要求，输出“Yes”，否则输出“No”输入格式：先输入T，有T组数据每组数据第一行是N,表示有N部电影接下来N行，每行有9个数字，前7个代表一周中的每一天是否能拍，第八是D，第九是W思路：

2016-07-18 22:08:24 297

原创 [最大流]增广路算法Edmonds-Karp

最大流可以看做是把一些东西从源点s送到汇点t，可以从其他的点中转，每条边最多只能输送一定的物品，求最多可以把多少东西从s送到t，这样的问题就是最大流问题。如图节点1为源点，节点6位汇点每一条边上的数字即为这条边最多能输送的数量，也称为容量。（对于不存在的边，容量为0）这个图能够求出的最大流为23从源点开始，送12到2、送11到3，2送12到4，3送7到4、送4到5，4送

2016-07-16 20:47:49 6219 1

原创 [模板]线段树

如题，给出一种数据结构的模板#include #include #include #include using namespace std;class SegmentTree { private: int fp; struct Tnode { int LeftChild,RightChild; int l,r; in

2016-05-29 14:54:53 223

这一次去gdoi 是第一次，于是原本就打算要去打酱油，接着，很愉快地没有爆零……竟然混了一个三等奖回来……day0坐车到四会，去到贞山宾馆，然后分房间，和高中的神犇ZZB分到了一间房，再接着，就直接坐车去四会中学吃饭，话说四会中学的饭菜好便宜，比我们学校便宜多了……而且味道也比我们学校的要好……晚上回来，随便复习了一下，看了看LCS，接着就开始抽手机了……day1早上在宾馆吃早餐，只有一个包，一份

2016-05-18 12:58:25 355

原创集训第一周总结

这总结也算是迟到了吧，第二周都快过完了才写……集训的第一周首先是重做市选的题目。首先是先重做了上午的题。在这里先简单说说思路：第一题主要是用贪心策略，计算出最多能举行的比赛，再通过枚举计算举行x场比赛是否成立，求出最大值。第二题就是通过偏移量求出公式，（具体证明当然是另外开一篇来讲啦）：求每一个节点在k叉树上的父亲的公式——(x + k - 2) / k。接着不停地将两个节点变成自己的父亲

2016-05-18 12:58:23 386

原创 USACO Angry Cows总结

Angry Cows总共有三道题，分别是铜牌组的、银牌组的和金牌组的。首先先看铜牌组的这一道题题目描述牛奶Bessie设计了一个游戏：“愤怒的牛奶”。游戏的原型是：有一些可爆燃的草堆分布在一条数轴的不同坐标，玩家用弹弓把一头奶牛发射到数轴上。牛奶砸到草堆上的冲击能量会引发草堆燃爆，并有可能引起附近的草堆连环燃爆。游戏的目标是玩家用一头奶牛燃爆尽可能多的草堆。有N个草堆在数轴的不同位置，坐标为x1,

2016-05-18 12:58:20 1257

原创线段树-基础

线段树是一种高级数据结构，可以用于解决动态的区间最值问题和区间求和问题。这一种算法比纯粹的模拟算法要快。例如每次修改单个数，求一个区间的最优值。用模拟算法每一次修改单个数要O(1)的时间，查询要O(N)的时间，总共修改M个数，时间复杂度为O(NM)，而线段树每一次修改需要O(logN)的时间，修改M次，总时间为O(MlogN)，整体会比模拟算法快得多。二叉树通常是一棵完全二叉树，占2^N的空间，

2016-05-18 12:58:17 173

原创最小生成树[Prim]

问题：参照[Kruskal]原理：Prim算法使用的是一种贪心的思想，通过从一个点出发，选择所有链接这一个点的边中，选择权值最小的边。在选择了这一条边之后，优化之前的边的选择方案。在最后，把所有的最小边之和加起来就得到了最小的方案来看一个例子首先，在第一个点的所有链接的边中，选择链接到5的边，设置到达2的最小边为7。从5出发，发现到4的边最短，选择这一条边。将到达3的最小边设置为2查询4号点，发

2016-05-18 12:58:14 233

原创最小生成树[Kruskal]

最小生成树问题：在一个无向图中，链接每一条边都有相应的权值，如何链接这一些边，让这一个图成为一个连通图，而且让权值之和最小。根据题目，可以得知生成一棵最小生成树使用的自然需要链接n-1条边使这一个图变成连通图，显然可以使用DFS和BFS来尝试每一条边是否能成立，但是这自然效率低下。所以，生成一棵最小生成树，自然需要使用到一种算法——最小生成树算法。首先先介绍一下Kruskal算法。这是一种以贪心为

2016-05-18 12:58:12 227

原创 Floyd 多源最短路径算法

为求出一个无向图每一个点之间的最短距离，就可以使用到Floyd算法。首先，把每一条最短路径表示为 dis[i,j] ，接着就需要求出每一个点到其他点的算法。例如这样的一个图要求出每一个节点之间的距离，首先想到的自然是BFS，但是这样的速度太慢，所以，就需要引出Floyd算法了。Floyd的本质是DP的一种。每一个节点到另外一个的长度自然可以表示为i到其中一个中间节点的距离加上这个中间节点到另一个节

2016-05-18 12:58:09 1271

原创拓扑排序

定义：给出一个一个序列中每一个节点的关系，即每一个节点必须在另一个节点的前面。那么如何求出这一个序列，但是这一个序列可能不止一种。而拓扑排序就是用来处理这一种问题的。首先先把要在前面的节点链接到在它后面的节点，组成一个有向无环图。计算每一个节点的入度，然后把每一个入度为0的节点删去，同时删去这些边。反复进行操作，直到所有的节点都被删除为止。这时候删除的顺序就可以作为这样的序列。例题：poj2367

2016-05-18 12:58:06 255

原创 message[时间标记]

题意分析：在一个有向图中，含有N个点和N条边，求出在这个图中最小环的长度。思路分析：时间标记是一种通过类似DFS的方法，但是在其中记录了每一个点的访问次序，通过记录访问次序，来求环。从任意一个节点开始，每访问一个节点，就给它记录当前的时间标记。当访问到一个节点，它的时间标记已经被记录了，就证明至少会形成一个环。而在这个环当中，会出现两种情况，如果另一个节点已经和它产生了一个环，而这

2016-05-18 12:58:04 303

原创 stone

题目的大概意思是：在一条道路上有N个石头，现在要移走M个石头，问移走之后剩下的石头中的最小的距离最大是多少。首先，根据题目，以及修改数据发现，如果移走的石头越多，那么答案就会越大。从这里就证明了答案是具有单调性的。根据这一点，那么答案就可以用二分答案的方法来求出。首先，每一个答案都需要验证需移走的石头数是多少，那么，到底要怎么移动，才能让移走的数量最少呢？例如样例2 11 1417

2016-05-18 12:58:01 309

原创关路灯——power 解题报告

关路灯源程序名 power.pas/c/cpp 可执行文件名 power.exe输入文件名 power.in 输出文件名 power.out【问题描述】某一村庄在一条路线上安装了n盏路灯，每盏灯的功率有大有小（即同一段时间内消耗的电量有多有少）。老张就住在这条路中间

2016-05-16 13:57:15 1004

空空如也

空空如也