何事秋。

分类

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

数据结构优化dp：

写在前面：一般的，只要决策的候选集合只扩大，不缩小，我们就可以仅用一个变量维护最值，不断与新加入候选集合的元素比较，即可直接得到最优决策，O（1）的进行转移。在更加复杂的情况下，我们就要用更加高级的数据结构，而不仅仅是一个变量维护dp的决策候选集合，以便快速执行插入元素，删除元素，查询最值等操作...

2020-09-04

0 575

计数类dp：

写在前面：这一类dp特别要求不重不漏。统计对象的可能情况一般比较多，通常需要精确的划分和整体性计算。因此，使用动态规划抽象出问题中的子结构和推导的阶段，将有助于我们准确而高效的进行求解。在求解计数类动态规划的问题时，通常要找到一个基准点，围绕这个基准点构造一个不可划分的整体，以避免子问题之间的...

2020-09-04

0 642

倍增优化dp：

写在前面：用倍增优化的动态规划算法求解问题时，一般分为两部分，第一部分是预处理，用阶段成倍增长的DP，计算出若干与2的整数次幂相关的代表状态。第二部分是拼凑，基于二进制拆分思想，用上一部分得到的代表状态组合成最终答案。一、P1081 开车旅行：题目描述小 A 和小 B 决定利用假期外出旅行...

2020-09-04

0 695

单调队列优化dp：

用数组模拟队列速度会更快一点。一、Fence POJ - 1821: A team of k (1 <= K <= 100) workers should paint a fence which contains N (1 <= N <= 16 000) planks n...

2020-09-04

0 428

斜率优化dp：

一、任务安排1：有 N 个任务排成一个序列在一台机器上等待执行，它们的顺序不得改变。机器会把这 N 个任务分成若干批，每一批包含连续的若干个任务。从时刻0开始，任务被分批加工，执行第 i 个任务所需的时间是 Ti。另外，在每批任务开始前，机器需要 S 的启动时间，故执行一批任务所需的时...

2020-09-04

0 612

概率/期望dp：

一、Acwing 217. 绿豆蛙的归宿：给出一个有向无环的连通图，起点为1，终点为N，每条边都有一个长度。数据保证从起点出发能够到达图中所有的点，图中所有的点也都能够到达终点。绿豆蛙从起点出发，走向终点。到达每一个顶点时，如果有K条离开该点的道路，绿豆蛙可以选择任意一条道路离开该点，...

2020-09-04

0 397

划分树：

话说这个东西大概要退出历史的舞台了吧。。。专用功能，静态查询区间第k大，主席树完全可以搞定啊，还能搞点别的。不过思想还是要学一下的。以下转自：https://blog.csdn.net/Akatsuki__Itachi/article/details/80030929 有这样一类题目，求的是区...

2020-09-04

0 548

分块：

分块大法好：具体应用见例题。一、A Simple Problem with Integers POJ - 3468： You have N integers, A1, A2, … , AN. You need to deal with two kinds of operations. One ...

2020-09-04

0 395

线段树动态开点：

貌似权值线段树动态开点用的比较多。例题： I Hate It HDU - 1754 很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。这让很多学生很反感。不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更...

2020-09-04

0 474

权值线段树：

维护当前节点代表值出现的次数。题目描述您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作： 1。插入x数 2。删除x数(若有多个相同的数，因只删除一个) 3。查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数，因输出最小的排名) 4。查询排名为x的数...

2020-09-04

0 595