AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 应用
  • 其它
    • 题解
    • 分享
    • 商店
    • 问答
  • 吐槽
  • 登录/注册

$$\Huge\color{blue}{算法提高课整理}$$

作者: 作者的头像   incra ,  2022-09-21 18:11:21 ,  所有人可见 ,  阅读 2128


85


95

<—点个赞吧QwQ




<—强烈建议收藏!!!

$\Huge{持续更新ing!!!}$

感谢Ethanyyc帮我写的设计密码

$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$ 状态机模型$(4/5)$

$1.4.1$ 大盗阿福(状态机$\text{DP}$$~$或$~$线性$\text{DP}$)
$1.4.2$ 股票买卖$\textrm{IV}$(状态机$\text{DP}$)
$1.4.3$ 股票买卖$\textrm{V}$(状态机$\text{DP}$)
Ethanyyc帮我写的设计密码

$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}$$(3/6)$

$1.7.1$ 树的最长路径(树形$\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.3.1$ 矩阵距离(多源$\text{BFS}$)

$2.4$ 最小步数模型$(1/1)$

$2.4.1$ 魔板($\text{BFS}$)

$2.5$ 双端队列广搜$(1/1)$

$2.5.1$ 电路维修(双端队列$\text{BFS}$)

$2.6$ 双向广搜$(1/1)$

$2.6.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}$之剪枝与优化$(1/4)$

$2.10.1$ 小猫爬山($\text{DFS}$$+$剪枝优化)
$2.10.3$ 木棒($\text{DFS}+$剪枝优化)

$2.11$ 迭代加深$(1/1)$

$2.11.1$ 加成序列(迭代加深)

$2.12$ 双向$\text{DFS}$$(0/1)$

$2.13$ $\text{IDA}^*$$(1/2)$

$2.13.1$ 排书($\text{IDA}^∗$)

$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}$算法$(2/4)$

$3.4.1$ 牛的旅行($\text{Floyd}$)
$3.4.2$ 排序($\text{Floyd}$)

$3.5$ 最小生成树

$3.6$ 最小生成树的扩展应用

$3.7$ 负环

$3.8$ 差分约束

$3.9$ 最近公共祖先

$3.10$ 有向图的强连通分量

$3.11$ 无向图的双连通分量

$3.12$ 二分图

$3.13$ 欧拉回路和欧拉路径$(1/4)$

$3.13.1$ 铲雪车(欧拉回路)

$3.14$ 拓扑排序$(1/4)$

$3.15.1$ 家谱树(拓扑排序)

$4$ 高级数据结构

$4.1$ 并查集$(5/5)$

$4.1.1$ 格子游戏(并查集)
$4.1.2$ 搭配购买(并查集)
$4.1.3$ 程序自动分析(离散化$+$并查集)
$4.1.4$ 奇偶游戏(离散化$+$带权并查集)
$4.1.5$ 银河英雄传说(带权并查集)

$4.2$ 树状数组$(0/4)$

$4.3$ 线段树$(5/6)$

$4.3.1$ 最大数(线段树)
$4.3.2$ 你能回答这些问题吗(线段树)
$4.3.3$ 区间最大公约数(线段树)
$4.3.4$ 一个简单的整数问题$2$(线段树)
$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}$)

$5$ 数学知识

$5.1$ 筛质数$(3/3)$

$5.1.1$ 哥德巴赫猜想(线性筛)
$5.1.2$ 夏洛克和他的女朋友(筛质数)
$5.1.3$ 质数距离(筛质数)

$5.2$ 分解质因数$(1/1)$

$5.2.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}$)

$6$ 基础算法

$6.1$ 位运算$(1/1)$

$6.1.1$ $64$位乘法(位运算)

$6.2$ 前缀和与差分$(1/2)$

$6.2.1$ 激光炸弹(前缀和)

$6.4$ 二分$(1/2)$

$6.4.1$ 最佳牛围栏(二分)

$6.5$ 排序$(1/3)$

$6.5.3$ 超快速排序(归并排序)

7 评论


用户头像
JcWing   4个月前      3    踩      回复

$\% \% \%$


用户头像
liaoyanxu   1个月前         踩      回复

能不能先把4.4写掉?(因为我不太明白)

用户头像
incra   1个月前         踩      回复

可以啊

用户头像
incra   1个月前         踩      回复

已修改

用户头像
liaoyanxu   1个月前    回复了 incra 的评论         踩      回复

好嘞~


用户头像
封禁用户   4个月前         踩      回复

跟我一起写最小圆覆盖吗(区间查询加单点修改)

用户头像
incra   4个月前         踩      回复

我真的不会!!!


你确定删除吗?
1024
x

© 2018-2023 AcWing 版权所有  |  京ICP备17053197号-1
用户协议  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息