ATcoder题目算法分类

· · 个人记录

1 前缀和/差分

$ABC278E$ 二维差分/其实枚举就可以了( $ABC267C$ 前缀和套前缀和 $ABC265D$ 尺取法/前缀和 $ABC183D$ 【模板】差分 ## $2$ 图论 ### $2.1$ 并查集 $ABC327E$ 拓展域并查集 $ABC304E ABC293D $ABC291E$ 拓扑+并查集 $ABC287C$ 并查集判连通 $ABC284C$ 【模板】图的连通块个数 $ABC280F$ （并查集判连通块+dfs+简单动脑筋） $ABC279F$ （复杂并查集） $ABC264E$ 并查集+反向建边 ### $2.2$ 图的遍历 $ABC284E $ABC277C ABC276B ### $2.3$ 拓扑排序/$\mathtt{DAG}$/$\mathtt{DFS}$ 树 $ABC315E$ DAG $ABC296E$ 缩点/拓扑排序 $ABC291E$ 拓扑+并查集 $ABC285D$（需用哈希离散化） ### $2.4$ 最短路 $ABC305E$ 多个起点的dijkstra $ABC299E$ dijkstra+构造 $ABC289E$（复杂最短路） $ABC287E$（复杂最短路） $ABC277E$（复杂最短路） ### $2.5$ 最小生成树 $ABC282E$ 最小生成树+快速幂 ### $2.6$ 树/链/环 $ABC315E$ dfs 树的深度问题 $ABC312G$ 树上问题，随便搞搞就可以了 $ABC288C$ 破环问题 $ABC287C$ 判断是否为链 ### $2.7$ 缩点/割点/桥 $ABC296E$ 缩点/拓扑排序 ## $3$ 哈希 $ABC296C$ 哈希/map $ABC287E$ 哈希截取子串+vector $ABC284F$（字符串哈希） $ABC279C$（多重一维哈希） $ABC278C$（哈希离散化） ## $4 \mathtt{DP}

4.1 背包

$ABC321F$ 01 背包 $ABC317D$ 01 背包 $ABC306D$ 01背包 $ABC291D$ 01背包 $ABC169F$ 01背包+逆元 ### $4.2$ 状压 $ABC318D$ 状压 DP $ABC301E$ BFS套状压DP $ABC283E$ 状态压缩DP ### $4.3$ 区间 ### $4.4$ $\mathtt{LIS}$ 以及类似问题 $ABC165F$ 【模板】树上最长上升子序列 ### $4.5$ 概率/期望 $ABC327E$ 概率 DP $ABC326E$ 概率 DP $ABC323E$ 概率 DP $ABC300E$ 概率 DP $ABC298E$ 概率 DP ### $4.6$ $\mathtt{DP}$ 优化 $ABC315F$ DP+特殊优化 $ABC311E$ 二维DP+前缀和 $ABC288F$ DP+找规律优化 $ABC183E$ 二维DP+前缀和优化 ### $4.7$ 其他 $ABC324E$ DP+树状数组 $ABC312D$ 括号序列 DP $ABC288E$ DP $ABC285E$（记忆化搜索/DP） ## $5$ 搜索/记忆化/剪枝 $ABC326D$ DFS $ABC321E$ 搜索剪枝 $ABC317E$ BFS+优化 $ABC311D$ 广搜 $ABC297E$ BFS+优先队列 $ABC293C$ BFS $ABC289C$ DFS $\ |\ ABC289D$ DFS $ABC286D$ 记忆化dfs（想偷懒不写记忆化，结果寄了……） $ABC285E$（记忆化搜索/DP） $ABC278F$ 博弈论+dfs $ABC277D ABC276E ABC264D ABC165C $ABC151D$ bfs/冒泡排序 ## $6$ 数学 ### $6.1$ 分解质因数 $ABC292C$ 分解质因数+预处理 $ABC284D ABC280D $ABC161F$ 动脑筋+分解质因数 ### $6.2$ 快速幂/逆元 $ABC298D$ 快速幂+数学 $ABC293E$ 快速幂+分治 $ABC282E$ 最小生成树+快速幂 $ABC280E$（快速幂+dfs/组合数+逆元） $ABC169F$ 01背包+逆元 ### $6.3$ 组合数学 $ABC297F$ 组合数学计数 $ABC280E$（快速幂+dfs/组合数+逆元） $ABC151E

6.4 最大公约数/最小公倍数/更相减损术

$ABC290D$ 约瑟夫斯抽杀问题 $ABC276D$(gcd+动脑筋) ### $6.5$ 计算几何 $ABC289F$ 平面直角坐标系+点的对称 $ABC183B$ 相似三角形 $ABC151F$ 【模板】最小圆覆盖 ### $6.6$ 筛法 $ABC300D$ 线性筛+贪心/埃式筛+贪心 ### $6.7$ 推规律/递推 $ABC319E$ 周期 $ABC313E$ 递推 $AGC063B$ 递推+栈模拟 $ABC307E$ 环形染色问题 $ABC279E$ ~~简单~~动脑筋+找规律 ### $6.8$ 构造 $ABC313D$ 交互+构造 ## $7$ 数据结构 $ABC327F$ 扫描线（同窗口的星星） $ABC322F$ 区间最大子段和 $ABC307D$ 栈模拟 $ABC306E$权值树状数组+二分 $|ABC306F$ 树状数组求逆序对 $ABC298C$ map $ABC283D$ 栈 $|\ ABC283F$ 线段树 $ABC282F$ ST表 $ABC281E$ set/线段树 $|\ ABC281F$ 字典树Trie $ABC278D$ 线段树/map $ABC246C$ 优先队列 ## $8$ 贪心 $ABC318C $ABC305F$ 图论贪心 $ABC301D$ 贪心，位运算 $ABC298F$ 贪心+离散化 $ABC174D $ABC161E

9 二分/三分

$ABC312C$ 二分套二分（被超出值域的答案罚了3发） $ABC305D$ 二分 $ABC304D$ 二分 $ABC299D$ 二分+交互 $ABC279D$ 三分 $ABC174E$ 二分 ## $10$字符串 $ABC287D$ 简单动脑筋+字符串 $ABC286C$ 字符串 ## $11$ 分治 $ABC293E$ 快速幂+分治 ## $12$ 博弈论 $AGC063A

13 不是很水的模拟

ABC323F ABC322D ABC307C ABC301C ABC300C

其他

$ABC276C$ 康拓展开，全排列 $ABC264B$ 打表（你可以硬推规律，试试就逝逝）