何事秋。

分类

AC自动机(4) bfs/dfs(5) bitset(3) CF刷题(23) dp一般看规律(11) dp基本算法(12) KMP(2) LCA(1) LCT(4) Prufer(2) SAM(3) STL(1) tarjan(1) 主席树/线段树(14) 二分/三分(2) 二分图(1) 位运算(1) 偏序问题(2) 分块(1) 分治/点分治/边分治(2) 单调栈(2) 单调队列(1) 博弈/sg(3) 博弈论基本算法(11) 后缀数组(1) 启发式合并(1) 哈希(4) 回文自动机(2) 图论一顿套模板(3) 图论基本算法(31) 基本算法(2) 多项式(1) 套题(1) 字典树(1) 字符串基本算法(27) 容斥(1) 平衡树/堆(2) 并查集(3) 序列自动机(1) 快速幂/矩阵快速幂(1) 思维只会A+B(5) 投稿(2) 拓扑序(1) 数位dp(1) 数学不好先打表(4) 数据结构基本算法(69) 数据结构瞎乱写(8) 数论分块(1) 数论只会gcd(20) 数论基本算法(64) 暴力(1) 最短路(3) 期望/概率(1) 期望dp/概率dp(1) 构造(3) 枚举(3) 树形dp(3) 树链剖分(5) 模拟只会猜题意(5) 生成树(1) 签到题(2) 线性dp(12) 线性基(2) 组合数学(1) 组合数学靠运气(2) 结论题(2) 网络流/费用流(5) 网络流基本算法(5) 群论(2) 背包dp(1) 莫比乌斯反演(1) 莫队(1) 虚树(1) 计数类dp(1) 计算几何(8) 计算几何基本算法(15) 贪心刚好过样例(3) 随机化算法(2)

/ 注册

全部文章（共461篇）

曼哈顿最小生成树：

Object Clustering POJ - 3241 We have N (N ≤ 10000) objects, and wish to classify them into several groups by judgement of their resemblance. To simply...

2020-09-04

0 358

最大团问题：

无向图的最大团等于其补图的最大独立集无向图的最大独立集等于其补图的最大团。一、Maximum Clique HDU - 1530 ： Given a graph G(V, E), a clique is a sub-graph g(v, e), so that for all vertex pa...

2020-09-04

0 872

树上分治：

一、点分治。题目① Tree POJ - 1741： Give a tree with n vertices,each edge has a length(positive integer less than 1001). Define dist(u,v)=The min distance bet...

2020-09-04

0 370

树链剖分：

这真是个神奇的东西。一、模板例题： P3384 【模板】树链剖分：题目描述如题，已知一棵包含N个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：操作1：格式： 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z 操作2：格式： 2 x y 表示求树从...

2020-09-04

0 577

最近公共祖先lca（2）：

之前学习过一次lca，是用暴力，倍增，tarjan离线处理的。之前就知道lca还有其他两种写法，不过那个时候还不会树剖，就没学。今天学习树剖之后，发现lca树剖写法不就是个裸的树剖吗。预处理 O（n）查询logn 比倍增还优秀一点。今天就补上没学的那两种lca的写法了。 P3379 【模...

2020-09-04

0 594

单调队列：

O（n）一、ACwing 输入一个长度为n的整数序列，从中找出一段长度不超过m的连续子序列，使得子序列中所有数的和最大。输入格式第一行输入两个整数n,m。第二行输入n个数，代表长度为n的整数序列。同一行数之间用空格隔开。输出格式输出一个整数，代表该序列的最大子序和。数据范围...

2020-09-04

0 414

RMQ：

一、一维RMQ：前两天学lca的时候学了这个东西，今天再来系统的学一下。 P3865 【模板】ST表：题目背景这是一道ST表经典题——静态区间最大值请注意最大数据时限只有0.8s，数据强度不低，请务必保证你的每次查询复杂度为 O(1) 题目描述给定一个长度为 N 的数列，和 M 次询问...

2020-09-04

0 300

哈夫曼树，哈夫曼编码：

一、哈夫曼树： ①、 P1090 合并果子：题目描述在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 n-1次合并之后，就只剩下...

2020-09-04

0 480

环形结构上的动态规划问题的两种基本处理方式：

一、执行两次DP，第一次在任意位置把环断开成链，按照线性问题求解。第二次通过适当的条件和赋值，保证计算的状态等价于把断开的位置强制相连。 Naptime POJ - 2228： Goneril is a very sleep-deprived cow. Her day is partitione...

2020-09-04

0 981

有后效性的状态转移方程：

一、实际上无后效性是动态规划算法的前提之一，然后有些题，我们设计出状态表示和状态转移方程之后才发现，其似乎不满足无后效性这一特点。以以下期望dp为例，在很多的题目中，动态规划的状态转移分阶段带环，我们需要把dp和高斯消元相结合，在整体层面采用动态规划框架，在局部使用高斯消元解出互相影...

2020-09-04

0 765