Absoler

未归档

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

/ 注册

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

树上启发式合并模板

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

2020-05-09

0 517

长链剖分优化树上dp

长链剖分可以把维护子树中只与深度有关的信息做到线性的时间复杂度。例题cf1009f 给一棵树，定义每个点的dom值为，以该点为根的子树重中，节点数最多的那一层的层数，即那一层距离这个根节点有几条边，如果多层节点数相同，取最小的层数。例如单独叶节点的dom值是0，一条垂直的链的dom值也是0...

2020-05-09

0 642

上下界网络流

cf704D 给棋盘上n个棋子染色，红黑两种，代价不同，有m个约束，要求某一行或某一列的红黑棋子数差不能超过某一数值。求最小代价的染色方案。上下界网络流的思路就是分别减去最低流量，剩余的放在图中跑最大流，对于原有大于零下界的边就通过新建超级源点ss和汇点tt解决，即出点多出的连向汇点，入点...

2020-05-09

0 376

字符串模板（后缀数组、后缀自动机、回文树）

再整理一遍板子后缀数组例题cf432D：问对字符串s，对于所有的前缀，当它等于同长度后缀时，这个子串一共在s中出现多少次。后缀数组求lcp是logn，显然直接二分即可。复杂度nlogn 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15...

2020-05-09

0 754

双哈希

和自然溢出法不同的是，这种方法需要取模，并且是两套base mod。每次做哈希操作时，需要两套哈希值都一致，这就大大降低了冲突概率。但是据说常数比较大，并且写起来麻烦一些。 CF1320D 对于一个01串（2e5），给出两种操作：110<->011，可以执行任意多次，q（2e5）...

2020-05-09

0 717

假日赛boss

https://ac.nowcoder.com/acm/contest/4862/E 给n（<=20）头牛，每头牛有自己的身高、重量、承重，要让它们叠罗汉并高度至少是h，并要求剩余的载重量最大（说明最稳），求这个最大剩余载重量。这题初看直接暴搜剪枝，，仔细一想才发现复杂度不对，是20...

2020-05-09

0 450

CF1303E序列自动机+dp

序列自动机其实就是一个数组，记录了每个位置后第一次出现字符c是哪个位置，用于解决一些子序列的问题，它共有n+1个状态，即位置0-n，每个状态都是子序列的接受状态。这个数组在On内完成构建 CF1303E：给字符串s、t问能不能从s中抽取两个不重复的子序列拼接成t。由于长度最大400，考虑枚举两个...

2020-05-09

0 472

时间分治

cdq分治，也叫时间分治，核心概念就是对于若干个操作和查询，维护每次操作在哪个时间段中有效。 https://ac.nowcoder.com/acm/contest/888/E?&headNav=acm 这道题中的size就是时间，我们维护某个size区间上点的连通状况（用并查集维护...

2020-05-09

0 514

思维：线段树dp

https://ac.nowcoder.com/acm/contest/881/I 不得不说这题是真的难，看题解都差点没用理解。）给定平面上若干（1e5）点，每个点ab两个权值，要求将其分为两组，a组的a权值和加b组的b权值和最大，划分条件转化一下就是，不能有a出现在b的右下，也就是要找到...

2020-05-09

0 525