Absoler

未归档

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

/ 注册

全部文章 / 未归档（共29篇）

2-sat模板

2-sat用于解决这样一类问题：给出n个二元组，每个二元组必选出一个元素，而这些元素间可能有互斥的情况，要求给出合理方案。我们可以知道，对于二元组，如果因为被排斥而不选择某个元素，那么意味着必定选择另一个，这就使得问题可解，3-sat及以上似乎没有多项式算法……？ tarjan方法利用tar...

2020-05-09

0 568

构造算法题目积累

cf1304D 题目给出n-1个‘<’‘>’约束，第i个位置的<意味着结果串中a[i]<a[i+1]，要求用1~n个数构造出两个串，分别拥有最小和最大的LIS。思路：我们将升序1~n中连续>的区间执行reverse操作，执行完毕后的结果就是拥有最大LIS的满足约...

2020-05-09

0 474

lca倍增模板

lca即最近公共祖先，倍增法可以在O(n)的预处理后以每次logn的代价进行查询操作。思路：预处理出fa[n][i]数组，表示第n号点的第（1<<i）个父亲，之后在寻找u、v的lca时，可以对二进制上的每一位进行向上跳跃。例题：cf1304E 给出一棵树，有q个询问，格式...

2020-05-09

0 631

三分法

二分用于在单调序列上以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

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 548