- 博客(5)
- 收藏
- 关注
RSS订阅原创 专题1：图论
专题1：图论 一、tarjan 我在之前的博客中详细介绍过，在这里直接放一个神奇的链接 二、2-SAT 2-SAT 问题是这样的：有nnn个布尔变量xixix_{i}，另有mmm个需要满足的条件，每个条件的形式都是“xixix_{i}为真/假或者xjxjx_{j}为真/假”。比如：“x1x1x_{1}为真或者x3x3x_{3}为假”、“x7x7x_{7}为假或者x2x2x_{2}为...
2018-03-07 16:32:35
353
原创 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
261
原创 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
279
原创 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
306
原创 Tarjan算法（蒟蒻专用）
一个蒟蒻眼中的tarjan算法(C++) 一、初识tarjan 第一次听见**tarjan**这个算法，这什么鬼，读音就很奇怪，百度一查才知道是一位巨佬的名字，也发现这是一个图论算法，在同学和老师的帮助下，简单的了解了一下这个算法，感觉好强，是我这个渣渣学到现在最复杂的算法了吧。 **tarjan**算法，在我这个蒟蒻看来，是一个更加复杂的搜索，可以找出一个复杂的图里的**强连通分
2017-08-16 23:06:41
637
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人