Absoler

分类

Java开发(1) MFC(1) 动态规划(5) 图论(7) 基本算法(6) 字符串(3) 思维(2) 搜索(7) 数学(2) 数据结构(4) 未归档(29) 杂项(1) 树(2) 模板(3) 真题(9) 计算几何(1)

/ 注册

TA的专栏 9篇文章 0人订阅

9篇文章 1279人学习

全部文章（共83篇）

三分法

二分用于在单调序列上以logn的时间确定某个值，三分则用在凸函数上，即先增后减序列，可以找它的极值。我们需要mid=(l+r)/2和midmid=(mid+r)/2这两个分界点，前者大则令r=midmid，否则令l=mid。例题：cf939E 1 2 3 4 5 6...

2020-05-09

0 389

欧拉回路模板

直接介绍复杂度最低（O(n+m)）的Hierholzer方法。它能帮我们找到一条欧拉回路。欧拉回路指不重复经过所有边的一条回路，在有向图中，如果满足每个点入度=出度则存在欧拉回路。在无向图中，满足每个点度数为偶数则存在欧拉回路。它具有这样的性质，即从一个欧拉图中去除一个小欧拉图，剩下的...

2020-05-09

0 697

数位dp模板

本质是记忆化搜索，一般求解区间[l,r]内有多少数字满足要求。我们可以拆分问题为solve(r)-solve(l-1)或solve(r)-solve(l)+judge(l)。注意到整个区间（例如[0,999]）在很多地方重复使用，所以对它记录。例题：cf628D 1...

2020-05-09

0 725

codeforces/1312E（区间dp）

题目这道题不管从内容还是数据范围看起来都像是区间dp，可一时想不出来怎么构造出一个满足无后效性的区间状态，看了一眼题解才顿悟。分两步走，第一步我们求出所有的dp[l][r]，表示[l,r]区间可以最终转化为的一个数，如果无法转化则为零，这一步的巧妙就在于包含了足够的信息来“总结”这个区间。第...

2020-05-09

0 760

treap(可持久性)模板

普通treap：参考https://www.csdn.net/gather_2a/MtTacg3sMTE0NS1ibG9n.html cf702f：将所有人的钱数放入平衡树，每次按照可选衣服的价格将树一分为二，对于有购买能力的一棵树上的人钱数减去衣服价格，然后将剩余钱数小于c-1的再...

2020-05-09

0 494

强连通分量模板

知识背景：首先明确强连通分量(strongly connected component)的概念，从任一顶点能够到达任一其他顶点的有向图的顶点子集，而任意有向图均可以分解成若干不相交的scc。把每个scc视作一个顶点，可得到一个DAG。实现算法：两次dfs，第一次 dfs 遍历将顶点后序(po...

2020-05-09

0 516

割点和桥模板

寻找连通图的割点和桥用的也是tarjan算法，我们计算每个点不经过父亲能到达点的最小dfs序，如果是大于等于父亲的，则说明去掉父节点，该点即无法同上面连通，所以父节点是割点。桥类似，我们对于每个点标记它到父亲的那条边是否是桥。 cf1277E：给出一个图求对于两点ab，有多少对xy使得从x...

2020-05-09

0 511

spfa&差分约束模板

cf1131D 给出一个n*m关系表，有<>=三种关系，要求为这n+m个对象分配一个值，使得满足约束关系且最大值最小。用差分约束，＞转化为>=x+1。=转化为>=且<=。如果y要比x至少大1，就建立边x指向y。对于这样一张图，满足所有要求其实就意味着能走的边都...

2020-05-09

0 547

树上启发式合并模板

这个算法真是研究了好久才明白……众多博客真的不是面向小白的模板拿cf600E举例子，问题是给一棵有根树（rt==1），每个节点有一个颜色值，树的节点数和颜色值的范围都是1e5。对于每个节点我们定义其子树中数量最多的那个颜色值为主颜色（可以有多个并列），现要给出每个节点的主颜色的值的和。首...

2020-05-09

0 517

树上启发式合并（dsu on tree）一篇就会！理解其他博客的基础

这个算法真是研究了好久才明白……众多博客真的不是面向小白的模板拿cf600E举例子，问题是给一棵有根树（rt==1），每个节点有一个颜色值，树的节点数和颜色值的范围都是1e5。对于每个节点我们定义其子树中数量最多的那个颜色值为主颜色（可以有多个并列），现要给出每个节点的主颜色的值的和。首先想...

2020-05-09

0 525