力扣博文链接2_力扣1762

目录

栈

堆

dfs

kmp

宽搜

模拟

枚举

递推

数学

差分

归并

找环

环图

构造

贪心

RMQ

找规律

高精度

哈希表

双指针

子序列

全排列

位运算

前缀和

离散化

单调栈

线段树

二进制

基环树

二分图

并查集

思维题

树形dp

区间dp

区间合并

分类讨论

破环成链

二分查找

树状数组

背包问题

拓扑排序

前缀最值

状态压缩

floyd算法

状态机dp

字符串哈希

最小生成树

蓝桥杯真题

单源最短路径

最近公共祖先

---

栈

4207 最长合法括号子序列（栈）

4198 最长合法括号子串（栈）

2197 替换数组中的非互质数（栈）

堆

4072 习题册（堆-使用标记数组实现延迟删除）

2208 将数组和减半的最少操作次数（堆）

dfs

2060 奶牛选美（dfs-bfs）

2005 马蹄铁（dfs）

1875 贝茜的报复（dfs、二进制）

3802 消灭数组（dfs）

4310 树的DFS（dfs序列）

4213 最小结果（dfs）

4004 传送阵（枚举 + dfs）

3990 砍树（贪心 + dfs）

3796 凑平方（dfs）

6029 射箭比赛中的最大得分（dfs、零一背包问题求解具体方案）

3734 求和（dfs + 求解两个区间的交集）

3695 扩充序列（dfs）

记忆化搜索

3828 行走路径（记忆化搜索 + 找环）

kmp

3823 寻找字符串（kmp）

宽搜

2019 拖拉机（双端队列广搜）

4300 两种操作（宽搜）

3797 最大化最短路（bfs + 贪心）

模拟

2120 执行所有后缀指令（模拟）

2164 对奇偶下标分别排序（模拟）

2165 重排数字的最小值（模拟）

1726 挤奶顺序（分类讨论、模拟）

2180 统计各位数字之和为偶数的整数个数（模拟）

3769 移动石子（模拟）

3781 乘车问题（模拟）

3790 录入单词（模拟）

3791 解码（模拟）

3793 最大分数（模拟）

3798 幸运年份（模拟）

4215 处理字符串（模拟）

4212 字符串比较（模拟）

4209 三元组（模拟）

4206 判断数字（模拟）

4197 吃苹果（模拟）

4079 数字串（模拟）

4076 字符串权值（模拟）

4073 找规律输出（模拟）

4070 异或（模拟）

4003 完全平方数（模拟）

3998 变成1（模拟 + 高精度）

3997 整数幂（模拟）

3991 满足条件的01串（模拟）

3971 最小的商（模拟）

3955 统一大小写（模拟）

3826 青蛙跳（模拟）

3822 食堂排队（模拟）

3821 区间选数（模拟）

3733 去掉一个元素（模拟）

3726 调整数组（模拟）

3660 最短时间（模拟）

2181 合并零之间的节点（模拟）

2221 数组的三角和（模拟）

2224 转化时间需要的最少操作数（模拟）

2169 得到 0 的操作数（模拟）

2161 根据给定数字划分数组（模拟、双指针）

2154 将找到的值乘以 2（模拟、哈希表）

4400 玩游戏（约瑟夫环、模拟）

4410 吃鸡蛋（模拟）

4425 改变数字（模拟）

枚举

2119 反转两次的数字

4201 01数（python3 枚举）

2122 还原原数组（枚举，双指针）

2114 句子中的最多单词数（枚举）

2058 笨拙的手指（暴力枚举）

1969 品种邻近（枚举 + 滑动窗口）

1945 奶牛棒球（枚举 + 双指针）

1922 懒惰的牛（枚举 + 双指针）

1913 公平摄影（枚举 + 前缀和 + 哈希表）

1855 愤怒的奶牛（思维题、枚举）

1843 圆形牛棚（枚举）

1826 农田缩减（枚举）

1813 方块游戏（枚举）

1801 蹄子剪刀布（枚举）

1789 牛为什么过马路 II（枚举）

1750 救生员（枚举 + 区间合并、线段树）

1684 大型植被恢复（枚举）

1443 拍照（枚举 + 推公式）

3347 菊花链（暴力枚举、哈希表）

3774 亮灯时长（枚举 + 贪心 + 前缀和）

3785 战舰（枚举）

3792 质数问题（枚举 + 线性筛）

3808 画正方形（思维题、枚举）

3809 修改数组（枚举、贪心）

4302 元素分类（枚举）

4304 字符串归类（枚举技巧 + 并查集）

4299 删点（枚举）

4301 截断数列（枚举）

4308 组合字符串（暴力枚举、贪心）

4296 合适数对（暴力枚举）

4214 三元组（枚举技巧、树状数组维护最值）

4201 01数（二进制枚举）

4083 最大公约数（枚举技巧）

4082 子序列（暴力枚举）

4077 k显性字符（枚举技巧）

4071 国际象棋（枚举）

4004 传送阵（枚举 + dfs）

3956 截断数组（枚举 + 前缀和）

3957 子序列（思维题、枚举 + 前缀最值）

3812 机器人走迷宫（枚举 + 全排列）

3813 最大路径权值（枚举 + 拓扑排序 + 递推）

3789 隐藏字符串（枚举 + 递推）

3759 第k个字符串（枚举）

2195 向数组中追加 K 个整数（枚举）

3661 重置数列（枚举 + 贪心）

3626 三元一次方程（枚举）

2171 拿出最少数目的魔法豆（枚举 + 前缀和）

2176 统计数组中相等且可以被整除的数对（暴力枚举）

4314 三元组（暴力枚举）

4377 农田灌溉（枚举）

60 排列序列（枚举--第 k 个全排列模板）

4398 查询字符串（暴力 + 哈希表）

4401 找回数组（差分、枚举）

4417 选区间（贪心 + 枚举）

4416 缺少的数

85 最大矩形（优化暴力）

4423 最近距离（枚举）

4426 整除子串（枚举 + 数论）

递推

dp本质上是暴力枚举的优化，一个状态表示的其实是一类方案方案的集合，核心是状态表示和状态计算，状态表示一般是结合题目给出的变量和需要求解的是什么确定需要声明多少维的数组，状态计算一般是找最后一个不同点。

1884 COW（递推、状态机dp）

1762 牛的洗牌（递推）

3777 砖块（递推）

4078 01串（前缀和 + dp）

3813 最大路径权值（枚举 + 拓扑排序 + 递推）

3789 隐藏字符串（枚举 + 递推）

2207 字符串中最多数目的子字符串（递推）

2209 用地毯覆盖后的最少白色砖块（递推）

3662 最大上升子序列和（dp + 树状数组优化）

2188 完成比赛的最少时间（递推）

2222 选择建筑的方案数（递推、找规律）

4378 选取数对（递推）

4418 选元素（递推）

数学

3491 完全平方数（试除法分解质因数）

1471 牛奶工厂（floyd求解传递闭包、证明）

1443 拍照（枚举 + 推公式）

3782 点（推公式）

3783 第 k 个除数（试除法求解约数）

3792 质数问题（枚举 + 线性筛）

3799 送糖果

3800 奇数还是偶数（同余）

2183 统计可以被 K 整除的下标对数目（数学、哈希表）

4210 数字（进制转化）

4200 简单问题（推公式）

4199 公约数（求解约数 + 最大公约数 + 二分）

4194 Pow（快速幂）

3994 水果派（向上取整转为向下取整）

3992 树上有猴（二分、求解区间交集）

3827 最小正整数（最小公倍数）

3795 计算abc（解方程）

3787 整除（向上取整）

4315 两个数列（区间相交）

4319 合适数对（数论--算数基本定理，线性筛求解最小质数）

4424 等式（一元二次方程）

4426 整除子串（枚举 + 数论）

欧拉函数

3999 最大公约数（欧拉函数值）

组合计数问题

4002 构造数组（可重复组合数问题--隔板法）

3972 方格集数量（组合计数）

差分

2041 干草堆（差分）

1987 粉刷栅栏（差分）

1952 金发姑娘和 N 头牛（差分 + 离散化--两种离散化方式）

1715 桶列表（差分）

4195 线段覆盖（差分）

4401 找回数组（差分、枚举）

归并

对于k路归并的模型其实考察的还是比较隐晦的，需要一步步分析其中的过程，最终发现有一个特点是需要总共n个有序序列中找到前k大或者前k小的值。

1934 贝茜放慢脚步（二路归并）

3995 最小的和（多路归并）

找环

判断图中是否存在环的方法

1960 闪烁（状态压缩、找环）

3828 行走路径（记忆化搜索 + 找环）

3579 数字移动（环图、找环、并查集）

环图

1929 镜子田地（环图、位运算）

3775 数组补全（环图）

3579 数字移动（环图、找环、并查集）

构造

1696 困牛排序（思维题、构造）

3762 二进制矩阵（思维题、构造）

3794 构造字符串（构造）

3807 构造字符串（构造）

4211 序列重排（构造、思维题--双关键字排序）

4204 构造矩阵（构造）

3811 排列（构造）

3778 平衡数组（思维题、构造）

4318 最短路径（构造）

贪心

1672 疯狂的科学家（贪心）

1660 社交距离 II（贪心 + 双指针求解连续相等的区间）

3764 三元数异或（贪心）

3767 最小的值（贪心）

3773 兔子跳（贪心）

3774 亮灯时长（枚举 + 贪心 + 前缀和）

3776 水果拼盘（贪心）

4306 序列处理（贪心）

3806 最小化字符串（贪心）

4307 数字重构（贪心）

3809 修改数组（枚举、贪心）

4308 组合字符串（暴力枚举、贪心）

4298 搭档（二分图的最大匹配、贪心）

5227 K 次操作后最大化顶端元素（贪心）

3993 石子游戏（贪心 + 前缀和）

3990 砍树（贪心 + dfs）

3797 最大化最短路（bfs + 贪心）

3661 重置数列（枚举 + 贪心）

3627 最大差值（贪心）

2193 得到回文串的最少操作次数（贪心）

2182 构造限制重复的字符串（贪心 + 哈希表）

2170 使数组变成交替数组的最少操作数（贪心、哈希表）

2178 拆分成最多数目的正偶数之和（贪心）

4380 合并石子（贪心）

4397 卡牌（贪心）

4414 子序列（分类讨论、贪心）

4417 选区间（贪心 + 枚举）

4421 信号（贪心）

4427 树中节点和（贪心）

RMQ

2104 子数组范围和（ST表求解区间最值）

找规律

找规律有一个比较牛的网站，这个网站可以输入对应的数字可以得到对应的通项公式：OEIS

4000 排位（找规律）

3989 看图做题（找规律）

2222 选择建筑的方案数（递推、找规律）

4411 三仙归洞（找规律-周期）

高精度

3998 变成1（模拟 + 高精度）

哈希表

2103 环和杆（哈希表）

2121 相同元素的间隔之和（哈希表）

1913 公平摄影（枚举 + 前缀和 + 哈希表）

1776 牛的基因组学（判断两个集合是否存在交集--哈希表）

3347 菊花链（暴力枚举、哈希表）

3761 唯一最小数（哈希表）

4303 链表（哈希表记录起点与终点）

4309 消灭老鼠（哈希表存储一个向量表示一条直线）

2183 统计可以被 K 整除的下标对数目（数学、哈希表）

4208 电话号码（哈希表）

3988 不同的数（哈希表）

3803 数组去重（哈希表）

3779 相等的和（哈希表）

3771 选取石子（哈希表）

3770 最小消耗（哈希表）

2201 统计可以提取的工件（哈希表）

2191 将杂乱无章的数字排序（哈希表）

3577 选择数字（哈希表）

2186 使两字符串互为字母异位词的最少步骤数（哈希表）

2182 构造限制重复的字符串（贪心 + 哈希表）

2225 找出输掉零场或一场比赛的玩家（哈希表）

2170 使数组变成交替数组的最少操作数（贪心、哈希表）

2154 将找到的值乘以 2（模拟、哈希表）

4317 不同正整数的个数（哈希表）

4394 最长连续子序列（滑动窗口 + 哈希表）

4398 查询字符串（暴力 + 哈希表）

双指针

2105 给植物浇水 II（双指针）

2122 还原原数组（枚举，双指针）

1969 品种邻近（枚举 + 滑动窗口）

1945 奶牛棒球（枚举 + 双指针）

1922 懒惰的牛（枚举 + 双指针）

1660 社交距离 II（贪心 + 双指针求解连续相等的区间）

3768 字符串删减（双指针）

4203 寻找子串（双指针）

15 三数之和（三指针）

3973 无线网络（二分 + 双指针）

2161 根据给定数字划分数组（模拟、双指针）

4394 最长连续子序列（滑动窗口 + 哈希表）

4395 最大子矩阵（前缀和 + 双指针）

子序列

2222 选择建筑的方案数（递推、找规律）

全排列

2160 拆分数位后四位数字的最小和（暴力 + 全排列）

3812 机器人走迷宫（枚举 + 全排列）

60 排列序列（枚举--第 k 个全排列模板）

位运算

2166 设计位集（位运算）

1929 镜子田地（环图、位运算）

前缀和

1913 公平摄影（枚举 + 前缀和 + 哈希表）

3774 亮灯时长（枚举 + 贪心 + 前缀和）

4297 截断数组（前缀和 + 后缀和）

4217 机器人移动（二分 + 前缀和）

4078 01串（前缀和 + dp）

3993 石子游戏（贪心 + 前缀和）

3956 截断数组（枚举 + 前缀和）

3788 截断数组（前缀和）

2171 拿出最少数目的魔法豆（枚举 + 前缀和）

2155 分组得分最高的所有下标（前缀和 + 后缀和）

4395 最大子矩阵（前缀和 + 双指针）

离散化

离散化一般有很多种的实现方式，常见的有两种：① map来实现（哈希表）② 手写离散化

1952 金发姑娘和 N 头牛（差分 + 离散化--两种离散化方式）

4214 三元组（枚举技巧、树状数组维护最值）

4316 合适数对（树状数组）

单调栈

找到左/右边第一个比当前位置小/大的元素或者位置

3780 构造数组（单调栈）

线段树

线段树一般能够处理区间单点修改，区间修改，区间查询等与区间相关的问题，一般如果只是单点修改那么不需要使用懒标记，如果是区间修改一般需要懒标记。注意有的线段树的题目是不包含区间右端点，此时需要处理一下，类似于1750题。

1750 救生员（枚举 + 区间合并、线段树）

3805 环形数组（线段树-c++-java-python）

6030 由单个字符重复的最长子字符串（线段树）

二进制

1875 贝茜的报复（dfs、二进制）

3727 乘方相加（k进制）

基环树

1738 蹄球（思维题、基环树）

4216 图中的环（基环树）

二分图

4298 搭档（二分图的最大匹配、贪心）

4205 树的增边（二分图染色）

4415 点的赋值（二分图染色）

并查集

4304 字符串归类（枚举技巧 + 并查集）

4084 号码牌（并查集）

4075 染色（并查集）

3579 数字移动（环图、找环、并查集）

4420 连通分量（并查集--统计每个集合中点的数目）

思维题

1904 奶牛慢跑（思维题）

1855 愤怒的奶牛（思维题、枚举）

1738 蹄球（思维题、基环树）

1696 困牛排序（思维题、构造）

3762 二进制矩阵（思维题、构造）

3763 数字矩阵（思维题）

3784 交换相邻元素（思维题）

3808 画正方形（思维题、枚举）

3814 矩阵变换（思维题）

4211 序列重排（构造、思维题--双关键字排序）

3957 子序列（思维题、枚举 + 前缀最值）

3778 平衡数组（思维题、构造）

2177 找到和为给定整数的三个连续整数（思维题）

4396 取石子（思维题）

树形dp

3760 最大剩余油量（树形dp）

4381 翻转树边（树形dp）

区间dp

3996 涂色（区间dp）

5 最长回文子串（区间 dp）​​​​​​​

区间合并

4412 构造数组（区间合并）

分类讨论

1726 挤奶顺序（分类讨论、模拟）

3804 构造字符串（分类讨论）

4414 子序列（分类讨论、贪心）

破环成链

3810 最长连续休息时间（破环成链）

二分查找

一般数据范围在10 ^ 5左右的求解最值的问题可以考虑能否使用二分来解决，二分的难点在于如何找到一个题目中的一个性质使得枚举的答案具有二段性，而且题目能用二分来解决的充要条件是枚举的答案具有两段性，可以将答案区间分为两部分，单调性是二段性的一个特例，所有很多时候时候可以根据单调性进行二分，但是有的题目没有单调性但是是可以使用二分来解决的。

3418 杨辉三角形（python3 找规律 + 二分）

1460 我在哪？（二分、字符串哈希）

4217 机器人移动（二分 + 前缀和）

4199 公约数（求解约数 + 最大公约数 + 二分）

4080 第k个数（二分）

4001 训练（二分 + count列表标记）

3992 树上有猴（二分、求解区间交集）

3973 无线网络（二分 + 双指针）

3578 最大中位数（二分查找）

2187 完成旅途的最少时间（二分）

树状数组

树状数组一般维护的是区间的单点修改与区间查询的相关问题，一般可以求解比左边大/小的相关问题。

4214 三元组（枚举技巧、树状数组维护最值）

3662 最大上升子序列和（dp + 树状数组优化）

4316 合适数对（树状数组）

背包问题

背包问题的特点是"有限制的选择问题"

3417 砝码称重（python3 零一背包问题）

4081 选数（二维费用零一背包问题）

6029 射箭比赛中的最大得分（dfs、零一背包问题求解具体方案）

拓扑排序

拓扑排序用在有向无环图中，可以判断拓扑排序是否存在，求解拓扑序列

2115 从给定原材料中找到所有可以做出的菜（拓扑排序）

3813 最大路径权值（枚举 + 拓扑排序 + 递推）

3696 构造有向无环图（拓扑排序）

2192 有向无环图中一个节点的所有祖先（拓扑排序）

前缀最值

1978 奶牛过马路（前缀最值）

 3957 子序列（思维题、枚举 + 前缀最值）

状态压缩

1960 闪烁（状态压缩、找环）

floyd算法

1471 牛奶工厂（floyd求解传递闭包、证明）

状态机dp

1884 COW（递推、状态机dp）

字符串哈希

1460 我在哪？（二分、字符串哈希）

最小生成树

3728 城市通电（prim算法--添加超级源点）

蓝桥杯真题

第十三届蓝桥杯

单源最短路径

4196 最短路径（堆优化版的dijkstra算法、spfa算法模板）

4074 铁路与公路（单源最短路径）

3772 更新线路（bfs、最短路计数）

2203 得到要求路径的最小带权子图（堆优化版的dijkstra算法）

3628 边的删减（最短路树）

最近公共祖先

最近公共祖先主要用来求解树种任意两点之间的最短距离，而求解树中任意两点的最长路径则需要使用树形dp来解决。

4202 穿过圆（倍增法求解最近公共祖先）