AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

算法提高课整理

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


380


558

<—点个赞吧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~状态机模型(5/5)$

$1.4.1~大盗阿福(状态机\text{DP}~或~线性\text{DP})$
$1.4.2~股票买卖\textrm{IV}(状态机\text{DP})$
$1.4.3~股票买卖\textrm{V}(状态机\text{DP})$
$1.4.4~设计密码(\text{DP+KMP})$
$1.4.5~修复\text{DNA}(\text{DP+AC}自动机)$

$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}之剪枝与优化(2/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.11.1~加成序列(\text{IDDFS})$

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

$3.4.1~牛的旅行(\text{Floyd})$
$3.4.2~排序(\text{Floyd})$
$3.4.3~观光之旅(\text{Floyd})$
$3.4.3~牛站(\text{Floyd})$

$3.5~最小生成树(1/5)$

$3.5.1~最短网络(\text{Kruskal~或~prim})$

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

$5.7~矩阵乘法(1/3)$

$5.7.2~佳佳的斐波那契(矩阵乘法)$

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~超快速排序(归并排序)$

$6.6~\text{RMQ}(1/1)$

$6.6.1~天才的记忆(\text{ST}表)$

39 评论


用户头像
JcWing   2022-10-02 10:22      5    踩      回复

$\% \% \%$


用户头像
wusixuan   2025-05-10 09:23 · 广东      1    踩      回复

%%%


用户头像
Oscar2015   2024-09-23 19:50      1    踩      回复

$mod$$mod$$mod$$mod$$mod$$mod$$mod$$mod$$mod$$mod$$mod$$mod$$mod$$mod$$mod$$mod$$mod$$mod$$mod$$mod$$mod$$mod$$mod$$mod$$mod$$mod$$mod$$mod$$mod$$mod$$mod$$mod$$mod$$mod$$mod$$mod$$mod$$mod$$mod$$mod$$mod$$mod$$mod$$mod$


用户头像
Conan15   2024-08-24 14:33      1    踩      回复

为什么你赞比我多为什么你赞比我多为什么你赞比我多为什么你赞比我多为什么你赞比我多为什么你赞比我多为什么你赞比我多

报名基础课的人不是比提高的人多吗()

用户头像
incra   2024-08-24 17:22      1    踩      回复

因为,我整日宣传(

用户头像
Conan15   2024-08-24 17:30    回复了 incra 的评论         踩      回复

有这时间,帮我宣传下吧 QwQ
最近有在更()

用户头像
incra   2024-08-24 17:42    回复了 Conan15 的评论      1    踩      回复

不是,我在题解里宣传

用户头像
incra   2024-08-24 17:42    回复了 Conan15 的评论      1    踩      回复

现在首页没了,很难有高阅读量/赞

用户头像
Conan15   2024-08-24 17:51    回复了 incra 的评论         踩      回复

你看我基础课的格式啊()我也有题解宣传啊()

用户头像
Conan15   2024-08-24 17:52    回复了 incra 的评论         踩      回复

为什么你的赞和收藏比我高
你这篇帖子明明比我晚出啊()

用户头像
incra   2024-08-25 09:24    回复了 Conan15 的评论         踩      回复

不清楚,因为我当时有一车题解赞比较高(其实写的狗屎)


用户头像
TigerTanWQY   2024-02-07 19:46      1    踩      回复

orz%%%


用户头像
垫底抽风-小号   2023-07-28 21:38      1    踩      回复

$\bmod \bmod \bmod$


用户头像
垫底抽风-小号   2023-07-28 21:37      1    踩      回复

$\bmod$


用户头像
垫底抽风-小号   2023-07-28 21:37      1    踩      回复

\bmod


用户头像
user.banned   2023-07-14 21:59      1    踩      回复

$\mod %\mod$


用户头像
user.banned   2023-07-14 21:59      1    踩      回复

qpzc

%%%


用户头像
AutomaticAC   2024-10-12 19:43         踩      回复

modmodmodmodmodmodmodmodmodmodmodmodmodmodmodmodmodmodmodmodmodmodmodmodmod


用户头像
Zh0uKal1   2024-09-20 16:02         踩      回复

还在更新吗

用户头像
incra   2024-09-23 20:09         踩      回复

楼主摆了,有什么想要我写题解的题可以私信我题解太差了轻喷


用户头像
doreen129   2024-09-03 15:00         踩      回复

不全是吧


用户头像
张耀扬   2024-07-19 15:16         踩      回复

%%%


用户头像
acwing_93338   2024-05-01 12:51         踩      回复

佬怎么404了


用户头像
Asukaズ   2024-03-18 13:48         踩      回复

orz%%%


用户头像
WAsbry   2024-03-16 11:16         踩      回复

or2


用户头像
幻顾   2024-03-06 11:59         踩      回复

已收藏,不吃灰


用户头像
fangsijie   2024-02-12 21:33         踩      回复

storz


用户头像
xxx听取ac声一片   2024-02-01 14:46         踩      回复

感觉会火所以先占一排


App 内打开
你确定删除吗?
1024
x

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