并查集 什么是并查集？ 并查集（Disjoint Set Union，DSU）数据结构，也称为联合-查找数据结构，允许你向图中添加边，并测试图中两个顶点是否相连。 由于实现非常简单，你可能更倾向于使用它来代替 DFS 计算连通分量。 核心优化 1. 路径压缩 (Path Compression) 在 find 操作中，将路径上的所有节点直接指向根节点，大大加快后续查询。 2. 按秩合并 (Unio

动态规划简介 核心思想 将大问题拆解为小问题，记录子问题的解，避免重复计算。 示例 - 青蛙 1 (Frog 1) 题目描述 https://atcoder.jp/contests/dp/tasks/dp_a 题目要求我们计算青蛙从石头 11 跳到石头 NN (N≤105N \le 10^5) 的最小总成本，已知青蛙只能跳一或两的距离。任意两个石头 ii 和 jj 之间的旅行成本由 |hi−hj

背包DP 模板 0-1 背包（倒序） N, W = map(int, input().split()) w = list(map(int, input().split())) v = list(map(int, input().split())) dp = [0] * (W + 1) for i in range(N): for j in range(W, w[i] - 1, -1):

网格路径问题 问题概述 DP 问题的一个常见原型涉及由正方形单元格组成的 2D 网格（类似于方格纸），我们需要分析”路径”。路径是一系列单元格的序列，其移动仅限于在 xx 轴的一个方向和 yy 轴的一个方向（例如，你可能只能向下或向右移动）。通常，路径还必须从网格的一个角落开始，并在另一个角落结束。问题可能要求你计算满足某些属性的路径数量，或者可能要求你在所有路径中找到某个量的最大值或最小值。

排序 竞赛中优先使用内置 sorted / list.sort（Timsort，稳定 O(nlog⁡n)O(n \log n)）；手写六大排序主要用于理解算法与应付考点。排序本身很少是考点，考点是排序后的性质——贪心按序取、双指针要求有序、二分要求有序。 arr.sort(key=lambda x: (-x[0], x[1])) # 第一维降序、第二维升序 b = sorted(a

递归与回溯 一、递归 1. 什么是递归 递归就是函数自己调用自己。把一个大的问题拆成规模更小的同类问题，直到问题小到可以直接解决为止。 一个递归函数必须包含两部分： 终止条件（base case）：什么时候不再递归，直接返回结果； 递归关系（recurrence）：如何把当前问题转化为规模更小的同类问题。 def factorial(n): if n == 0: #

例题 例题 1：Counting Haybales 来源：USACO - Haybales 给定 N 个不同位置的干草捆，有 Q 次查询，每次查询区间 [A, B] 内有多少个干草捆。 N, Q ≤ 100,000 坐标范围：0 ~ 1,000,000,000 思路： 1. 先将所有干草捆位置排序 2. 对于每次查询 [A, B]： - <= B 的个数：upper_bound(B) -

二分查找 二分搜索的核心思想是利用单调性快速缩小搜索区间。 用途：O(log⁡n)O(\log n) 定位目标——有序数组上找位置 / 单调判定函数上找边界。 原理：每次与区间中点比较，把搜索范围缩小一半。 本文分两大部分： 有序数组上的二分查找：在已排序数组中找某个值的下标或边界； 单调函数上的二分查找：在单调的布尔函数 check(x) 上找可行边界。 一、有序数组上的二分查

滑动窗口 滑动窗口通用模板 # 通用框架 l = 0 ans = 0 # 或其他初始化 for r in range(n): # 1. 将 arr[r] 加入窗口（扩展右边界） # ... # 2. 窗口不满足条件时，收缩左边界 while 不满足条件: # 移除 arr[l] # ... l += 1

优先队列 模板 import heapq pq = [] heapq.heapify(pq) # 把已有列表原地转成堆，O(n) heapq.heappush(pq, x) # 插入元素 smallest = pq[0] # 获取最小元素（不弹出） smallest = heapq.heappop(pq) # 弹出并返回最小值