林空鹿饮溪ovo

分类

算法学习笔记(2) 题解(3)

/ 注册

全部文章（共5篇）

《病毒检测》题解（AC自动机）

病毒检测考点：Trie树+BFS 题意：给定一个带通配符的文本串，和若干不带通配符的文本串，求有几个模式串没有出现在文本串中。字符集大小为，文本串长度为，模式串个数为，长度为。通配符有两种，星号可以对应任意多字符，问号能且只能对应一个字符。首先很明显可以转化问题：有几个没有出现等于总数减去出...

算法字符串省选题解 AC自动机数据结构

2019-07-19

1 1257

《特别行动队》题解（斜率优化）

特别行动队考点：斜率优化题意：有个正整数，请分成若干段，每段的总和为，价值为，求最大总价值。。考虑动态规划，表示前个队员产生的最大价值，则显然最终答案为，利用前缀和可以实现求，时间复杂度。考虑到瓶颈主要在于状态转移时，最佳状态无法快速找到，所以尝试斜率优化。观察转移方程：经过展开、...

算法斜率优化题解 APIO DP

2019-07-19

1 859

Nowcoder小白月赛12题解

Nowcoder小白月赛12题解更新：2019.3.11在本文末尾补充了标程链接~ 命题：fzszkl 前言月月和华华是出题人的好朋友，然后他们最近（2019年2月份）互相帮助对方脱单了，出了这套题祝他们幸福。第一题考虑贪心，将所有区间按照左端点排序，从...

算法小白月赛

2019-07-19

1 887

史上最简单的平衡树：无旋Treap

史上最简单的平衡树：无旋Treap 与下文无关的补充说明：本文最早发布在牛客发帖区，链接https://ac.nowcoder.com/discuss/177864 ；最近因为牛客加入了博客功能就搬迁到了我自己的博客，pdf文件中未作修改。还有就是，撰写本文时迷恋英文符号……对于您阅读时产生的恶...

平衡树算法 Treap 无旋Treap fhq_treap 数据结构

2019-07-19

1 902

树上启发式合并实（强）现（上）点分治模板题

点分治？没听说过，还是写一发DSU On Tree（树上启发式合并）好了~ 个人拙见，DSU On Tree主要是解决一些静态的子树信息查询的问题，当然通过一些骚操作可以拓展。拓展到路径最常见的套路就是强制该路径经过当前子树根节点，然后DFS枚举每个点作为根节点。点分治的思想主要是寻找重心作为根节...

树上启发式合并算法数据结构点分治

2019-07-19

1 1403