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篇）

长链剖分优化树上dp

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

2020-05-09

0 642

上下界网络流 cf704D

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

2020-05-09

0 437

上下界网络流

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 753

双哈希

和自然溢出法不同的是，这种方法需要取模，并且是两套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

牛客多校 E Explorer（时间分治+可持久性并查集）

题目 cdq分治，也叫时间分治，核心概念就是对于若干个操作和查询，维护每次操作在哪个时间段中有效。这道题中的size就是时间，我们维护某个size区间上点的连通状况（用并查集维护），进行查询时进入某个点则连上这个点上的边，退出它时把并查集再复原。 #include<bits/stdc...

2020-05-09

0 508

使用freopen重定向输入流后cin出现问题的解决方案

写作业代码需要读文件，图方便直接用了freopen重定向输入流，可是后面发现还要切换回控制台输入。于是查资料。发现大多博客都介绍用freopen("CON", "r", stdin); 这句来改回去，可是实际测试中发现使用了之后scanf是正常读入了，ci...

2020-05-09

0 526