<—点个赞吧QwQ
<—强烈建议收藏!!!
$\Huge{持续更新ing!!!}$
特别感谢@MildRain的贡献!
1 动态规划
$1.1~数字三角形模型(4/4)$
$1.1.1~摘花生(线性\text{DP})$
$1.1.2~最低通行费用(线性\text{DP})$
$1.1.3~方格取数(线性\text{DP})$
$1.1.4~传纸条(线性\text{DP})$
$1.2~最长上升子序列模型(8/8)$
$1.2.1~怪盗基德的滑翔翼(线性\text{DP})$
$1.2.2~登山(线性\text{DP})$
$1.2.3~合唱队形(线性\text{DP})$
$1.2.4~友好城市(线性\text{DP})$
$1.2.5~最大上升子序列和(线性\text{DP})$
$1.2.6~拦截导弹(线性\text{DP})$
$1.2.7~导弹防御系统(\text{DFS}+线性\text{DP})$
$1.2.8~最长公共上升子序列(线性\text{DP}+前缀和优化)$
$1.3~背包模型(19/19)$
$1.3.1~采药(背包\text{DP})$
$1.3.2~装箱问题(背包\text{DP})$
$1.3.3~宠物小精灵之收服(背包\text{DP})$
$1.3.4~数字组合(背包\text{DP})$
$1.3.5~买书(背包\text{DP})$
$1.3.6~货币系统(一)(背包\text{DP})$
$1.3.7~货币系统(二)(背包\text{DP})$
$1.3.8~多重背包问题\text{III}(背包\text{DP}+单调队列优化)$
$1.3.9~庆功会(背包\text{DP})$
$1.3.10~混合背包问题(背包\text{DP})$
$1.3.11~二维费用的背包问题(背包\text{DP})$
$1.3.12~潜水员(背包\text{DP})$
$1.3.13~机器分配(背包\text{DP})$
$1.3.14~开心的金明(背包\text{DP})$
$1.3.15~有依赖的背包问题(背包\text{DP})$
$1.3.16~背包问题求方案数(背包\text{DP})$
$1.3.17~背包问题求具体方案(背包\text{DP})$
$1.3.18~能量石(背包\text{DP}+贪心)$
$1.3.19~金明的预算方案(背包\text{DP})$
$1.4~状态机模型(3/5)$
$1.4.1~大盗阿福(状态机\text{DP}~或~线性\text{DP})$
$1.4.2~股票买卖\textrm{IV}(状态机\text{DP})$
$1.4.3~股票买卖\textrm{V}(状态机\text{DP})$
$1.5~状态压缩\text{DP}(4/5)$
$1.5.1~小国王(状态压缩\text{DP})$
$1.5.2~玉米田(状态压缩\text{DP})$
$1.5.3~炮兵阵地(状态压缩\text{DP})$
$1.4.4~愤怒的小鸟(状态压缩\text{DP})$
$1.6~区间\text{DP}(4/5)$
$1.6.1~环形石子合并(区间\text{DP})$
$1.6.2~能量项链(区间\text{DP})$
$1.6.3~加分二叉树(区间\text{DP})$
$1.6.4~凸多边形的划分(区间\text{DP})$
$1.7~树形\text{DP}(4/6)$
$1.7.1~树的最长路径(树形\text{DP})$
$1.7.3~数字转换(树形\text{DP})$
$1.7.4~二叉苹果树(背包\text{DP}+树形\text{DP})$
$1.7.5~战略游戏(树形\text{DP}+状态机\text{DP})$
$1.8~数位\text{DP}(0/6)$
$1.9~单调队列优化\text{DP}(1/6)$
$1.9.1~最大子序和(单调队列优化\text{DP})$
2 搜索
$2.1~\text{Flood Fill}(3/3)$
$2.1.1~池塘计数(\text{Flood Fill})$
$2.1.2~城堡问题(\text{Flood Fill})$
$2.1.3~山峰和山谷(\text{Flood Fill})$
$2.2~最短路模型(3/3)$
$2.2.1~迷宫问题(\text{BFS})$
$2.2.2~武士风度的牛(\text{BFS})$
$2.2.3~抓住那头牛(\text{BFS})$
$2.3~多源\text{BFS}(1/1)$
$2.4~最小步数模型(1/1)$
$2.5~双端队列广搜(1/1)$
$2.5.1~电路维修(\text{Dijkstra}或双端队列\text{BFS})$
$2.6~双向广搜(1/1)$
$2.7~\text A^*(2/2)$
$2.7.1~第K短路(\text A^∗+\text{Dijkstra})$
$2.7.2~八数码(\text A^∗)$
$2.8~\text{DFS}之连通性模型(2/2)$
$2.8.1~迷宫(\text{BFS}或\text{DFS})$
$2.8.2~红与黑(\text{BFS}或\text{DFS})$
$2.9~\text{DFS}之搜索顺序(3/3)$
$2.9.1~马走日(\text{DFS})$
$2.9.2~单词接龙(\text{DFS})$
$2.9.3~分成互质组(\text{DFS})$
$2.10~\text{DFS}之剪枝与优化(4/4)$
$2.10.1~小猫爬山(\text{DFS}+剪枝优化)$
$2.10.2~数独(\text{DFS}+剪枝优化)$
$2.10.3~木棒(\text{DFS}+剪枝优化)$
$2.10.4~生日蛋糕(\text{DFS}+剪枝优化)$
$2.11~迭代加深(1/1)$
$2.12~双向\text{DFS}(1/1)$
$2.13~\text{IDA}^*(1/2)$
3 图论
$3.1~单源最短路的建图方式(6/6)$
$3.1.1~热浪(\text{Dijkstra})$
$3.1.2~信使(\text{Floyd})$
$3.1.3~香甜的黄油(\text{Dijkstra})$
$3.1.4~最小花费(\text{Dijkstra})$
$3.1.5~最优乘车(\text{BFS})$
$3.1.6~昂贵的聘礼(\text{SPFA})$
$3.2~单源最短路的综合应用(4/4)$
$3.2.1~新年好(\text{Dijkstra})$
$3.2.2~通信线路(\text{Dijkstra})$
$3.2.3~道路与航线(\text{SPFA})$
$3.2.4~最优贸易(\text{SPFA})$
$3.3~单源最短路的扩展应用(4/4)$
$3.3.1~选择最佳线路(\text{SPFA})$
$3.3.2~拯救大兵瑞恩(状态压缩+\text{BFS})$
$3.3.3~最短路计数(\text{SPFA})$
$3.3.4~观光(\text{Dijkstra})$
$3.4~\text{Floyd}算法(4/4)$
$3.4.1~牛的旅行(\text{Floyd})$
$3.4.2~排序(\text{Floyd})$
$3.4.3~观光之旅(\text{Floyd})$
$3.4.3~牛站(\text{Floyd})$
$3.5~最小生成树(5/5)$
$3.5.1~最短网络(\text{Kruskal 或 prim})$
$3.5.2~局域网(\text{Kruskal})$
$3.5.3~繁忙的都市(\text{Prim})$
$3.5.4~联络员(\text{Kruskal})$
$3.5.5~连接格点(\text{Kruskal})$
$3.6~最小生成树的扩展应用(4/4)$
$3.6.1~新的开始(\text{Prim})$
$3.6.2~北极通讯网络(\text{Kruskal})$
$3.6.3~走廊泼水节(\text{Kruskal})$
$3.6.4~秘密的牛奶运输(\text{Kruskal}+倍增,和3.9.3完全一样)$
$3.7~负环(2/3)$
$3.7.1~虫洞(\text{SPFA})$
$3.7.2~观光奶牛(\text{SPFA}+二分查找)$
$3.8~差分约束(1/4)$
$3.9~最近公共祖先(4/4)$
$3.9.1~祖孙询问(倍增)$
$3.9.2~距离(倍增)$
$3.9.3~次小生成树(\text{Kruskal}+倍增)$
$3.9.4~闇の連鎖(倍增+树上差分)$
$3.10~有向图的强连通分量$
$3.11~无向图的双连通分量$
$3.12~二分图(5/5)$
1为二分图判断,并隐含二分查找
$3.12.1~关押罪犯(染色法+二分查找)$
其余为匹配
先用难度较低的EK算法引出
$3.12.2~机器任务(\text{EK})$
$3.12.3~捉迷藏(\text{Floyd+EK})$
再用难度较高的Dinic算法优化
$3.12.4~棋盘覆盖(\text{Dinic})$
$3.12.5~骑士放置(\text{Dinic})$
另外对于评论区中有人提到的ISAP算法,MildRain单独写了一条分享介绍
$3.13~欧拉回路和欧拉路径(1/4)$
$3.14~拓扑排序(2/4)$
$3.14.1~家谱树(拓扑排序)$
$3.14.2~奖金(差分约束或拓扑排序)$
4 高级数据结构
$4.1~并查集(5/5)$
本部分的顺序稍作了改变,遵循了先连续后离散,先明确后模糊,先不带权后带权,先直接应用后与其他思想结合的规律
$4.1.1~格子游戏(并查集)$
$4.1.2~程序自动分析(并查集+哈希表)$
$4.1.3~搭配购买(并查集+01背包)$
$4.1.4~银河英雄传说(带权并查集)$
$4.1.5~奇偶游戏(带权并查集+哈希表)$
$4.2~树状数组(4/4)$
先模板后应用,先单纯应用后与其他方法结合,并且先和线段树对比再坚持使用
$4.2.1~一个简单的整数问题(树状数组或线段树)$
$4.2.2~一个简单的整数问题2(树状数组或线段树)$
$4.2.3~楼兰图腾(树状数组)$
$4.2.4~谜一样的牛(树状数组+二分查找)$
$4.3~线段树(6/6)$
1、2、3为传统线段树,用来熟悉偏移量(懒标记)的使用方法
$4.3.1~最大数(线段树)$
$4.3.2~一个简单的整数问题2(线段树)$
$4.3.3~维护序列(线段树)$
4是与dp的结合,5是比较另类的应用,有相似的小技巧
$4.3.4~你能回答这些问题吗(线段树)$
$4.3.5~区间最大公约数(线段树)$
6是衍生出的扫描线算法,本身就具有很大难度
$4.3.6~亚特兰蒂斯(线段树+离散化)$
$4.4~可持久化数据结构(2/2)$
$4.4.1~最大异或和(可持久化\text{trie}树)$
$4.4.2~第K小数(主席树)$
$4.5~平衡树(2/2)$
$4.5.1~普通平衡树(\text{Treap})$
$4.5.2~营业额统计(\text{Treap})$
$4.6~\text{AC}自动机(2/2)$
$4.6.1~搜索关键词(\text{AC}自动机)$
$4.6.2~单词(\text{AC}自动机+拓扑排序)$
5 数学知识
$5.1~筛质数(3/3)$
$5.1.1~哥德巴赫猜想(线性筛)$
$5.1.2~夏洛克和他的女朋友(筛质数)$
$5.1.3~质数距离(筛质数)$
$5.2~分解质因数(1/1)$
$5.3~快速幂(2/2)$
$5.3.1~序列的第k个数(快速幂)$
$5.3.2~越狱(快速幂)$
$5.4~约数个数(1/4)$
$5.4.1~轻拍牛头(倍数)$
$5.4.2~樱花(线性筛+分解质因数+推式子)$
$5.4.3~反素数(\text{DFS})$
$\% \% \%$
orz%%%
$\bmod \bmod \bmod$
$\bmod$
\bmod
$\mod %\mod$
qpzc
%%%
orz%%%
or2
已收藏,不吃灰
storz
感觉会火所以先占一排
%%%
%%%
Orz
%%%
能不能先把4.4写掉?(因为我不太明白)
可以啊
已修改
好嘞~
跟我一起写最小圆覆盖吗(区间查询加单点修改)
我真的不会!!!Orz