- 博客(5)
- 收藏
- 关注
RSS订阅原创 专题1：图论
专题1：图论一、tarjan我在之前的博客中详细介绍过，在这里直接放一个神奇的链接二、2-SAT2-SAT 问题是这样的：有nnn个布尔变量xixix_{i}，另有mmm个需要满足的条件，每个条件的形式都是“xixix_{i}为真/假或者xjxjx_{j}为真/假”。比如：“x1x1x_{1}为真或者x3x3x_{3}为假”、“x7x7x_{7}为假或者x2x2x_{2}为...
2018-03-07 16:32:35
211
原创 BZOJ3224 普通平衡树
treap模板。。。没啥好说的啊。。。#include<iostream>#include<cstdio>#include<cstdlib>using namespace std;int m,sz,root,tmp;struct Tree{ int l,r; int num,rnd,w,s;}tree[400005];void update(int t){
2017-12-25 16:12:59
199
原创 BZOJ3196 二逼平衡树
线段树套平衡树因为线段树支持区间修改查询，平衡树支持查询第k大，一个数的排名，一个数的前驱、后继。所以选择两个数据结构套在一起。#include<iostream>#include<cstdlib>#include<cstdio>using namespace std;int n,m,sz,tmp;int a[200005],root[200005];struct Tree{
2017-12-25 14:18:25
224
原创 poj2892(treap)
poj2892(treap)我用的是treap操作的 每一次把被摧毁的村庄放进treap中，然后找到查询点的前驱和后继就是改联通块的起始点和终止点，之后每个联通块中村庄的个数也就知道了，每次修复时将这个村庄从treap中删除即可。#include<iostream>#include<cstdio>#include<cstdlib>using namespace std;int n,m;i
2017-12-21 21:34:11
241
原创 Tarjan算法（蒟蒻专用）
一个蒟蒻眼中的tarjan算法(C++)一、初识tarjan 第一次听见**tarjan**这个算法，这什么鬼，读音就很奇怪，百度一查才知道是一位巨佬的名字，也发现这是一个图论算法，在同学和老师的帮助下，简单的了解了一下这个算法，感觉好强，是我这个渣渣学到现在最复杂的算法了吧。 **tarjan**算法，在我这个蒟蒻看来，是一个更加复杂的搜索，可以找出一个复杂的图里的**强连通分
2017-08-16 23:06:41
497
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人