哥们的算法进阶指南
图论相关
Floyd
- 3512. 最短距离总和 - AcWing题库：这个题就是Floyd的变种，要注意Floyd中不存在负环不然最短距离可能为负无穷。还有在
dp[k][i][j] = min(dp[k-1][i][j],dp[k-1][i][k] + dp[k-1][k][j]的转移公式中，和背包的三维化成二维的思想不一样，背包的是dp[k-1][i]永远不会被更新。但是Floyd中，dp[k-1][i][k]，也就是dp[i][k]可能是dp[k-1][i][k]也可能是dp[k][i][k]。（因为图中不存在负环，所以可以证明：所有最短路中的任意一条每个点只经过一次，因此不管是是dp[k-1][i][k]也可能是dp[k][i][k]都可以保证是最短路，不影响。）
搜索相关
Bfs
Flood Fill
- 3480. 棋盘游戏 - AcWing题库：其实重点就是分析路径中是否有回路，然后记得剪枝。具体看题解，其实是可以有回路得，为了避免
TLE那就限制ans。 - AcWing 1098. 城堡问题 - AcWing：这个题目用的二进制压缩来判断方向。
- AcWing 1106. 山峰和山谷 - AcWing：这个题目主要就是比较了边界里面和外面的情况。
最短路模型
- AcWing 1076. 迷宫问题 - AcWing：和经典最短路模型差别在于，这个题目需要记录一下上一步。
- AcWing 188. 武士风度的牛 - AcWing：就是上下左右四个方向改成了八个方向。
- AcWing 1100. 抓住那头牛 - AcWing：一维数轴上的最短路模型，可以看看，注意边界问题。
多源BFS
- AcWing 173. 矩阵距离 - AcWing：多源最短路问题，在图论中解决这种问题我们一般都是引入一个超级源点，连接超级原点和这些起点，超级原点到起点的距离为0，然后从超级源点开始像所有格子bfs。每个点得到的最短距离就是答案。
最小步数模型
- AcWing 1107. 魔板 - AcWing：这中题目就是外部的最短路模型，我们需要处理每个状态的存储，以及每个状态如何编导下一个状态的。
双端队列广搜
- AcWing 175. 电路维修 - AcWing：这个题目很巧妙，把电路转换成了图的最短路问题，图的边有0有1，每次遍历到0就放对头，1就放队位，保证队列的双端性和单调性。
双向广搜
A*
DFS
连通性模型
- AcWing 1112. 迷宫 - AcWing：注意return和回溯（超时）。
- AcWing 1113. 红与黑 - AcWing：连通快模型不需要回溯。
顺序搜索
- AcWing 1116. 马走日 - AcWing：很简单的
dfs模板。 - AcWing 1117. 单词接龙 - AcWing：可以看一下这个题目，需要注意的是理解题目。
- AcWing 1118. 分成互质组 - AcWing：重点题目，涉及到两个搜索顺序，需要理解一下如何写这种
dfs。
数论相关
质数
- 3497. 质数 - AcWing题库：
- 第100个质数是：541；
- 第500个质数是：3571；
- 第1000个质数是：7919；
- 第10000个质数是：104729；
- 第70000个质数是：882377。
线性代数
- AcWing 532. 货币系统 - AcWing：这个题目用到了线性代数中极大无关组的概念。可以注意下为什么完全背包和01背包优化后第二层循环不一样。
日期相关
- 3498. 日期差值 - AcWing题库：关于日期问题都是有模板的。第一个就是记录平年每月份有多少天的数组。第二个就是判断某一年是不是闰年。第三个就是返回某一年某一月有几天。
dp相关
数字三角形
- 1015. 摘花生 - AcWing题库：这个就是数字三角形。
- 1018. 最低通行费 - AcWing题库：这个题目就是摘花生的变种，主要是题目限制了步数，但是经过分析，可以知道这个限制将题目归类为和摘花生一样的题目。
- AcWing 1027. 方格取数 - AcWing：这个题目就是走两边的摘花生，需要注意的是dp数组的选取，以及优化，和为什么是同时走。
- AcWing 275. 传纸条 - AcWing：如何将这个问题转换成方格取数问题
最长上升子序列
- AcWing 1017. 怪盗基德的滑翔翼 - AcWing：就是最基本的最长上升子序列问题，其中需要注意的是时间复杂度高的时候可以用二分做
- AcWing 1014. 登山 - AcWing：需要掌握一个以i开头的最长下降子序列的求法
- AcWing 482. 合唱队形 - AcWing：和登山一模一样
- AcWing 1012. 友好城市 - AcWing：如何将两岸交叉转换为一边的最长上升子序列问题
- AcWing 1016. 最大上升子序列和 - AcWing：就是板子拉~
- AcWing 1010. 拦截导弹 - AcWing：这个题目其实使用贪心来做的，需要研究一下使用贪心解决最长上升子序列问题和使用贪心解决一个序列中上升序列最小值的相同
- AcWing 896. 最长上升子序列 II - AcWing：这个题目就是同上面的问题差不多，但是g数组存放的内容不一样。需要好好复习。
- AcWing 187. 导弹防御系统 - AcWing：在AcWing 1010. 拦截导弹 - AcWing加上一个暴搜，注意的是时间范围为什么可以过，数据小加上剪枝。
- AcWing 897. 最长公共子序列 - AcWing：dp划分是根据i，j对应两个字母是否相等进行划分的。
- **AcWing 272. 最长公共上升子序列 - AcWing**：这个题目的dp划分是根据AcWing 897. 最长公共子序列 - AcWing和AcWing 895. 最长上升子序列 - AcWing结合进行划分的。其中设计一个优化循环可以看看，不优化过不了。
背包问题
- AcWing 423. 采药 - AcWing：简单的01背包变种，但是需要注意优化的时候二层循环需要反着来，因为
dp[i-1][]]j]变成dp[j]前者没有优化但是后者优化了。需要反着来就是没有优化的结果。 - AcWing 1024. 装箱问题 - AcWing：也是01背包问题，只不过dp值不一样，需要初始化。
- AcWing 1022. 宠物小精灵之收服 - AcWing：这个题目其实就是一个01背包的变体，他的体积可能就是二维的。
- AcWing 278. 数字组合 - AcWing：这个题目其实就是一个01背包。公式是很容易推断的，但是主要就是对于dp数组的初始化需要考虑一下。
- AcWing 1023. 买书 - AcWing：完全背包求方案数。
- AcWing 1021. 货币系统 - AcWing：一样的完全背包求方案数字，需要看下视频注意下为什么回暴int。
- AcWing 532. 货币系统 - AcWing：这个题目用到了线性代数中极大无关组的概念。可以注意下为什么完全背包和01背包优化后第二层循环不一样。
- AcWing 6. 多重背包问题 III - AcWing：这个题目有三种方法，一个是基础版本，一个是二进制优化，一个是单调队列优化。后面两种方法可以过，可以参考下。
- AcWing 8. 二维费用的背包问题 - AcWing：简单的01背包问题的二维费用模板。
- AcWing 1019. 庆功会 - AcWing：多重背包的模板题目。
- AcWing 1020. 潜水员 - AcWing：这个题目值得看一下，将二位费用的dp表示转换了一下，需要考虑0的情况。
- AcWing 12. 背包问题求具体方案 - AcWing：这个题目的字典序很有意思，可以注意一下。
- AcWing 1013. 机器分配 - AcWing：这个题目就是分组背包加上求方案书数的结合，需要注意是什么转换成分组背包的。
- AcWing 426. 开心的金明 - AcWing：很简单的01背包问题。
- AcWing 487. 金明的预算方案 - AcWing：有依赖的背包问题，转化为分组背包很巧妙，而且使用过了二进制优化可以看看。
- AcWing 7. 混合背包问题 - AcWing：01背包，多重背包，完全背包的合体。
- AcWing 10. 有依赖的背包问题 - AcWing：很好的一个思想 使用v来划分dp 然后其实思想是分组背包的思想 dfs相当与循环n 然后玄幻体积 然后根据分组（子树所有体积）更新。
- AcWing 734. 能量石 - AcWing：这个题目考点是贪心+01背包，这个贪心的思想可以看一下。
- AcWing 11. 背包问题求方案数 - AcWing：其实就是加了另一个dp，需要注意的是dp的状态变化可以总结成一个有向无环图。
状态机模型
- AcWing 1049. 大盗阿福 - AcWing：我们正常做是需要依赖前两次的状态的，如果给dp加上两个状态我们可以只依赖上一次的状态。
- AcWing 1057. 股票买卖 IV - AcWing：也是两个状态但是有一个交易限制需要注意，我们把限制加入了dp。并且初始化持有股票必须是无穷大，因为不然我们就会有一个不用买就卖的现象。
- AcWing 1058. 股票买卖 V - AcWing：两个状态已经不满足了，需要三个状态，并且需要明确状态的入口和出口。
- AcWing 1052. 设计密码 - AcWing：根据kmp来的一个状态机，可以看看
状态压缩dp
- AcWing 1064. 小国王 - AcWing：棋盘类状态压缩但是限制了个数
- AcWing 327. 玉米田 - AcWing：针对上题目进行了优化
- AcWing 292. 炮兵阵地 - AcWing：前面两题的升级版，需要用到前两次的状态，重点看下滚动数组如何更新
- AcWing 524. 愤怒的小鸟 - AcWing：集合类的状态压缩，这个题目将抛物线结合，需要看下证明。
区间dp
- AcWing 1068. 环形石子合并 - AcWing：主要就是如何破环成链，需要注意一下dp循环的i，j取值。
- AcWing 320. 能量项链 - AcWing：如何简化a数组。
- AcWing 1069. 凸多边形的划分 - AcWing：这个题目的dp很难想。
- AcWing 479. 加分二叉树 - AcWing：注意左右子树为空情况下的处理，先序遍历就是遍历每次选择的根节点，这个题目包含了一个区间dp存储记录。
- AcWing 1222. 密码脱落 - AcWing
树形dp
- AcWing 1072. 树的最长路径 - AcWing：模板题，树的直径。
- AcWing 1073. 树的中心 - AcWing：换根dp。
- AcWing 1075. 数字转换 - AcWing：如何将数字转换 转换成 树结构。
- AcWing 1074. 二叉苹果树 - AcWing：树的遍历就是第一层dp循环。
- AcWing 323. 战略游戏 - AcWing：这个题目等同AcWing 285. 没有上司的舞会 - AcWing，只不过就是求一个最小值，有意义的是看下如果需要格式化输入如何输入。
数位dp
- AcWing 1081. 度的数量 - AcWing
- AcWing 1082. 数字游戏 - AcWing
- AcWing 1083. Windy数 - AcWing
- AcWing 1085. 不要62 - AcWing
单调队列优化dp
*
斜率优化dp
*
高级数据结构
并查集
- AcWing 1250. 格子游戏 - AcWing：转换一下思路，我们将每个点的二维描述，映射成唯一的一维映射。
- AcWing 1252. 搭配购买 - AcWing：并查集加上01背包。
线段树
- AcWing 1275. 最大数 - AcWing
- AcWing 245. 你能回答这些问题吗 - AcWing：这里需要设计一下线段树结构Node内容，考虑到涉及到连续子区间如何更新。
- AcWing 246. 区间最大公约数 - AcWing：有一个数论知识，
gcd(a_1 , a_2 , ... , a_n) = gcd(a_1 , a_2 - a_1 , ... , a_n - a_n-1) - AcWing 243. 一个简单的整数问题2 - AcWing：区间查询区间修改的方法，也就是懒标记怎么使用。
- AcWing 247. 亚特兰蒂斯 - AcWing：扫描线的使用，注意这个题特殊性太强了。
- AcWing 1277. 维护序列 - AcWing：这个题目就是难一点的懒标记，考虑了懒标记的更新问题，如何定义多个懒标记以及如何规定多个懒标记的更新。
破环成链相关
- AcWing 5183. 好三元组 - AcWing：这个题目最主要的就是如果圆心不在三角形中间，那么就是三个点之间与圆心夹角只和小于180。换句话说也就是三个点在180°里面也就是数组距离小于c/2。
周赛不会题目汇总
- 第114场周赛（acwing）：AcWing 5058. 双色球 - AcWing：这个题目是一个dp问题，但是递推式其实很简单，不是数论问题直接算出来。需要注意代码的写法以及边界。
- 第115场周赛（acwing）：AcWing 5133. 奶牛排队 - AcWing：这个题目是个思维题，主要是需要一个奇数链和偶数链一起来推到整个数组，需要确定第一个数字。
- 第 133 场周赛（acwing）：AcWing 5370. 最小和 - AcWing：利用贪心算法，主要是题目求解可以化简，这个没想到。
- 第 133 场周赛（acwing）：AcWing 5371. 素数整除 - AcWing：埃式筛法和前缀和。
每日一题汇总
- 秋季每日一题汇总：
- AcWing 5166. 对称山脉 - AcWing：这个题目是dp做出来的，
dp[i][j]的含义已经想出来了，就是推导式差点想出来。 - AcWing 5170. 二进制 - AcWing：这个题目其实前面k个二进制决定了整个长度的总数，这个规律很好找。但是就是如何根据判断给定K-
子串数字和序列找到对应的前面k个二进制的数目。可以参考题解。 - AcWing 5164. 所有三角形 - AcWing：这个题目使用dfs不好判断其实就是一个简单的模拟题。我们只需要考虑上下，左右其中的一个方向，也就是我们可以只考虑上和左两个方向。只要这两个方向有黑色，那就-2.这样可以保证不重复。
- AcWing 5183. 好三元组 - AcWing：这个题目最主要的就是如果圆心不在三角形中间，那么就是三个点之间与圆心夹角只和小于180。换句话说也就是三个点在180°里面也就是数组距离小于c/2。
- AcWing 5179. 分组 - AcWing：Integer之间相比用equals方法不然会错
- AcWing 5180. 正方形泳池 - AcWing：这个题目好好看看。思路就是遍历横轴和纵轴，就会满足情况。
- AcWing 5198. 整理书籍 - AcWing：这个题目不能用逆序对做，如果交换是相邻的字母交换才可以用逆序对做。
- AcWing 5166. 对称山脉 - AcWing：这个题目是dp做出来的，
评论