## File: README.md

# 算法竞赛模板库 by 灵茶山艾府 💭💡🎈

## 算法 Algorithm

由于算法知识点繁杂，将自己学习到的算法、做过的题目分类整理好是有必要的。

一个算法模板应当涵盖以下几点：
- 对该算法的基本介绍（核心思想、复杂度等）
- 参考链接或书籍章节（讲得比较好的资料）
- 模板代码（代码注释、使用说明）
- 模板补充（常见题型中的额外代码、建模技巧等）
- 相关题目（模板题、经典题、思维转换题等）

## 算法目录

[不了解 Go？快速入门教程](https://gobyexample-cn.github.io/)

- [集合论与位运算](https://leetcode.cn/circle/discuss/CaOJ45/)
- 数据结构
  - [单调栈 monotone_stack.go](/copypasta/monotone_stack.go)
  - [单调队列 monotone_queue.go](/copypasta/monotone_queue.go)
    - 二维单调队列
  - [双端队列 deque.go](/copypasta/deque.go)
    - [最小双端队列 deque_min.go](/copypasta/deque_min.go)
  - [堆（优先队列）heap.go](/copypasta/heap.go)
    - 支持修改、删除指定元素的堆
    - 懒删除堆
    - 对顶维
    - 前缀中位数
    - 滑动窗口前 k 小元素和
  - [并查集 union_find.go](/copypasta/union_find.go)
    - 点权并查集
    - 边权并查集（种类并查集）
    - 可持久化并查集
    - 回滚并查集 & 动态图连通性
  - [ST 表 sparse_table.go](/copypasta/sparse_table.go)
    - 不相交 ST 表（猫树）
    - 二维 ST 表
    - 线段树套 ST 表
  - [树状数组 fenwick_tree.go](/copypasta/fenwick_tree.go)
    - 差分树状数组（支持区间加、区间求和）
    - 二维树状数组
    - 二维差分树状数组
    - 离线二维数点
  - [线段树 segment_tree.go](/copypasta/segment_tree.go)
    - 线段树二分
    - 延迟标记（懒标记）
      - [矩形面积并（扫描线）segment_tree_rect.go](/copypasta/segment_tree_rect.go)
    - 动态开点
    - 线段树合并
    - 线段树分裂
    - 线段树分治 / 时间线段树
    - 可持久化线段树（主席树）
      - 在线二维数点
  - [树套树 seg_in_bit.go](/copypasta/seg_in_bit.go)
  - [0-1 线段树 segment_tree01.go](/copypasta/segment_tree01.go)
  - [左偏树（可并堆）leftist_tree.go](/copypasta/leftist_tree.go)
  - [笛卡尔树 cartesian_tree.go](/copypasta/cartesian_tree.go)
  - [二叉搜索树公共方法 bst.go](/copypasta/bst.go)
  - [Treap treap.go](/copypasta/treap/README.md)
    - [前 k 小元素和](/copypasta/treap/prefixsum/prefixsum.go)
  - [伸展树 splay.go](/copypasta/splay.go)
  - [动态树 LCT link_cut_tree.go](/copypasta/link_cut_tree.go)
  - [红黑树 red_black_tree.go](/copypasta/red_black_tree.go)
  - [替罪羊树 scapegoat_tree.go](/copypasta/scapegoat_tree.go)
  - [k-d 树 kd_tree.go](/copypasta/kd_tree.go)
  - 珂朵莉树（ODT）
    - [数组版 odt.go](/copypasta/odt.go)
    - [平衡树版 odt_bst.go](/copypasta/odt_bst.go)
  - [根号分治、分块 sqrt_decomposition.go](/copypasta/sqrt_decomposition.go)
  - [莫队算法 mo.go](/copypasta/mo.go)
     - 普通莫队
     - 带修莫队
     - 回滚莫队
     - 树上莫队
- [字符串 strings.go](/copypasta/strings.go)
  - 字符串哈希
  - KMP
    - pi 函数
    - border
    - 最小循环节
    - fail 树（失配树 / border 树）
  - 扩展 KMP（Z algorithm）
  - 最小表示法
  - 最长回文子串 
    - Manacher 算法
  - [回文自动机（回文树，PAM）pam.go](/copypasta/pam.go)
  - 后缀数组（SA）
  - [后缀自动机（SAM）sam.go](/copypasta/sam.go)
  - [字典树 trie.go](/copypasta/trie.go)
    - 可持久化字典树
  - [0-1 字典树 trie01.go](/copypasta/trie01.go)
    - 最大异或和
    - 第 k 大异或和
    - 删除元素
    - 可持久化 0-1 字典树
    - 【研究】0-1 字典树上最多有多少个节点
  - [AC 自动机 acam.go](/copypasta/acam.go)
- 数学
  - [数论 math.go](/copypasta/math.go)
    - 辗转相除法（最大公因数 GCD）
    - 类欧几里得算法 ∑⌊(ai+b)/m⌋
    - Pollard-Rho 质因数分解算法
    - 埃氏筛（埃拉托斯特尼筛法）
    - 欧拉筛（线性筛）
    - 欧拉函数
    - 原根
    - 扩展 GCD
      - 二元一次不定方程
    - 逆元
      - 线性求逆元
    - 中国剩余定理（CRT）
      - 扩展中国剩余定理
    - 离散对数
    - 大步小步算法（BSGS）
      - 扩展大步小步算法
    - 二次剩余
    - Jacobi 符号
    - N 次剩余
    - 卢卡斯定理
      - 扩展卢卡斯定理
    - 卡特兰数
    - 默慈金数
    - 那罗延数
    - 斯特林数
      - 第一类斯特林数（轮换）
      - 第二类斯特林数（子集）
    - 贝尔数
    - 欧拉数
    - 数论分块（整除分块）
    - 莫比乌斯函数
    - 莫比乌斯反演
      - 互质计数问题
      - GCD 求和问题
    - 杜教筛
  - [组合数学 math_comb.go](/copypasta/math_comb.go)
    - 常见模型
    - 常用恒等式
    - 容斥原理
  - [快速傅里叶变换 FFT math_fft.go](/copypasta/math_fft.go)
  - [快速数论变换 NTT math_ntt.go](/copypasta/math_ntt.go)
    - 包含多项式全家桶（求逆、开方等等）
  - [快速沃尔什变换 FWT math_fwt.go](/copypasta/math_fwt.go)
  - [连分数、佩尔方程 math_continued_fraction.go](/copypasta/math_continued_fraction.go)
  - [线性代数 math_matrix.go](/copypasta/math_matrix.go)
    - 矩阵快速幂
    - Berlekamp-Massey 算法
    - Kitamasa 算法
    - 高斯消元
    - 行列式
    - 线性基
  - [数值分析 math_numerical_analysis.go](copypasta/math_numerical_analysis.go)
    - 自适应辛普森积分
    - 拉格朗日插值
  - [计算几何 geometry.go](/copypasta/geometry.go)
    - 线与点
    - 线与线
    - 圆与点
      - 最小圆覆盖
        - Welzl 随机增量法
      - 固定半径覆盖最多点
    - 圆与线
    - 圆与圆
    - 圆与矩形
    - 最近点对
    - 多边形与点
      - 判断点在凸多边形内 $O(\log n)$
      - 判断点在任意多边形内
        - 转角法（统计绕数）
    - 凸包
      - 动态凸包
    - 最远点对
      - 旋转卡壳
    - 半平面交
  - [博弈论 games.go](/copypasta/games.go)
    - SG 函数
- [动态规划 dp.go](/copypasta/dp.go)
  - 背包
    - 0-1 背包
    - 完全背包
    - 多重背包
      - 二进制优化
      - 单调队列优化
      - 同余前缀和优化（求方案数）
    - 分组背包
    - 树上背包（依赖背包）
    - 字典序最小方案
  - 线性 DP
    - 最大子段和
    - LCS
    - LPS
    - LIS
      - 狄尔沃斯定理
    - LCIS
    - 长度为 m 的 LIS 个数
    - 本质不同子序列个数
  - 区间 DP
  - 环形 DP
  - 博弈 DP
  - 概率 DP
  - 期望 DP
  - 状压 DP
    - 全排列 DP
    - 旅行商问题（TSP）
    - 子集 DP
    - 高维前缀和（SOS DP）
    - 插头 DP
  - 数位 DP
    - 求个数
    - 求和
  - 倍增优化 DP
  - 斜率优化 DP（CHT）
  - WQS 二分优化 DP（凸优化 DP / 带权二分）
  - 树形 DP
    - 树的直径个数
    - 在任一直径上的节点个数
    - 树上最大独立集
    - 树上最小顶点覆盖
    - 树上最小支配集
    - 树上最大匹配
    - 换根 DP（二次扫描法）
      - 简单写法
      - 维护最大次大写法
      - 前后缀分解写法（适用性最广）
- [图论 graph.go](/copypasta/graph.go)
  - 链式前向星
  - DFS 常用技巧
  - BFS 常用技巧
  - 欧拉回路和欧拉路径
    - 无向图
    - 有向图
    - 完全图
  - 割点
  - 割边（桥）
  - 双连通分量（BCC）
    - v-BCC
    - e-BCC
  - 仙人掌 & 圆方树
  - 最短路
    - Dijkstra
    - SPFA（队列优化的 Bellman-Ford）
      - 差分约束系统
    - Floyd-Warshall
    - Johnson
    - 0-1 BFS（双端队列 BFS）
    - 字典序最小最短路
    - 同余最短路
  - 最小环
  - 最小斯坦纳树
  - 最小生成树（MST）
    - Kruskal
    - Prim
  - 单度限制最小生成树
  - 次小生成树
  - 曼哈顿距离最小生成树
  - 最小差值生成树
  - 最小树形图
    - 朱刘算法
  - 二分图判定（染色）
  - 二分图找奇环
  - 二分图最大匹配
    - 匈牙利算法
  - 带权二分图最大完美匹配
    - Kuhn–Munkres 算法
  - 拓扑排序
  - 强连通分量（SCC）
    - Kosaraju
    - Tarjan
  - 2-SAT
  - 基环树
  - 最大流
    - Dinic
    - ISAP
    - HLPP
  - 最小费用最大流
    - SPFA
    - Dijkstra
  - 三元环计数
  - 四元环计数
  - [树上问题 graph_tree.go](/copypasta/graph_tree.go)
    - 直径
    - 重心
    - 点分治
    - 点分树
    - 最近公共祖先（LCA）
      - 倍增
      - ST 表
      - Tarjan
      - 树上差分
      - 虚树
    - 重链剖分（HLD）
    - 长链剖分
    - 树上启发式合并（small to large）
      - 按大小合并
      - 轻重儿子合并
    - 树分块
    - Prufer 序列
  - [网格图 graph_grid.go](/copypasta/graph_grid.go)
- 其他
  - [bitset](/copypasta/bitset.go)
  - [位运算笔记 bits.go](/copypasta/bits.go)
    - 区间位运算 trick（含 GCD）
  - [二分 三分 sort.go](/copypasta/sort.go)
    - 二分答案
    - 0-1 分数规划
    - 整体二分
  - [搜索 search.go](/copypasta/search.go)
    - 枚举排列
    - 枚举组合
    - 生成下一个排列
    - 康托展开
    - 逆康托展开
    - 枚举子集
      - Gosper's Hack
    - 折半枚举（Meet in the middle）
      - 超大背包问题
  - [随机算法 rand.go](/copypasta/rand.go)
    - 模拟退火
  - [基础算法 common.go](/copypasta/common.go)
    - 算法思路整理
    - 分组循环
    - 滑动窗口
    - 前缀和
    - 同余前缀和
    - 二维前缀和
    - 菱形区域和
    - 斜向前缀和
      - 菱形边界和
    - 等腰直角三角形区域和
      - 金字塔区域和
    - 二阶差分
    - 二维差分
    - 菱形二维差分
    - 离散化
  - [杂项 misc.go](/copypasta/misc.go)
- [快速输入输出模板 io.go](/copypasta/io.go)
- [交互题单 interactive.go](/copypasta/interactive.go)

## 算法题单

[如何科学刷题？](https://leetcode.cn/circle/discuss/RvFUtj/)

1. [滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）](https://leetcode.cn/circle/discuss/0viNMK/)
2. [二分算法（二分答案/最小化最大值/最大化最小值/第K小）](https://leetcode.cn/circle/discuss/SqopEo/)
3. [单调栈（基础/矩形面积/贡献法/最小字典序）](https://leetcode.cn/circle/discuss/9oZFK9/)
4. [网格图（DFS/BFS/综合应用）](https://leetcode.cn/circle/discuss/YiXPXW/)
5. [位运算（基础/性质/拆位/试填/恒等式/思维）](https://leetcode.cn/circle/discuss/dHn9Vk/)
6. [图论算法（DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径）](https://leetcode.cn/circle/discuss/01LUak/)
7. 🔥[动态规划（入门/背包/状态机/划分/区间/状压/数位/数据结构优化/树形/博弈/概率期望）](https://leetcode.cn/circle/discuss/tXLS3i/)
8. [常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）](https://leetcode.cn/circle/discuss/mOr1u6/)
9. [数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）](https://leetcode.cn/circle/discuss/IYT3ss/)
10. [贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）](https://leetcode.cn/circle/discuss/g6KTKL/)
11. [链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）](https://leetcode.cn/circle/discuss/K0n2gO/)
12. [字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）](https://leetcode.cn/circle/discuss/SJFwQI/)

欢迎关注 [B站@灵茶山艾府](https://space.bilibili.com/206214)

## 如何选择题目 How to Choose Problems

### Rating < 2100

这一阶段主要目标是提高对问题的观察能力。做构造题可以针对性地训练这一点。

选择难度在自己 rating 到 rating+200 范围内的构造题 (tag: constructive algorithms)，按照过题人数降序做题，比如 [1700,1900] 区间的就是下面这个链接：

[https://codeforces.com/problemset?order=BY_SOLVED_DESC&tags=constructive+algorithms%2C1700-1900](https://codeforces.com/problemset?order=BY_SOLVED_DESC&tags=constructive+algorithms%2C1700-1900)

通过大量的构造题训练，提高观察能力，快速找到切题入口。具体见我在知乎上的这篇 [回答](https://www.zhihu.com/question/353734418/answer/2353160035)。

### Rating >= 2100（个人训练用，仅供参考）

见识更高的山、更广的海。

按人数从高到低，做 2200+ 的题目。**建议不设置难度上限**！由于按人数排序，难度分不会太高，**不设上限可以避免错过高分好题**。

- [按照洛谷通过人数排序的 CF 题单](https://www.luogu.com.cn/training/465300)
- [构造题 2200+](https://codeforces.com/problemset?order=BY_SOLVED_DESC&tags=constructive+algorithms%2C2200-)：锻炼手玩能力。
- [DP 2200+](https://codeforces.com/problemset?order=BY_SOLVED_DESC&tags=dp%2C2200-)：几乎每场都有 DP。
- [数学综合：数论、组合数学、概率期望等 2200+](https://codeforces.com/problemset?order=BY_SOLVED_DESC&tags=combine-tags-by-or%2Ccombinatorics%2Cfft%2Cmatrices%2Cnumber+theory%2Cprobabilities%2Cchinese+remainder+theorem%2C2200-)：包含 6 个 tag。
- [图论综合：图论+树上问题 2200+](https://codeforces.com/problemset?order=BY_SOLVED_DESC&tags=combine-tags-by-or%2C2-sat%2Cdsu%2Cflows%2Cgraph+matchings%2Cgraphs%2Cshortest+paths%2Ctrees%2C2200-)：包含 7 个 tag。
- [字符串 2200+](https://codeforces.com/problemset?order=BY_SOLVED_DESC&tags=combine-tags-by-or%2Cstring+suffix+structures%2Cstrings%2C2200-)：数据结构题不好筛选，可以找树状数组/线段树的题单，这里只单独筛选字符串的题。
- [交互 2200+](https://codeforces.com/problemset?order=BY_SOLVED_DESC&tags=interactive%2C2200-)：偶尔做做，了解一些解题套路。
- [博弈 2000+](https://codeforces.com/problemset?order=BY_SOLVED_DESC&tags=games%2C2000-)：也适合锻炼手玩。由于题目比较少，从 2000 开始筛选。

**我的 Codeforces 账号**

[](https://codeforces.com/profile/0x3F)


## 测试及对拍 Testing

编写一个 `run(io.Reader, io.Writer)` 函数来处理输入输出。这样写的理由是：

- 在 `main` 中调用 `run(os.Stdin, os.Stdout)` 来执行代码；
- 测试时，将测试数据转换成 `strings.Reader` 当作输入，并用一个 `strings.Builder` 来接收输出，将这二者传入 `run` 中，然后就能比较输出与答案了；
- 对拍时需要实现一个暴力算法 `runAC`，参数和 `run` 一样。通过 [随机数据生成器](/main/testutil/rand.go) 来生成数据，分别传入 `runAC` 和 `run`，通过比对各自的输出，来检查 `run` 中的问题。

具体可以见 Codeforces 代码仓库 [main](/main)，所有非交互题的代码及其对应测试全部按照上述框架实现。

例如：[1439C_test.go](/main/1400-1499/1439C_test.go)

交互题的写法要复杂一些，需要把涉及输入输出的地方抽象成接口，详见 [interactive_problem](/copypasta/template/interactive_problem)。

## 学习资料及题目 Resources

注：由于入门经典上选了很多区域赛的题，一部分题目可以在 GYM 上找到，这样可以就可以用 Go 编程提交了。

[算法竞赛入门经典（第二版）](https://github.com/aoapc-book/aoapc-bac2nd)

[算法竞赛入门经典训练指南](https://github.com/klb3713/aoapc-book/tree/master/TrainingGuide/bookcodes)

[算法竞赛入门经典训练指南（升级版）](https://gitee.com/sukhoeing/aoapc-training-guide2)

[算法竞赛进阶指南](https://github.com/lydrainbowcat/tedukuri)

[算法竞赛入门到进阶](https://github.com/luoyongjun999/code)

[《算法竞赛》配套题单](https://www.luogu.com.cn/training/441063)

[国家集训队论文列表](https://github.com/enkerewpo/OI-Public-Library/tree/master/IOI%E4%B8%AD%E5%9B%BD%E5%9B%BD%E5%AE%B6%E5%80%99%E9%80%89%E9%98%9F%E8%AE%BA%E6%96%87)

[算法竞赛 (ICPC, OI, etc) 论文，课件，文档，笔记等](https://github.com/LzyRapx/Competitive-Programming-Docs)

[算法竞赛课件分享 by hzwer](https://github.com/hzwer/shareOI)

[算法第四版 Java 源码](https://algs4.cs.princeton.edu/code/)

[数据结构和算法动态可视化](https://visualgo.net/zh)

[OI Wiki](https://oi-wiki.org/)

[CP-Algorithms](https://cp-algorithms.com/)

[The Ultimate Topic List (with Resources, Problems and Templates)](https://codeforces.com/blog/entry/95106)

[A Huge Update on The Ultimate Topic List](https://codeforces.com/blog/entry/129419)

[洛谷日报](https://www.craft.do/s/N0l80k2gv46Psq)

[All the good tutorials found for Competitive Programming](https://codeforces.com/blog/entry/57282)

[Codeforces Problem Topics](https://codeforces.com/blog/entry/55274)

[The Ultimate Topic List(with Tutorials, Problems, and Templates)](https://blog.shahjalalshohag.com/topic-list/)

[GeeksforGeeks 上的算法合集](https://www.geeksforgeeks.org/how-to-prepare-for-acm-icpc/)

[Pepcy 模板](http://pepcy.cf/icpc-templates/)

[F0RE1GNERS 模板](https://github.com/F0RE1GNERS/template)

https://github.com/hh2048/XCPC 含 jiangly 模板

https://www.cnblogs.com/alex-wei/p/contents.html

[【模板整合计划】目录](https://www.cnblogs.com/Xing-Ling/p/10930556.html)

[算法学习笔记（目录）](https://zhuanlan.zhihu.com/p/105467597)

[洛谷模板题（建议按难度筛选）](https://www.luogu.com.cn/problem/list?keyword=%E6%A8%A1%E6%9D%BF&page=1)

[能力全面提升综合题单](https://www.luogu.com.cn/training/9391)

[Luogu Problem List](https://github.com/SFOI-Team/luogu-problem-list/blob/master/list.md)

[洛谷原试炼场](https://www.luogu.com.cn/paste/0id3h6on)

[Links of ICPC/CCPC Contests from China](https://codeforces.com/blog/entry/84429)

[AtCoder 题目分类](https://atcoder-tags.herokuapp.com/explain)

### AtCoder 版《挑战程序设计竞赛》

[AtCoder 版！蟻本 (初級編)](https://qiita.com/drken/items/e77685614f3c6bf86f44)

[AtCoder 版！蟻本 (中級編)](https://qiita.com/drken/items/2f56925972c1d34e05d8)

[AtCoder 版！蟻本 (上級編)](https://qiita.com/drken/items/9b311d553aa434bb26e4)

[AtCoder 版！蟻本 (発展的トピック編)](https://qiita.com/drken/items/0de3d205690d92307b7c)

### 待整理

[【杂文】记一些有用的神奇网站](https://www.cnblogs.com/Xing-Ling/p/10897760.html)

[偶然在 GitHub 上发现的超长列表](https://github.com/dhs347/Dream/blob/master/%E8%AE%A1%E5%88%92/%E8%AE%A1%E5%88%92%E4%B9%A6/A%E8%AE%A1%E5%88%92_%E9%98%B6%E6%AE%B51.md)

[算法竞赛训练中较难的部分](https://blog.csdn.net/skywalkert/article/details/48924861)

[算法竞赛中可能不太会遇到的论文题](https://blog.csdn.net/skywalkert/article/details/48878925)

[[杂谈]OI/ACM中冷门算法](https://zhuanlan.zhihu.com/p/21924647)

[Things I don't know](https://codeforces.com/blog/entry/92248)

> [meme] If you know at least 3 of these things and you are not red — you are doing it wrong. Stop learning useless algorithms, go and solve some problems, learn how to use binary search.

https://blog.csdn.net/calabash_boy/article/details/79973483

https://github.com/zimpha/algorithmic-library

https://www.luogu.com.cn/blog/command-block/blog-suo-yin-zhi-ding-post

https://wcysai.github.io/

https://www.luogu.com.cn/blog/Troverld/index

[C++ @cache](https://codeforces.com/blog/entry/124683)

## 其他 Others

My GoLand `Live Templates` and `Postfix Completion` [settings](/misc/my_goland_template)

### Useful Tools

[查看汇编](https://godbolt.org/)

[GeoGebra](https://www.geogebra.org/classic)

[Draw Geometry](https://csacademy.com/app/geometry_widget/)

[Draw Graph](https://csacademy.com/app/graph_editor/)

[OEIS](https://oeis.org/)

[Wolfram|Alpha](https://www.wolframalpha.com/)

[ACD Ladders](https://www.acodedaily.com/)

[Contests Filter](https://codeforceshelper.herokuapp.com/contests)

[Codeforced](http://codeforced.github.io/handle/)

[Codeforces Visualizer](https://cfviz.netlify.app/)

[Codeforces Solve Tracker](https://tom0727.github.io/cf-problems/)

[Another Codeforces Solve Tracker](https://cftracker.netlify.app/contests)

[AtCoder Categories](https://atcoder-categories.github.io/) 题单

[AtCoder Problems](https://kenkoooo.com/atcoder/#/table/)

[AtCoder Companions](https://atcoder-companions.kakira.dev/)

[AtCoder-Codeforces Rating converter](https://silverfoxxxy.github.io/rating-converter)

[在线 Markdown + LaTeX](https://stackedit.io/app)

### Rating and Difficulties

[Open Codeforces Rating System](https://codeforces.com/blog/entry/20762)

[How to Interpret Contest Ratings](https://codeforces.com/blog/entry/68288)

[Codeforces: Problem Difficulties](https://codeforces.com/blog/entry/62865)

[Elo rating system](https://en.wikipedia.org/wiki/Elo_rating_system#Theory)

### Stay Healthy

[Exercises!](https://musclewiki.org/)

---

## File: copypasta/template/interactive_problem/README.md

# Interactive Problem Template

To mock the IO part, implement this interface and use it both in `main.go` and `main_test.go`.

```go
type interaction interface {
	readInitData() initData
	query(request) response
	printAnswer(answer)
}
```

---

## File: copypasta/treap/README.md

目前有四个版本：

- [对标 C++ 的 set](./set/set.go)
- [对标 C++ 的 multiset](./multiset/multiset.go)
- [对标 C++ 的 map](./map/map.go)
- [把 treap 当作有序数组（允许重复元素），同时动态维护这个有序数组的前缀和](./prefixsum/prefixsum.go)

具体使用方法，见对应目录下的 test.go 文件。

关于遍历 treap 的逻辑，见 [bst.go](../bst.go)。

TIPS：某些题目通过插入 $-\infty$ 和 $\infty$ 哨兵，可以减少边界判断。

---

## File: leetcode/biweekly/179/d/README.md

## 方法一：前缀和优化 DP

设 $x = \textit{arr}[n-1]$，那么 $y = \textit{arr}[n-2]$ 必须 $\le x$。枚举所有满足数位和等于 $\textit{digitSum}[n-2]$ 的 $y$，问题变成：

- 在 $\textit{digitSum}$ 的 $[0,n-2]$ 中，以 $y$ 结尾的有效数组的个数。

这是一个规模更小的子问题。

定义 $f[i+1][x]$ 表示在 $\textit{digitSum}$ 的 $[0,i]$ 中，以 $x$ 结尾的有效数组的个数。

枚举所有满足数位和等于 $\textit{digitSum}[i-1]$ 的 $y$，问题变成在 $\textit{digitSum}$ 的 $[0,i-1]$ 中，以 $y$ 结尾的有效数组的个数，即 $f[i][y]$。

累加得

$$
f[i+1][x] = \sum_{y\le x} f[i][y]
$$

上式可以用 [前缀和](https://leetcode.cn/problems/range-sum-query-immutable/solution/qian-zhui-he-ji-qi-kuo-zhan-fu-ti-dan-py-vaar/) 优化。

初始值：$f[0][0] = 1$。

答案：$\sum\limits_{x} f[n][x]$。

代码实现时，注意取模。为什么可以在**中途取模**？原理见 [模运算的世界：当加减乘除遇上取模](https://leetcode.cn/circle/discuss/mDfnkW/)。

[本题视频讲解](https://www.bilibili.com/video/BV1dxXSBAE6F/?t=14m42s)，欢迎点赞关注~

```py [sol-Python3]
MOD = 1_000_000_007
MX = 5001
MAX_DIGIT_SUM = 31  # 4999 的数位和最大
dig_sum = [0] * MX

# 预处理数位和
for x in range(MX):
    # 去掉 x 的个位，问题变成 x // 10 的数位和，即 dig_sum[x // 10]
    dig_sum[x] = dig_sum[x // 10] + x % 10

class Solution:
    def countArrays(self, digitSum: List[int]) -> int:
        s = [1] * MX  # f 的前缀和
        for ds in digitSum:
            if ds > MAX_DIGIT_SUM:
                return 0
            for x in range(MX):
                # 如果 dig_sum[x] != ds，那么 f[x] = 0，否则 f[x] = s[x]
                # 把 f[x] 的值填到 s[x] 中，那么只需要把 dig_sum[x] != ds 的 s[x] 置为 0
                if dig_sum[x] != ds:
                    s[x] = 0
                if x > 0:
                    s[x] = (s[x] + s[x - 1]) % MOD
        return s[-1]
```

```java [sol-Java]
class Solution {
    private static final int MOD = 1_000_000_007;
    private static final int MX = 5001;
    private static final int MAX_DIGIT_SUM = 31; // 4999 的数位和最大
    private static final int[] digSum = new int[MX];
    private static boolean initialized = false;

    // 这样写比 static block 快
    public Solution() {
        if (initialized) {
            return;
        }
        initialized = true;

        // 预处理数位和
        for (int x = 0; x < MX; x++) {
            // 去掉 x 的个位，问题变成 x / 10 的数位和，即 digSum[x / 10]
            digSum[x] = digSum[x / 10] + x % 10;
        }
    }

    public int countArrays(int[] digitSum) {
        int[] sum = new int[MX]; // f 的前缀和
        Arrays.fill(sum, 1);
        for (int ds : digitSum) {
            if (ds > MAX_DIGIT_SUM) {
                return 0;
            }
            for (int x = 0; x < MX; x++) {
                // 如果 digSum[x] != ds，那么 f[x] = 0，否则 f[x] = sum[x]
                // 把 f[x] 的值填到 sum[x] 中，那么只需要把 digSum[x] != ds 的 sum[x] 置为 0
                if (digSum[x] != ds) {
                    sum[x] = 0;
                }
                if (x > 0) {
                    sum[x] = (sum[x] + sum[x - 1]) % MOD;
                }
            }
        }
        return sum[MX - 1];
    }
}
```

```cpp [sol-C++]
static constexpr int MX = 5001;
static constexpr int MAX_DIGIT_SUM = 31; // 4999 的数位和最大
int dig_sum[MX];

int init = [] {
    // 预处理数位和
    for (int x = 0; x < MX; x++) {
        // 去掉 x 的个位，问题变成 x / 10 的数位和，即 dig_sum[x / 10]
        dig_sum[x] = dig_sum[x / 10] + x % 10;
    }
    return 0;
}();

class Solution {
public:
    int countArrays(vector& digitSum) {
        constexpr int MOD = 1'000'000'007;
        vector sum(MX, 1); // f 的前缀和
        for (int ds : digitSum) {
            if (ds > MAX_DIGIT_SUM) {
                return 0;
            }
            for (int x = 0; x < MX; x++) {
                // 如果 dig_sum[x] != ds，那么 f[x] = 0，否则 f[x] = sum[x]
                // 把 f[x] 的值填到 sum[x] 中，那么只需要把 dig_sum[x] != ds 的 sum[x] 置为 0
                if (dig_sum[x] != ds) {
                    sum[x] = 0;
                }
                if (x > 0) {
                    sum[x] = (sum[x] + sum[x - 1]) % MOD;
                }
            }
        }
        return sum[MX - 1];
    }
};
```

```go [sol-Go]
const mx = 5001
const maxDigitSum = 31 // 4999 的数位和最大
var digSum [mx]int

func init() {
	// 预处理数位和
	for x := range digSum {
		// 去掉 x 的个位，问题变成 x/10 的数位和，即 digSum[x/10]
		digSum[x] = digSum[x/10] + x%10
	}
}

func countArrays(digitSum []int) int {
	const mod = 1_000_000_007
	sum := [mx]int{} // f 的前缀和
	for i := range sum {
		sum[i] = 1
	}
	for _, ds := range digitSum {
		if ds > maxDigitSum {
			return 0
		}
		for x := range mx {
			// 如果 digSum[x] != ds，那么 f[x] = 0，否则 f[x] = sum[x]
			// 把 f[x] 的值填到 sum[x] 中，那么只需要把 digSum[x] != ds 的 sum[x] 置为 0
			if digSum[x] != ds {
				sum[x] = 0
			}
			if x > 0 {
				sum[x] = (sum[x] + sum[x-1]) % mod
			}
		}
	}
	return sum[mx-1]
}
```

#### 复杂度分析

不计入预处理的时间和空间。

- 时间复杂度：$\mathcal{O}(nU)$，其中 $n$ 是 $\textit{digitSum}$ 的长度，$U=5000$。
- 空间复杂度：$\mathcal{O}(U)$。

## 方法二：双指针优化 DP

示例 1 的 $\textit{digitSum} = [25,1]$：

- 数位和为 $25$ 的数字为 $a=[799,889,898,979,988,997]$。
- 数位和为 $1$ 的数字为 $b=[1,10,100,1000]$。

我们其实只需考虑数组 $a$ 和 $b$ 中的数字如何转移，无需考虑 $[0,5000]$ 中的所有数字，从而减少计算量。

具体地，枚举 $b$ 中的数字 $x$，对于 $a$ 中所有 $\le x$ 的数字 $y$，我们需要知道，以 $y$ 结尾的有效数组的个数 $f[y]$ 是多少，从而算出以 $x$ 结尾的有效数组的个数 $f[x]$，即

$$
f[x] = \sum_{y\in a\ \wedge\ y\le x} f[y]
$$

如果 $a$ 和 $b$ 都是递增的，那么上述过程可以用双指针优化，具体见代码。

```py [sol-Python3]
MOD = 1_000_000_007
MX = 5001
MAX_DIGIT_SUM = 31  # 4999 的数位和最大
sum_to_nums = [[] for _ in range(MAX_DIGIT_SUM + 1)]
dig_sum = [0] * MX
for x in range(MX):
    # 去掉 x 的个位，问题变成 x // 10 的数位和，即 dig_sum[x // 10]
    dig_sum[x] = dig_sum[x // 10] + x % 10
    sum_to_nums[dig_sum[x]].append(x)

class Solution:
    def countArrays(self, digitSum: List[int]) -> int:
        f = [0] * MX  # f[x] 表示以 x 结尾的有效数组的个数
        f[0] = 1
        pre = 0

        for cur in digitSum:
            if cur > MAX_DIGIT_SUM:
                return 0
            a = sum_to_nums[pre]
            j, m = 0, len(a)
            s = 0
            for x in sum_to_nums[cur]:
                # 有效数组的前一个数只要 <= x 就行
                while j < m and a[j] <= x:
                    s += f[a[j]]
                    j += 1
                # s 现在就是以 x 结尾的有效数组的个数
                f[x] = s % MOD
            pre = cur  # 记录上一个数位和

        return sum(f[x] for x in sum_to_nums[pre]) % MOD
```

```java [sol-Java]
class Solution {
    private static final int MOD = 1_000_000_007;
    private static final int MX = 5001;
    private static final int MAX_DIGIT_SUM = 31; // 4999 的数位和最大
    private static final List[] sumToNums = new ArrayList[MAX_DIGIT_SUM + 1];
    private static boolean initialized = false;

    // 这样写比 static block 快
    public Solution() {
        if (initialized) {
            return;
        }
        initialized = true;

        Arrays.setAll(sumToNums, _ -> new ArrayList<>());
        int[] digSum = new int[MX];
        for (int x = 0; x < MX; x++) {
            // 去掉 x 的个位，问题变成 x / 10 的数位和，即 digSum[x / 10]
            digSum[x] = digSum[x / 10] + x % 10;
            sumToNums[digSum[x]].add(x);
        }
    }

    public int countArrays(int[] digitSum) {
        int[] f = new int[MX]; // f[x] 表示以 x 结尾的有效数组的个数
        f[0] = 1;
        int pre = 0;

        for (int cur : digitSum) {
            if (cur > MAX_DIGIT_SUM) {
                return 0;
            }
            List a = sumToNums[pre];
            int j = 0, m = a.size();
            int sum = 0;
            for (int x : sumToNums[cur]) {
                // 有效数组的前一个数只要 <= x 就行
                for (; j < m && a.get(j) <= x; j++) {
                    sum = (sum + f[a.get(j)]) % MOD;
                }
                // sum 现在就是以 x 结尾的有效数组的个数
                f[x] = sum;
            }
            pre = cur; // 记录上一个数位和
        }

        long ans = 0;
        for (int x : sumToNums[pre]) {
            ans += f[x];
        }
        return (int) (ans % MOD);
    }
}
```

```cpp [sol-C++]
static constexpr int MX = 5001;
static constexpr int MAX_DIGIT_SUM = 31; // 4999 的数位和最大
vector sum_to_nums[MAX_DIGIT_SUM + 1];

int init = [] {
    int dig_sum[MX]{};
    for (int x = 0; x < MX; x++) {
        // 去掉 x 的个位，问题变成 x / 10 的数位和，即 dig_sum[x / 10]
        dig_sum[x] = dig_sum[x / 10] + x % 10;
        sum_to_nums[dig_sum[x]].push_back(x);
    }
    return 0;
}();

class Solution {
public:
    int countArrays(vector& digitSum) {
        constexpr int MOD = 1'000'000'007;
        // f[x] 表示以 x 结尾的有效数组的个数
        int f[MX] = {1}; // f[0] = 1，其余 f[x] = 0 
        int pre = 0;

        for (int cur : digitSum) {
            if (cur > MAX_DIGIT_SUM) {
                return 0;
            }
            auto& a = sum_to_nums[pre];
            int j = 0, m = a.size();
            int sum = 0;
            for (int x : sum_to_nums[cur]) {
                // 有效数组的前一个数只要 <= x 就行
                for (; j < m && a[j] <= x; j++) {
                    sum = (sum + f[a[j]]) % MOD;
                }
                // sum 现在就是以 x 结尾的有效数组的个数
                f[x] = sum;
            }
            pre = cur; // 记录上一个数位和
        }

        long long ans = 0;
        for (int x : sum_to_nums[pre]) {
            ans += f[x];
        }
        return ans % MOD;
    }
};
```

```go [sol-Go]
const mx = 5001
const maxDigitSum = 31 // 4999 的数位和最大
var sumToNums [maxDigitSum + 1][]int

func init() {
	digSum := [mx]int{}
	for x := range digSum {
		// 去掉 x 的个位，问题变成 x/10 的数位和，即 digSum[x/10]
		digSum[x] = digSum[x/10] + x%10
		sumToNums[digSum[x]] = append(sumToNums[digSum[x]], x)
	}
}

func countArrays(digitSum []int) (ans int) {
	const mod = 1_000_000_007
	f := [mx]int{1} // f[x] 表示以 x 结尾的有效数组的个数
	pre := 0

	for _, cur := range digitSum {
		if cur > maxDigitSum {
			return 0
		}
		a := sumToNums[pre]
		j, m := 0, len(a)
		sum := 0
		for _, x := range sumToNums[cur] {
			// 有效数组的前一个数只要 <= x 就行
			for ; j < m && a[j] <= x; j++ {
				sum += f[a[j]]
			}
			// sum 现在就是以 x 结尾的有效数组的个数
			f[x] = sum % mod
		}
		pre = cur // 记录上一个数位和
	}

	for _, x := range sumToNums[pre] {
		ans += f[x]
	}
	return ans % mod
}
```

#### 复杂度分析

不计入预处理的时间和空间。

- 时间复杂度：$\mathcal{O}(nV)$，其中 $n$ 是 $\textit{digitSum}$ 的长度，最多有 $V=365$ 个数的数位和相同。
- 空间复杂度：$\mathcal{O}(U)$，其中 $U = 5000$。

## 专题训练

1. 动态规划题单的「**§11.1 前缀和优化 DP**」。
2. 双指针题单的「**四、双序列双指针**」。

## 分类题单

[如何科学刷题？](https://leetcode.cn/circle/discuss/RvFUtj/)

1. [滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）](https://leetcode.cn/circle/discuss/0viNMK/)
2. [二分算法（二分答案/最小化最大值/最大化最小值/第K小）](https://leetcode.cn/circle/discuss/SqopEo/)
3. [单调栈（基础/矩形面积/贡献法/最小字典序）](https://leetcode.cn/circle/discuss/9oZFK9/)
4. [网格图（DFS/BFS/综合应用）](https://leetcode.cn/circle/discuss/YiXPXW/)
5. [位运算（基础/性质/拆位/试填/恒等式/思维）](https://leetcode.cn/circle/discuss/dHn9Vk/)
6. [图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）](https://leetcode.cn/circle/discuss/01LUak/)
7. [动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）](https://leetcode.cn/circle/discuss/tXLS3i/)
8. [常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）](https://leetcode.cn/circle/discuss/mOr1u6/)
9. [数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）](https://leetcode.cn/circle/discuss/IYT3ss/)
10. [贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）](https://leetcode.cn/circle/discuss/g6KTKL/)
11. [链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）](https://leetcode.cn/circle/discuss/K0n2gO/)
12. [字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）](https://leetcode.cn/circle/discuss/SJFwQI/)

---

## File: leetcode/biweekly/179/c/README.md

其实这题改成往上下左右四个方向移动，也能做。

写一个网格图 DFS，除了有参数 $(i,j)$ 表示当前位置外，还需要参数 $\textit{xor}$ 表示走过的格子的异或和。

每访问一个格子，就把格子的值异或到 $\textit{xor}$ 中。

移动到终点时，用 $\textit{xor}$ 更新答案的最小值。

为避免重复访问相同的状态，用 $\textit{vis}$ 数组（哈希集合）标记访问过的状态 $(i,j,\textit{xor})$。

**最优性剪枝**：如果答案已经最小（等于 $0$），那么不再搜索。

[本题视频讲解](https://www.bilibili.com/video/BV1dxXSBAE6F/?t=11m40s)，欢迎点赞关注~

```py [sol-Python3]
class Solution:
    def minCost(self, grid: List[List[int]]) -> int:
        vis = set()
        ans = inf

        def dfs(i: int, j: int, xor: int) -> None:
            nonlocal ans
            # 最优性剪枝：如果答案已经最小（等于 0），那么不再搜索
            if ans == 0 or i < 0 or j < 0 or (i, j, xor) in vis:
                return
            vis.add((i, j, xor))
            xor ^= grid[i][j]
            if i == 0 and j == 0:
                ans = min(ans, xor)
                return
            dfs(i - 1, j, xor)
            dfs(i, j - 1, xor)

        dfs(len(grid) - 1, len(grid[0]) - 1, 0)
        return ans
```

```java [sol-Java]
class Solution {
    private int ans = Integer.MAX_VALUE;

    public int minCost(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        // 异或和不会超过所有元素的 OR
        int orAll = 0;
        for (int[] row : grid) {
            for (int x : row) {
                orAll |= x;
            }
        }

        boolean[][][] vis = new boolean[m][n][orAll + 1];
        dfs(m - 1, n - 1, 0, grid, vis);
        return ans;
    }

    private void dfs(int i, int j, int xor, int[][] grid, boolean[][][] vis) {
        // 最优性剪枝：如果答案已经最小（等于 0），那么不再搜索
        if (ans == 0 || i < 0 || j < 0 || vis[i][j][xor]) {
            return;
        }
        vis[i][j][xor] = true;
        xor ^= grid[i][j];
        if (i == 0 && j == 0) {
            ans = Math.min(ans, xor);
            return;
        }
        dfs(i - 1, j, xor, grid, vis);
        dfs(i, j - 1, xor, grid, vis);
    }
}
```

```cpp [sol-C++]
class Solution {
public:
    int minCost(vector<vector>& grid) {
        int m = grid.size(), n = grid[0].size();
        // 异或和不会超过所有元素的 OR
        int or_all = 0;
        for (auto& row : grid) {
            for (int x : row) {
                or_all |= x;
            }
        }

        vector vis(m, vector(n, vector(or_all + 1)));
        int ans = INT_MAX;

        auto dfs = [&](this auto&& dfs, int i, int j, int xor_val) -> void {
            // 最优性剪枝：如果答案已经最小（等于 0），那么不再搜索
            if (ans == 0 || i < 0 || j < 0 || vis[i][j][xor_val]) {
                return;
            }
            vis[i][j][xor_val] = true;
            xor_val ^= grid[i][j];
            if (i == 0 && j == 0) {
                ans = min(ans, xor_val);
                return;
            }
            dfs(i - 1, j, xor_val);
            dfs(i, j - 1, xor_val);
        };

        dfs(m - 1, n - 1, 0);
        return ans;
    }
};
```

```go [sol-Go]
func minCost(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	// 异或和不会超过所有元素的 OR
	orAll := 0
	for _, row := range grid {
		for _, x := range row {
			orAll |= x
		}
	}

	vis := make([][][]bool, m)
	for i := range vis {
		vis[i] = make([][]bool, n)
		for j := range vis[i] {
			vis[i][j] = make([]bool, orAll+1)
		}
	}
	ans := math.MaxInt

	var dfs func(int, int, int)
	dfs = func(i, j, xor int) {
		// 最优性剪枝：如果答案已经最小（等于 0），那么不再搜索
		if ans == 0 || i < 0 || j < 0 || vis[i][j][xor] {
			return
		}
		vis[i][j][xor] = true
		xor ^= grid[i][j]
		if i == 0 && j == 0 {
			ans = min(ans, xor)
			return
		}
		dfs(i-1, j, xor)
		dfs(i, j-1, xor)
	}

	dfs(m-1, n-1, 0)
	return ans
}
```

#### 复杂度分析

- 时间复杂度：$\mathcal{O}(mnU)$，其中 $m$ 和 $n$ 分别是 $\textit{grid}$ 的行数和列数，$U=\max(\textit{grid})$。
- 空间复杂度：$\mathcal{O}(mnU)$。

## 分类题单

[如何科学刷题？](https://leetcode.cn/circle/discuss/RvFUtj/)

1. [滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）](https://leetcode.cn/circle/discuss/0viNMK/)
2. [二分算法（二分答案/最小化最大值/最大化最小值/第K小）](https://leetcode.cn/circle/discuss/SqopEo/)
3. [单调栈（基础/矩形面积/贡献法/最小字典序）](https://leetcode.cn/circle/discuss/9oZFK9/)
4. [网格图（DFS/BFS/综合应用）](https://leetcode.cn/circle/discuss/YiXPXW/)
5. [位运算（基础/性质/拆位/试填/恒等式/思维）](https://leetcode.cn/circle/discuss/dHn9Vk/)
6. [图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）](https://leetcode.cn/circle/discuss/01LUak/)
7. [动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）](https://leetcode.cn/circle/discuss/tXLS3i/)
8. [常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）](https://leetcode.cn/circle/discuss/mOr1u6/)
9. [数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）](https://leetcode.cn/circle/discuss/IYT3ss/)
10. [贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）](https://leetcode.cn/circle/discuss/g6KTKL/)
11. [链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）](https://leetcode.cn/circle/discuss/K0n2gO/)
12. [字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）](https://leetcode.cn/circle/discuss/SJFwQI/)

---

## File: leetcode/biweekly/179/b/README.md

一旦我们确定了被 $\textit{pos}$ 看到的 $k$ 个人，那么：

- 这 $k$ 个人的方向是唯一确定的：在 $\textit{pos}$ 左边的人的方向为 $\texttt{L}$，在 $\textit{pos}$ 右边的人的方向为 $\texttt{R}$。
- 其余 $n-1-k$ 个人不可见，方向也是唯一确定的：在 $\textit{pos}$ 左边的人的方向为 $\texttt{R}$，在 $\textit{pos}$ 右边的人的方向为 $\texttt{L}$。

从 $n-1$ 个人中选 $k$ 个人有 $C(n-1,k)$ 种方案，每种方案，这 $n-1$ 个人的方向都是唯一确定的，而 $\textit{pos}$ 向左向右都可以，有 $2$ 种方案。所以一共有

$$
2\cdot C(n-1,k)
$$

种方案。

由于 $n$ 和 $k$ 都很大，需要**预处理阶乘及其逆元**，从而快速计算组合数。代码模板见 [模运算的世界：当加减乘除遇上取模](https://leetcode.cn/circle/discuss/mDfnkW/)。

[本题视频讲解](https://www.bilibili.com/video/BV1dxXSBAE6F/?t=4m31s)，欢迎点赞关注~

```py [sol-Python3]
class Solution:
    def countVisiblePeople(self, n: int, pos: int, k: int) -> int:
        # 这样写很慢，预处理的写法见另一份代码【Python3 预处理】
        return comb(n - 1, k) * 2 % 1_000_000_007
```

```py [sol-Python3 预处理]
MOD = 1_000_000_007
MX = 100_001

fac = [0] * MX  # fac[i] = i!
fac[0] = 1
for i in range(1, MX):
    fac[i] = fac[i - 1] * i % MOD

inv_f = [0] * MX  # inv_f[i] = i!^-1
inv_f[-1] = pow(fac[-1], -1, MOD)
for i in range(MX - 1, 0, -1):
    inv_f[i - 1] = inv_f[i] * i % MOD

# 从 n 个数中选 m 个数的方案数
def comb(n: int, m: int) -> int:
    return fac[n] * inv_f[m] * inv_f[n - m] % MOD

class Solution:
    def countVisiblePeople(self, n: int, pos: int, k: int) -> int:
        # 把预处理的逻辑写在 class 外面，这样只会初始化一次
        return comb(n - 1, k) * 2 % MOD
```

```java [sol-Java]
class Solution {
    private static final int MOD = 1_000_000_007;
    private static final int MX = 100_001;

    private static final long[] F = new long[MX]; // F[i] = i!
    private static final long[] INV_F = new long[MX]; // INV_F[i] = i!^-1 = pow(i!, MOD-2)

    private static boolean initialized = false;

    // 这样写比 static block 快
    public Solution() {
        if (initialized) {
            return;
        }
        initialized = true;

        F[0] = 1;
        for (int i = 1; i < MX; i++) {
            F[i] = F[i - 1] * i % MOD;
        }

        INV_F[MX - 1] = pow(F[MX - 1], MOD - 2);
        for (int i = MX - 1; i > 0; i--) {
            INV_F[i - 1] = INV_F[i] * i % MOD;
        }
    }

    private long pow(long x, int n) {
        long res = 1;
        for (; n > 0; n /= 2) {
            if (n % 2 > 0) {
                res = res * x % MOD;
            }
            x = x * x % MOD;
        }
        return res;
    }

    // 从 n 个数中选 m 个数的方案数
    private long comb(int n, int m) {
        return F[n] * INV_F[m] % MOD * INV_F[n - m] % MOD;
    }

    public int countVisiblePeople(int n, int pos, int k) {
        return (int) (comb(n - 1, k) * 2 % MOD);
    }
}
```

```cpp [sol-C++]
const int MOD = 1'000'000'007;
const int MX = 100'001; // 根据题目数据范围修改

long long F[MX]; // F[i] = i!
long long INV_F[MX]; // INV_F[i] = i!^-1 = qpow(i!, MOD-2)

long long qpow(long long x, int n) {
    long long res = 1;
    for (; n; n /= 2) {
        if (n % 2) {
            res = res * x % MOD;
        }
        x = x * x % MOD;
    }
    return res;
}

auto init = [] {
    F[0] = 1;
    for (int i = 1; i < MX; i++) {
        F[i] = F[i - 1] * i % MOD;
    }

    INV_F[MX - 1] = qpow(F[MX - 1], MOD - 2);
    for (int i = MX - 1; i; i--) {
        INV_F[i - 1] = INV_F[i] * i % MOD;
    }
    return 0;
}();

// 从 n 个数中选 m 个数的方案数
long long comb(int n, int m) {
    return F[n] * INV_F[m] % MOD * INV_F[n - m] % MOD;
}

class Solution {
public:
    int countVisiblePeople(int n, int, int k) {
        return comb(n - 1, k) * 2 % MOD;
    }
};
```

```go [sol-Go]
const mod = 1_000_000_007
const mx = 100_001

var fac [mx]int  // fac[i] = i!
var invF [mx]int // invF[i] = i!^-1 = pow(i!, mod-2)

func init() {
    fac[0] = 1
    for i := 1; i < mx; i++ {
        fac[i] = fac[i-1] * i % mod
    }

    invF[mx-1] = pow(fac[mx-1], mod-2)
    for i := mx - 1; i > 0; i-- {
        invF[i-1] = invF[i] * i % mod
    }
}

func pow(x, n int) int {
    res := 1
    for ; n > 0; n /= 2 {
        if n%2 > 0 {
            res = res * x % mod
        }
        x = x * x % mod
    }
    return res
}

// 从 n 个数中选 m 个数的方案数
func comb(n, m int) int {
    if m < 0 || m > n {
        return 0
    }
    return fac[n] * invF[m] % mod * invF[n-m] % mod
}

func countVisiblePeople(n, _, k int) int {
    return comb(n-1, k) * 2 % mod
}
```

#### 复杂度分析

不计入预处理的时间和空间。

- 时间复杂度：$\mathcal{O}(1)$。
- 空间复杂度：$\mathcal{O}(1)$。

## 专题训练

见下面数学题单的「**§2.2 组合计数**」。

## 分类题单

[如何科学刷题？](https://leetcode.cn/circle/discuss/RvFUtj/)

1. [滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）](https://leetcode.cn/circle/discuss/0viNMK/)
2. [二分算法（二分答案/最小化最大值/最大化最小值/第K小）](https://leetcode.cn/circle/discuss/SqopEo/)
3. [单调栈（基础/矩形面积/贡献法/最小字典序）](https://leetcode.cn/circle/discuss/9oZFK9/)
4. [网格图（DFS/BFS/综合应用）](https://leetcode.cn/circle/discuss/YiXPXW/)
5. [位运算（基础/性质/拆位/试填/恒等式/思维）](https://leetcode.cn/circle/discuss/dHn9Vk/)
6. [图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）](https://leetcode.cn/circle/discuss/01LUak/)
7. [动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）](https://leetcode.cn/circle/discuss/tXLS3i/)
8. [常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）](https://leetcode.cn/circle/discuss/mOr1u6/)
9. [数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）](https://leetcode.cn/circle/discuss/IYT3ss/)
10. [贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）](https://leetcode.cn/circle/discuss/g6KTKL/)
11. [链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）](https://leetcode.cn/circle/discuss/K0n2gO/)
12. [字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）](https://leetcode.cn/circle/discuss/SJFwQI/)

---

## File: leetcode/biweekly/179/a/README.md

在遍历 $\textit{nums}$ 的过程中，维护元素 $x$ 上一次出现的位置 $\textit{last}[x]$。

- 遍历到 $\textit{nums}[i] = 1$ 时，我们需要知道上一个 $2$ 的位置 $j = \textit{last}[2]$，用 $i-j$ 更新答案的最小值。
- 遍历到 $\textit{nums}[i] = 2$ 时，我们需要知道上一个 $1$ 的位置 $j = \textit{last}[1]$，用 $i-j$ 更新答案的最小值。

> 注：无需找 $i$ 右边的 $j$，因为我们会继续遍历，遍历到 $j$ 那个位置时，它会去找左边的 $i$。

[本题视频讲解](https://www.bilibili.com/video/BV1dxXSBAE6F/)，欢迎点赞关注~

```py [sol-Python3]
class Solution:
    def minAbsoluteDifference(self, nums: List[int]) -> int:
        ans = inf
        last = [-inf] * 2  # last[x] 表示 x+1 上一次出现的位置

        for i, x in enumerate(nums):
            if x > 0:
                # 如果 x 是 1，那么找上一个 2 的位置
                # 如果 x 是 2，那么找上一个 1 的位置
                x -= 1
                ans = min(ans, i - last[x ^ 1])
                last[x] = i

        return ans if ans < inf else -1
```

```java [sol-Java]
class Solution {
    public int minAbsoluteDifference(int[] nums) {
        int n = nums.length;
        int ans = n;
        // last[x] 表示 x+1 上一次出现的位置
        int[] last = {-n, -n}; // i - (-n) >= n，不会让 ans 变小

        for (int i = 0; i < nums.length; i++) {
            int x = nums[i];
            if (x > 0) {
                // 如果 x 是 1，那么找上一个 2 的位置
                // 如果 x 是 2，那么找上一个 1 的位置
                x--;
                ans = Math.min(ans, i - last[x ^ 1]);
                last[x] = i;
            }
        }

        return ans == n ? -1 : ans;
    }
}
```

```cpp [sol-C++]
class Solution {
public:
    int minAbsoluteDifference(vector& nums) {
        int n = nums.size();
        int ans = n;
        // last[x] 表示 x+1 上一次出现的位置
        int last[2] = {-n, -n}; // i - (-n) >= n，不会让 ans 变小

        for (int i = 0; i < nums.size(); i++) {
            int x = nums[i];
            if (x > 0) {
                // 如果 x 是 1，那么找上一个 2 的位置
                // 如果 x 是 2，那么找上一个 1 的位置
                x--;
                ans = min(ans, i - last[x ^ 1]);
                last[x] = i;
            }
        }

        return ans == n ? -1 : ans;
    }
};
```

```go [sol-Go]
func minAbsoluteDifference(nums []int) int {
	n := len(nums)
	ans := n
	// last[x] 表示 x+1 上一次出现的位置
	last := [2]int{-n, -n} // i - (-n) >= n，不会让 ans 变小

	for i, x := range nums {
		if x > 0 {
			// 如果 x 是 1，那么找上一个 2 的位置
			// 如果 x 是 2，那么找上一个 1 的位置
			x--
			ans = min(ans, i-last[x^1])
			last[x] = i
		}
	}

	if ans == n {
		return -1
	}
	return ans
}
```

#### 复杂度分析

- 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{nums}$ 的长度。
- 空间复杂度：$\mathcal{O}(1)$。

## 专题训练

见下面数据结构题单的「**§0.1 枚举右，维护左**」。

## 分类题单

[如何科学刷题？](https://leetcode.cn/circle/discuss/RvFUtj/)

1. [滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）](https://leetcode.cn/circle/discuss/0viNMK/)
2. [二分算法（二分答案/最小化最大值/最大化最小值/第K小）](https://leetcode.cn/circle/discuss/SqopEo/)
3. [单调栈（基础/矩形面积/贡献法/最小字典序）](https://leetcode.cn/circle/discuss/9oZFK9/)
4. [网格图（DFS/BFS/综合应用）](https://leetcode.cn/circle/discuss/YiXPXW/)
5. [位运算（基础/性质/拆位/试填/恒等式/思维）](https://leetcode.cn/circle/discuss/dHn9Vk/)
6. [图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）](https://leetcode.cn/circle/discuss/01LUak/)
7. [动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）](https://leetcode.cn/circle/discuss/tXLS3i/)
8. [常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）](https://leetcode.cn/circle/discuss/mOr1u6/)
9. [数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）](https://leetcode.cn/circle/discuss/IYT3ss/)
10. [贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）](https://leetcode.cn/circle/discuss/g6KTKL/)
11. [链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）](https://leetcode.cn/circle/discuss/K0n2gO/)
12. [字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）](https://leetcode.cn/circle/discuss/SJFwQI/)

---

## File: leetcode/biweekly/179/README.md

# 力扣双周赛 179 题解 - 灵茶山艾府 - 灵神

【题单+刷题路线】https://leetcode.cn/circle/discuss/RvFUtj/

本场比赛题解 + Python/Java/C++/Go 代码：
- Q1 https://leetcode.cn/problems/minimum-absolute-difference-between-two-values/solution/on-zuo-fa-mei-ju-you-wei-hu-zuo-pythonja-4kxq/
- Q2 https://leetcode.cn/problems/direction-assignments-with-exactly-k-visible-people/solution/nao-jin-ji-zhuan-wan-da-an-yu-pos-wu-gua-s45z/
- Q3 https://leetcode.cn/problems/minimum-xor-path-in-a-grid/solution/wang-ge-tu-dfspythonjavacgo-by-endlessch-c6b9/
- Q4 https://leetcode.cn/problems/count-non-decreasing-arrays-with-given-digit-sums/solution/liang-chong-fang-fa-qian-zhui-he-you-hua-dndq/

[本题视频讲解](https://www.bilibili.com/video/BV1dxXSBAE6F/)，欢迎点赞关注~

比赛地址：https://leetcode.cn/contest/biweekly-contest-179/

---

## File: leetcode/biweekly/178/d/README.md

**前置知识**：

1. [数位 DP v1.0 模板讲解](https://www.bilibili.com/video/BV1rS4y1s721/?t=19m36s)
2. [数位 DP v2.0 模板讲解](https://www.bilibili.com/video/BV1Fg4y1Q7wv/?t=31m28s)（上下界数位 DP）

对于本题，需要在模板的基础上，添加三个参数：

- $\textit{digitSum}$，表示已填数字之和（数位和）。
- $\textit{prev}$，表示上一个填的数字（$i-1$ 填的数字）。
- $\textit{state}$，表示已填数字的状态：
   - $0$，表示已经填了至多一个数（不含前导零）。
   - $1$，表示已填数字是严格递增的。
   - $2$，表示已填数字是严格递减的。
   - $3$，表示已填数字不是好数。

递归入口：$\textit{digitSum} = \textit{prev} = \textit{state} = 0$。

在递归的过程中，$\textit{state}$ 变化如下：

- 如果 $\textit{state} = 0$：
  - 在填了至多一个数的情况下，如果之前填过数，那么填的数一定非零。所以，我们可以根据 $\textit{prev}$ 是否为 $0$，判断之前是否填过数。
  - 如果 $\textit{prev} = 0$，说明之前没有填过数，那么状态仍然为 $0$。
  - 如果 $\textit{prev} > 0$，说明之前填过数，那么把当前填的数字 $d$ 和上一个填的数字 $\textit{prev}$ 比大小：
      - 如果 $d > \textit{prev}$，新状态为 $1$。
      - 如果 $d < \textit{prev}$，新状态为 $2$。
      - 如果 $d = \textit{prev}$，新状态为 $3$。
- 如果 $\textit{state} = 1$：
  - 如果 $d\le \textit{prev}$，新状态为 $3$，否则不变。
- 如果 $\textit{state} = 2$：
  - 如果 $d\ge \textit{prev}$，新状态为 $3$，否则不变。
- 如果 $\textit{state} = 3$：
  - 状态不变。

递归边界：如果 $\textit{state} \ne 3$，或者 $\textit{digitSum}$ 是好数，那么找到了一个合法方案（奇妙数），返回 $1$；否则返回 $0$。

[本题视频讲解](https://www.bilibili.com/video/BV111wTzQEbp/?t=13m6s)，欢迎点赞关注~

## 优化前

```
/* Detailed source-code truncated for AI context efficiency. */
```

```
/* Detailed source-code truncated for AI context efficiency. */
```

```
/* Detailed source-code truncated for AI context efficiency. */
```

```
/* Detailed source-code truncated for AI context efficiency. */
```

#### 复杂度分析

- 时间复杂度：$\mathcal{O}(D^3\log^2 r)$，其中 $D=10$。由于每个状态只会计算一次，动态规划的时间复杂度 $=$ 状态个数 $\times$ 单个状态的计算时间。本题状态个数等于 $\mathcal{O}(D^2\log^2 r)$，单个状态的计算时间为 $\mathcal{O}(D)$，所以总的时间复杂度为 $\mathcal{O}(D^3\log^2 r)$。
- 空间复杂度：$\mathcal{O}(D^2\log^2 r)$。保存多少状态，就需要多少空间。

## 优化

原问题（奇妙数的个数）可以拆分成两个计数问题：

1. 数位和是好数的数（这个数是不是好数都可以）。
2. 数位和不是好数的数，那么这个数必须是好数。

第一个问题，是一个（相比优化前）更简单的数位 DP。我们只需 $\textit{digitSum}$ 这个参数，在递归边界判断 $\textit{digitSum}$ 是否为好数即可。

第二个问题，我们可以直接枚举所有的好数。怎么枚举？

由于好数是严格递增或者严格递减的，所以**各个数位互不相同**。我们可以枚举 $\{0,1,2,\ldots,9\}$ 的非空**子集**，把子集排成严格递减或者严格递增，就枚举了所有的好数。注意严格递增的好数不能包含 $0$（无前导零）。

如何枚举子集？见 [78. 子集](https://leetcode.cn/problems/subsets/)，下面用的是 [我的题解](https://leetcode.cn/problems/subsets/solutions/2059409/hui-su-bu-hui-xie-tao-lu-zai-ci-pythonja-8tkl/) 的方法三。

```
/* Detailed source-code truncated for AI context efficiency. */
```

```
/* Detailed source-code truncated for AI context efficiency. */
```

```
/* Detailed source-code truncated for AI context efficiency. */
```

```
/* Detailed source-code truncated for AI context efficiency. */
```

#### 复杂度分析

不计入预处理的时间和空间。

- 时间复杂度：$\mathcal{O}(D^2\log^2 r)$，其中 $D=10$。由于每个状态只会计算一次，动态规划的时间复杂度 $=$ 状态个数 $\times$ 单个状态的计算时间。本题状态个数等于 $\mathcal{O}(D\log^2 r)$，单个状态的计算时间为 $\mathcal{O}(D)$，所以总的时间复杂度为 $\mathcal{O}(D^2\log^2 r)$。
- 空间复杂度：$\mathcal{O}(D\log^2 r)$。保存多少状态，就需要多少空间。

## 专题训练

见下面动态规划题单的「**十、数位 DP**」。

## 分类题单

[如何科学刷题？](https://leetcode.cn/circle/discuss/RvFUtj/)

1. [滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）](https://leetcode.cn/circle/discuss/0viNMK/)
2. [二分算法（二分答案/最小化最大值/最大化最小值/第K小）](https://leetcode.cn/circle/discuss/SqopEo/)
3. [单调栈（基础/矩形面积/贡献法/最小字典序）](https://leetcode.cn/circle/discuss/9oZFK9/)
4. [网格图（DFS/BFS/综合应用）](https://leetcode.cn/circle/discuss/YiXPXW/)
5. [位运算（基础/性质/拆位/试填/恒等式/思维）](https://leetcode.cn/circle/discuss/dHn9Vk/)
6. [图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）](https://leetcode.cn/circle/discuss/01LUak/)
7. [动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）](https://leetcode.cn/circle/discuss/tXLS3i/)
8. [常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）](https://leetcode.cn/circle/discuss/mOr1u6/)
9. [数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）](https://leetcode.cn/circle/discuss/IYT3ss/)
10. [贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）](https://leetcode.cn/circle/discuss/g6KTKL/)
11. [链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）](https://leetcode.cn/circle/discuss/K0n2gO/)
12. [字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）](https://leetcode.cn/circle/discuss/SJFwQI/)

---

## File: leetcode/biweekly/178/c/README.md

由于在同一个数组内交换是免费的，我们可以把数组视作**无序集合**，里面的元素是什么顺序都可以。

于是问题转化成：

- 给你两个大小都为 $n$ 的集合 $A$ 和 $B$。每次操作，从两个集合中各选一个数，交换。最少交换多少次，可以让 $A=B$？

首先，每种元素的**总**出现次数必须是**偶数**，不然无法均分。

否则可以均分。比如元素 $x$ 在集合 $A$ 中出现 $8$ 次，在集合 $B$ 中出现 $2$ 次，一共有 $10$ 个 $x$。交换后，需要满足两个集合各有 $5$ 个 $x$，也就是把 $A$ 中的 $3$ 个 $x$ 与 $B$ 中的另外 $3$ 个数交换（交换的数是集合 $A$ 需要的数），交换 $3$ 次。

定义 $\textit{diff}[x]$ 表示元素 $x$ 在集合 $A$ 中的出现次数，减去 $x$ 在集合 $B$ 中的出现次数。

我们需要把 $\textit{diff}[x]$ 变成 $0$，这样两个集合中的元素 $x$ 的个数就相等了。

由于两个集合的大小都是 $n$，根据 $\textit{diff}$ 的定义，$\textit{diff}$ 的总和（出现次数之差的总和）是 $n-n=0$。换句话说，$\textit{diff}$ 中的正数之和等于负数之和的绝对值。**集合 $A$ 多出的数，恰好也是集合 $B$ 多出的数**。把这些数交换，即可让 $A=B$。由于交换一次，可以让 $\textit{diff}[x]$ 中的正数之和减少 $1-(-1) = 2$，所以交换次数等于 $\textit{diff}$ 中的正数之和除以 $2$。在上面的例子中，$\textit{diff}[x]=6$，需要交换 $\dfrac{6}{2} = 3$ 次。

[本题视频讲解](https://www.bilibili.com/video/BV111wTzQEbp/)，欢迎点赞关注~

```py [sol-Python3]
class Solution:
    def minCost(self, nums1: List[int], nums2: List[int]) -> int:
        diff = Counter(nums1)
        diff.subtract(nums2)

        ans = 0
        for d in diff.values():
            if d % 2:
                return -1
            if d > 0:
                ans += d
        return ans // 2
```

```java [sol-Java]
class Solution {
    public int minCost(int[] nums1, int[] nums2) {
        Map diff = new HashMap<>(); // 更快的写法见【Java 数组】
        for (int x : nums1) {
            diff.merge(x, 1, Integer::sum); // diff[x]++
        }
        for (int x : nums2) {
            diff.merge(x, -1, Integer::sum); // diff[x]--
        }

        int ans = 0;
        for (int d : diff.values()) {
            if (d % 2 != 0) {
                return -1;
            }
            if (d > 0) {
                ans += d;
            }
        }
        return ans / 2;
    }
}
```

```java [sol-Java 数组]
class Solution {
    public int minCost(int[] nums1, int[] nums2) {
        int mx = 0;
        for (int x : nums1) {
            mx = Math.max(mx, x);
        }
        for (int x : nums2) {
            mx = Math.max(mx, x);
        }

        int[] diff = new int[mx + 1];
        for (int x : nums1) {
            diff[x]++;
        }
        for (int x : nums2) {
            diff[x]--;
        }

        int ans = 0;
        for (int d : diff) {
            if (d % 2 != 0) {
                return -1;
            }
            if (d > 0) {
                ans += d;
            }
        }
        return ans / 2;
    }
}
```

```cpp [sol-C++]
class Solution {
public:
    int minCost(vector& nums1, vector& nums2) {
        unordered_map diff;
        for (int x : nums1) {
            diff[x]++;
        }
        for (int x : nums2) {
            diff[x]--;
        }

        int ans = 0;
        for (auto& [_, d] : diff) {
            if (d % 2) {
                return -1;
            }
            if (d > 0) {
                ans += d;
            }
        }
        return ans / 2;
    }
};
```

```go [sol-Go]
func minCost(nums1, nums2 []int) (ans int) {
	diff := map[int]int{}
	for _, x := range nums1 {
		diff[x]++
	}
	for _, x := range nums2 {
		diff[x]--
	}

	for _, d := range diff {
		if d%2 != 0 {
			return -1
		}
		if d > 0 {
			ans += d
		}
	}
	return ans / 2
}
```

#### 复杂度分析

- 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{nums}_1$ 的长度。
- 空间复杂度：$\mathcal{O}(n)$。

## 分类题单

[如何科学刷题？](https://leetcode.cn/circle/discuss/RvFUtj/)

1. [滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）](https://leetcode.cn/circle/discuss/0viNMK/)
2. [二分算法（二分答案/最小化最大值/最大化最小值/第K小）](https://leetcode.cn/circle/discuss/SqopEo/)
3. [单调栈（基础/矩形面积/贡献法/最小字典序）](https://leetcode.cn/circle/discuss/9oZFK9/)
4. [网格图（DFS/BFS/综合应用）](https://leetcode.cn/circle/discuss/YiXPXW/)
5. [位运算（基础/性质/拆位/试填/恒等式/思维）](https://leetcode.cn/circle/discuss/dHn9Vk/)
6. [图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）](https://leetcode.cn/circle/discuss/01LUak/)
7. [动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）](https://leetcode.cn/circle/discuss/tXLS3i/)
8. [常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）](https://leetcode.cn/circle/discuss/mOr1u6/)
9. [数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）](https://leetcode.cn/circle/discuss/IYT3ss/)
10. [贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）](https://leetcode.cn/circle/discuss/g6KTKL/)
11. [链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）](https://leetcode.cn/circle/discuss/K0n2gO/)
12. [字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）](https://leetcode.cn/circle/discuss/SJFwQI/)