图论相关
关于图的问题,如果数据范围在 $1e5$ 以上,除非确定使用某些特定的算法,基本上就需要 $O(n)$ 的算法了。这个数据范围 $O(nlogn)$ 理论上也能过,但是带 $log$ 复杂度的和图相关的算法不多,所以可以优先向 $O(n)$ 的算法考虑(贪心,换根 DP 之类的)
- 判断图中是否存在环:AcWing 1352. 虫洞
- 判断有向图中是否存在环 + DP(还可以用拓扑排序判环):LeetCode 1857. 有向图中最大颜色值
- 找出图(基环树)中最长的环:LeetCode 2360. 图中的最长环
- 基环树 1:LeetCode 2127. 参加会议的最多员工数
- 基环树 2:LeetCode 2876. 有向图访问计数
- 找出无向图中的最长环:LeetCode 1559. 二维网格图中探测环
- $tarjan$ 算法求割点:LeetCode 1568. 使陆地分离的最少天数
- 最长路:LeetCode 1514. 概率最大的路径
- 拓扑排序:LeetCode 1591. 奇怪的打印机 II
- 拓扑排序 + DP1:LeetCode 2050. 并行课程 III
- 拓扑排序 + DP2:LeetCode 1857. 有向图中最大颜色值
- 拓扑排序 + 并查集:LeetCode 1632. 矩阵转换后的秩
- 拆点 + 最短路:LeetCode 1928. 规定时间内到达终点的最小花费
- 拓扑排序 + 构造:LeetCode 2392. 给定条件下构造矩阵
多维 BFS
树上相关问题
倍增技巧
离线技巧
- 并查集 + 离线查询:LeetCode 1697. 检查边长度限制的路径是否存在
- Trie + 离线查询:LeetCode 1707. 与数组中元素的最大异或值
- LeetCode 1847. 最近的房间
并查集
搜索相关
- AcWing 93. 递归实现组合型枚举
- AcWing 1573. 递归实现组合型枚举 II
- AcWing 92. 递归实现指数型枚举
- AcWing 1572. 递归实现指数型枚举 II
- AcWing 94. 递归实现排列型枚举
- AcWing 1537. 递归实现排列类型枚举 II
- 将 $n$ 个物品分到 $k$ 个组内的枚举:LeetCode 1723. 完成所有工作的最短时间
- 枚举子集技巧:LeetCode 1681. 最小不兼容性
- 折半搜索:LeetCode 1755. 最接近目标值的子序列和
- 八个方向搜索 + 限制拐弯方向:AcWing 5165. CCC单词搜索
状态压缩 DP
- LeetCode 996. 正方形数组的数目
- LeetCode 1595. 连通两组点的最小成本
- LeetCode 1879. 两个数组最小的异或值之和
- LeetCode 1931. 用三种不同颜色为网格涂色
- LeetCode 1994. 好子集的数目
- 这一题和上一题很像:LeetCode 2572. 无平方子集计数
- LeetCode 2741. 特别的排列
- 枚举子集技巧 + 状态压缩 1:LeetCode 1655. 分配重复整数
- 枚举子集技巧 + 状态压缩 2:LeetCode 1723. 完成所有工作的最短时间
- 枚举子集技巧 + 状态压缩 3:LeetCode 1799. N 次操作后的最大分数和
乘积相关 DP
选或者不选类型 DP
- LeetCode 1621. 大小为 K 的不重叠线段的数目
- LeetCode 1639. 通过给定词典构造目标字符串的方案数
- LeetCode 1751. 最多可以参加的会议数目 II
- LeetCode 1883. 准时抵达会议现场的最小跳过休息次数
- 选或者不选 + 状态机:LeetCode 1955. 统计特殊子序列的数目
- LeetCode 2809. 使数组和小于等于 x 的最少时间
枚举选哪个类型 DP
树形 DP
数位 DP
- 最基础的:AcWing 338. 计数问题
- 也是统计数位的个数:AcWing 3396. 求1和2的个数
- AcWing 56. 从1到n整数中1出现的次数
- 可以用数位 DP 求解:AcWing 3752. 更小的字符串
- LeetCode 600. 不含连续1的非负整数
- LeetCode 2376. 统计特殊整数
- LeetCode 2719. 统计整数数目
- LeetCode 2801. 统计范围内的步进数字数目
- 提高课的几道数位DP
其他有意思的 DP
二分查找
lodash.js
中提供了两个函数,具有 C++ 中的 lower_bound
和 upper_bound
的功能
_.sortedIndex(nums, target)
:从数组的 begin 位置到 end - 1 位置二分查找第一个大于或等于 target 的数字,找到返回该数字的下标,不存在则返回 end。_.sortedLastIndex(nums, target)
:从数组的 begin 位置到 end - 1 位置二分查找第一个大于 target 的数字,找到返回该数字的下标,不存在则返回end。- 例题:LeetCode 1547. 切棍子的最小成本
二分与其他算法的综合
- 这题需要绕个弯:LeetCode 1648. 销售价值减少的颜色球
- LeetCode 2528. 最大化城市的最小供电站数目
- LeetCode 2560. 打家劫舍 IV
- 二分 + 多源 BFS:LeetCode 2258. 逃离火灾
- 二分 + 多源 BFS:LeetCode 2812. 找出最安全路径
三分
奇偶性 + 位运算 + 集合状压mask + 异或前缀运算
- LeetCode 1371. 每个元音包含偶数次的最长子字符串
- LeetCode 1542. 找出最长的超赞子字符串
- LeetCode 1915. 最美子字符串的数目
- LeetCode 2791. 树中可以形成回文的路径数
求「两段」问题
前后缀分解
解码类(递归)
差分
- LeetCode 1674. 使数组互补的最少操作次数
- 二维差分 + 二维前缀和:LeetCode 2132. 用邮票贴满网格图
字典树
- Trie + 离线查询:LeetCode 1707. 与数组中元素的最大异或值
- LeetCode 1803. 统计异或值在范围内的数对有多少
- Trie 查询异或最大值的应用:LeetCode 1938. 查询最大基因差
- Trie + 树哈希:LeetCode 1948. 删除系统中的重复文件夹
贡献法 + 单调栈
- LeetCode 907. 子数组的最小值之和
- LeetCode 1793. 好子数组的最大分数
- LeetCode 1856. 子数组最小乘积的最大值
- LeetCode 2104. 子数组范围和
- LeetCode 2281. 巫师的总力量和
- LeetCode 2818. 操作使得分最大
- 单调栈的应用 1:LeetCode 1944. 队列中可以看到的人数
- 单调栈的应用 2(和二分的结合):LeetCode 2940. 找到 Alice 和 Bob 可以相遇的建筑
最长上升子序列
线段树
- (单点修改,区间查询)和单调栈的结合:LeetCode 2289. 使数组按非递减顺序排列
- (单点修改,区间查询)和最长上生子序列的结合:LeetCode 2407. 最长递增子序列 II
- (单点修改,区间查询)LeetCode 2926. 平衡子序列的最大和
- (区间修改,区间查询)带懒标记线段树 1:LeetCode 2262. 字符串的总引力
- (区间修改,区间查询)带懒标记线段树 2:LeetCode 100074. 子数组不同元素数目的平方和 II
数学(组合计数)
容斥原理
最大子序和
- 一维版本:LeetCode 53. 最大子数组和
- 二维版本1:牛客:子矩阵的最大累加和问题
- 二维版本2:LeetCode 面试题 17.24. 最大子矩阵
一些当时没有想到的双指针
按照数值进行分类
C++ 加速输入/输出
#define ios cin.tie(0);cout.tie(0);ios::sync_with_stdio(false)
int main() {
ios;
cin >> ...
cout << ...
}
或者是:
int main() {
cin.tie(0)->sync_with_stdio(false);
return 0;
}
scanf
和printf
太难写了…
多写写就会好不少,一直用sync和tie也挺累
hh是的,还是打的太少了我