算法
trie, LCA, topo(DFS, BFS), qsort v.s. merge sort
二分答案
Cpp < 的重载
如果要自定义比较语义，只需要重载<（不需要重载<=, = 或者>）。对于lower_bound，重载<内部实现不需要<=；你可能会问，你不告诉它=的语义，它怎么知道？其实它是通过”=” —> not “<” and not “>”来判断的，而”>”是可以通过”<”的实现通过某种技巧推出来的。
例子：1
2
3
4// 返回值it是迭代器
// 注意第四个参数，函数的参数得是const + &
// 函数的第一个参数表示target
auto it = lower_bound(mono_stack.begin(), mono_stack.end(), pair<int, int>{height[i], i}, [](const pair<int, int> &a, const pair<int, int> &b) {return a.first < b.first;});
升序排序/大根堆时要用<。底层逻辑是：如果 a < b 为真，则 a 排在 b 前面。
precision
在算法竞赛中，输出精度（尤其是浮点数）往往是决定 Accepted 还是 Wrong Answer 的关键细节。C++ 和 Python 在处理逻辑上有很大差异，这里为你梳理了核心用法和避坑指南。
一、 C++ 精度处理
在 C++ 中，<iomanip> 头文件是你的好伙伴。
1. 核心控制语句
- 固定小数位数：
cout << fixed << setprecision(n) << val;
这是竞赛中最常用的方式，确保小数点后正好有 $n$ 位。 - 有效数字：
cout << setprecision(n) << val;（不加fixed）
控制总的有效数字位数，通常用于科学计数法要求。 - printf 风格：
printf("%.nf", val);
简单直接，在处理大规模数据输出时性能优于cout。
2. 常见坑点
- 四舍五入的玄学：
printf和setprecision在处理“刚好在 0.5”的情况时，并不总是稳定的“四舍五入”，有时会受编译器和浮点数底层表示（IEEE 754）的影响（即“舍入到最接近的偶数”）。- 对策：如果对舍入要求极其严格，建议手动加上一个极小值
eps（如 $10^{-9}$），即printf("%.2f", val + 1e-9);。
- 对策：如果对舍入要求极其严格，建议手动加上一个极小值
- 输出 -0.00：当计算结果是一个极小的负数（如
-0.0000001）且保留两位小数输出时，可能会得到-0.00。- 对策：在输出前进行判断：
if (abs(val) < eps) val = 0;。
- 对策：在输出前进行判断：
二、 Python 精度处理
Python 的 float 默认就是双精度（相当于 C++ 的 double），语法更简洁。
1. 核心控制语句
- f-string (推荐)：
print(f"{val:.nf}") - format 函数：
print("{:.nf}".format(val)) - % 运算符：
print("%.nf" % val)
2. 常见坑点
- round() 函数的背叛：Python 的
round(x, n)采用的是 “四舍六入五成双”（Round half to even）。例如：
round(2.5)得到2，round(3.5)得到4。这在很多竞赛题目要求严格四舍五入时会白给。- 对策：使用
Decimal模块或手动处理：int(val * 10**n + 0.5) / 10**n。
- 对策：使用
- 浮点数运算误差：Python 虽然动态类型很爽，但浮点数依然存在 $0.1 + 0.2 \neq 0.3$ 的问题。
三、 综合对比与算法竞赛建议
| 特性 | C++ (double/long double) | Python (float) |
|---|---|---|
| 精度上限 | long double 可达 80/128 位 |
默认 64 位，需更高精度用 decimal 模块 |
| 默认舍入 | 趋向四舍五入（受环境影响） | 四舍六入五成双 |
| 速度 | 极快 | 较慢 |
💡 竞赛实战建议：
- 统一精度：除非内存极其紧张，否则 C++ 一律用
double，高精度需求用long double。 - 避免过早舍入：在所有计算完成之前，不要进行取整或保留小数操作，减少累积误差。
- 比较浮点数：永远不要用
if (a == b)，要用if (abs(a - b) < eps)，其中eps通常取 $10^{-8}$ 或 $10^{-9}$。 - 长整型转换：如果题目要求输出整数且涉及浮点运算，建议先
+eps再强转int，防止因为0.99999999被截断成0。
树状数组，线段树与分块
在算法竞赛（ACM/ICPC, NOI, CCPC）中，树状数组 (Binary Indexed Tree)、线段树 (Segment Tree) 和 分块 (Square Root Decomposition) 是处理区间问题的“三剑客”。
以下是这三种数据结构的详细对比：
数据结构特性对比表
| 维度 | 树状数组 (BIT) | 线段树 (Segment Tree) | 分块 (SQRT Decomposition) |
|---|---|---|---|
| 实现难度 | 极低。核心代码仅需几行（lowbit）。 |
中等。需要递归构建、PushDown/PushUp 操作。 | 低到中。逻辑直观，但边界处理（散块）需细心。 |
| 适用范围 | 较窄。主要用于点修区间查，且操作需满足可减性（如和、异或）。 | 极广。几乎能处理所有区间问题（最值、GCD、复杂懒标记）。 | 万能。不仅能处理区间，还能处理非结合律问题或配合莫队算法。 |
| 时间复杂度 | $O(\log n)$。常数极小，执行速度最快。 | $O(\log n)$。常数较大（递归开销）。 | $O(\sqrt{n})$。常数较小，但在 $10^5$ 以上数据量级可能超时。 |
| 空间复杂度 | $O(n)$。仅需一个原数组大小的额外空间。 | $O(4n)$。通常需要开 4 倍空间的数组。 | $O(n)$。仅需记录块信息，空间开销小。 |
| 常用程度 | 极高。基础区间问题的首选方案。 | 极高。竞赛中区间问题的“标准答案”。 | 高。作为暴力优化的最后手段或处理黑科技题目。 |
| 扩展性 | 较差。虽然能改区间修改，但逻辑复杂。 | 极强。可扩展为动态开点、持久化（主席树）。 | 强。对数据分布和操作类型几乎没有限制。 |
算法竞赛中的“避坑”与选择建议
1. 什么时候选树状数组？
- 追求速度：当题目时限非常紧（如 $10^6$ 数据量），树状数组的常数优势巨大。
- 求逆序对：这是树状数组最经典的用法。
- 维度增加：在处理二维或三维空间问题时，树状数组的实现远比多维线段树简单。
2. 什么时候选线段树？
- 区间修改 + 区间查询：这是线段树的统治区，通过
Lazy Tag（懒标记）可以高效处理。 - 非可减性维护：比如维护区间的最大值（RMQ），由于最大值不满足可减性，树状数组处理起来很麻烦，而线段树游刃有余。
- 复杂信息合并：如维护区间最长连续上升子序列，线段树的节点合并逻辑非常清晰。
3. 什么时候选分块？
- “强制在线”且逻辑复杂：有些操作线段树难以通过标记下传实现（如区间内大于 $x$ 的数有多少个），此时分块配合块内排序或桶可以解决。
- 时间换空间：如果内存限制极其严格（如 64MB），线段树的 4 倍空间可能炸内存，分块更节省。
- 作为保底方案：在考场上如果想不出线段树的标记合并逻辑，写一个 $O(n\sqrt{n})$ 的分块通常能拿到 70%~100% 的分数。
总结建议
- 入门阶段：先练熟树状数组，再死磕线段树。
- 实战策略：能用树状数组不用线段树（快且好写）；能用线段树不用分块（稳且不被卡常）；如果题目要求太奇葩，果断上分块或莫队。
Tarjan
Tarjan 算法的核心在于通过一次 DFS 利用栈和两个关键数组 $dfn$ 和 $low$ 来挖掘图的结构特征。
1. 核心定义：$dfn$ 与 $low$
这是 Tarjan 算法的灵魂，理解了这两个数组，算法就理解了一半：
- $dfn[u]$：时间戳。节点 $u$ 在 DFS 过程中被访问的先后顺序（从 1 开始递增）。
- $low[u]$：追溯值。节点 $u$ 通过树枝边或特定的反向边能够回溯到的 $dfn$ 最小的节点编号。
- 它代表了节点 $u$ 所在的连通结构的“最高点”。
2. 三个 Tarjan 算法对比总结
A. 有向图：强连通分量 (SCC)
- 目的：找极大的子图，使得其中任意两点可互相到达。
- $low$ 更新时机：
- 遇到未访问节点 $v$：递归后，$low[u] = \min(low[u], low[v])$。
- 遇到已访问且在栈中的节点 $v$：$low[u] = \min(low[u], dfn[v])$。
- 判断时机：
- 当 DFS 回溯时，如果 $dfn[u] == low[u]$，说明 $u$ 是该 SCC 的“根”。此时将栈中 $u$ 及其上方的节点全部弹出，这些节点构成一个 SCC。
B. 无向图：割点与点双连通分量 (v-BCC)
- 目的：找删去后会使原图不连通的点。
- $low$ 更新时机：
- 遇到未访问节点 $v$：递归后，$low[u] = \min(low[u], low[v])$。
- 遇到已访问且不是父节点的节点 $v$：$low[u] = \min(low[u], dfn[v])$。
- 判断条件：
- 非根节点 $u$：存在一个子节点 $v$，使得 $low[v] \ge dfn[u]$（说明 $v$ 无法绕过 $u$ 回到更高处）。
- 根节点 $u$：在 DFS 树上有两个或更多独立的子树。
C. 无向图：割边（桥）与边双连通分量 (e-BCC)
- 目的：找删去后会使原图不连通的边。
- $low$ 更新时机：与割点基本一致，但必须严格限制不通过当前输入的这条边回到父节点（处理重边时需记录边编号）。
- 判断条件：
- 对于边 $(u, v)$，如果 $low[v] > dfn[u]$，则该边为桥（说明从 $v$ 出发无论如何也回不到 $u$ 或 $u$ 以上的点）。
3. 实现中的关键细节
| 细节 | 有向图 (SCC) | 无向图 (割点/桥) |
|---|---|---|
| 栈的作用 | 记录当前可能属于同一个 SCC 的节点。 | 割点通常不强制用栈，点双/边双才需要栈存边或点。 |
| 父节点回溯 | 不需要考虑父节点。 | 必须跳过父节点（或进来的那条边），否则 $low$ 永远等于 $dfn$。 |
| 更新逻辑 | 只有在栈中的点才能更新 $low$。 | 只要不是父节点就能更新 $low$（表示存在反向边）。 |
| 判等逻辑 | $dfn == low$ 是判定 SCC 结束的标志。 | $low[v] \ge dfn[u]$ 是判定 $u$ 是割点的标志。 |
🛠️ 避坑指南：
- 重边问题：在求无向图桥时，不能简单判断
v != fa，而要记录进入 $u$ 的边 ID，防止通过重边直接回到父节点导致 $low$ 更新错误。 - 根节点特判：求割点时，DFS 的起点（根）不能用 $low[v] \ge dfn[u]$ 判断，必须看它是否有两个以上的子树。
- 多连通图：如果图不连通，需要对每个未访问的点跑一遍 Tarjan。
python自定义排序
在 Python 中，自定义排序的核心逻辑是将“复杂的对象”映射为“可比较的键”。以下是算法竞赛和日常开发中最常用的三种方式：
1. 使用 key=lambda（最常用）
这是最快捷的方法，适用于大多数基础的多维列表或对象排序。
- 基本语法：
list.sort(key=lambda x: x[0]) - 多关键字排序：如果想先按第一列升序，第一列相同时按第二列降序，可以利用元组：
1
2
3
4
5# 示例：学生列表 (名字, 分数, 年龄)
# 要求：分数降序 (-x[1])，年龄升序 (x[2])
data = [("Alice", 90, 20), ("Bob", 90, 18), ("Charlie", 85, 19)]
data.sort(key=lambda x: (-x[1], x[2]))
# 结果: [('Bob', 90, 18), ('Alice', 90, 20), ('Charlie', 85, 19)]注意：负号
-仅适用于数值类型。如果是字符串想降序，通常需要后面提到的方法。
2. 使用 functools.cmp_to_key（最强大）
当你无法简单地通过一个 key 映射来决定顺序（例如：排序规则取决于两个元素之间的逻辑关系）时，这个方法是救星。它模拟了 C++ 中 bool cmp(a, b) 的逻辑。
- 逻辑：返回负数表示
a在前，正数表示b在前，0表示相等。 - 典型场景：最大数问题（给定一组数字，拼成一个最大的数）。
1
2
3
4
5
6
7
8
9
10
11from functools import cmp_to_key
def my_cmp(a, b):
if str(a) + str(b) > str(b) + str(a):
return -1 # a 应该排在前面
else:
return 1
nums = [3, 30, 34, 5, 9]
nums.sort(key=cmp_to_key(my_cmp))
# 结果: [9, 5, 34, 3, 30] -> 拼接后最大
3. 重载类的比较运算符（工程常用）
如果你定义了一个类，并希望它在任何地方（sort, min, heapq）都能自动排序，可以直接在类内部定义 __lt__ (less than)。
- 实现细节：Python 的排序只要求实现
__lt__。1
2
3
4
5
6
7
8
9
10
11
12class Node:
def __init__(self, x, y):
self.x, self.y = x, y
def __lt__(self, other):
# 逻辑：x 越小越靠前；x 相等则 y 越大越靠前
if self.x != other.x:
return self.x < other.x
return self.y > other.y
nodes = [Node(1, 2), Node(1, 5), Node(0, 3)]
nodes.sort() # 自动调用 __lt__
💡 竞赛避坑指南
- 稳定性 (Stability)：Python 的
sort(Timsort) 是稳定的。这意味着如果两个元素 key 相同，它们的相对顺序会保持不变。你可以利用这一点进行多次排序（先排次要关键字，再排主要关键字）。 - 性能：
key函数在每个元素上只调用一次，而cmp_to_key会在每次比较时调用。在大数据量下，优先使用 lambda。 - 原地修改 vs 返回新列表：
list.sort()：原地修改，无返回值，省内存。sorted(list)：返回新列表，原列表不变。