题目列表

通过字符串哈希 O(1) 检验周期结合线性筛快速质因数分解贪心试除求解子串最短循环节

把每块元件的对角线看成格点之间权为 0 或 1 的边，答案即电源格点到灯泡格点的最短路，用 0-1 BFS 在 O(NM) 内求出。

枚举列0与主对角线两条素数链锁定每行的首位与第i位，行3用副对角线差值桶过滤，行0由列和反推，最后查素数表。

基于 IDA*（迭代加深搜索）与分数不等式上下界剪枝求解最优单位分数拆分。

通过体积与侧面积不等式估价、最小前缀体积与侧面积界限等多重剪枝优化深度优先搜索。

枚举总和的约数作为原棍长度，用逐根填满的回溯搜索，并靠等长去重、首块失败即失败、填满失败即失败与下标单调四类剪枝把搜索树压到可接受规模。

加法链经典题：每步只能用前面两个数之和向后延伸，要求链最短。用迭代加深 DFS + 双向界剪枝（末值翻倍够不到 n 剪掉、剩余步数翻倍够不到 n 的候选剪掉），从大到小枚举两两之和贪心逼近 n。

把最短时间拆成 A→X→Y→D 三段路线，X、Y 是两条传送带上的连续决策点；由距离函数的凸性对下车点、上车点嵌套实数三分搜索，O(log²(1/ε)) 求解。

两点 t 时刻连通等价于曼哈顿距离不超过 2t，边权取 ceil(d/2)，答案为最小生成树的最大边权。

根据凸函数点态最大值仍为凸函数的性质，在区间 [0, 1000] 上通过三分查找求上包络函数的最小值。

二分每段和的上限，用 O(n) 贪心判定能否分成不超过 m 段，总复杂度 O(n log Σa)。

二分答案：判定平均数不小于 x 的长度 ≥ L 子段是否存在，转化为前缀和减 x 后的滑动最小值判定，O(n log V)。

环状均分纸牌经典问题，建立糖果流转平衡方程，通过代数变形将环上流动代价转化为数轴上一点到各点的曼哈顿距离之和，利用中位数贪心求得最小值。

反悔贪心：作业按截止时间排序逐个接下，超出容量就丢弃学分最小的已选作业，小根堆维护 O(n log n)。

把相邻词的「首个不同字母对」建成有向图，拓扑排序还原密文字母的明文序；每一轮可选字母多于一个或成环就输出 0。

带权并查集（种类并查集）：每个点到根记录 0/1/2 三种关系，在模 3 意义下合并与查询，逐句判定假话。

边权全正的无向图单源最短路模板：堆优化 Dijkstra 按距离从小到大定型每个点，惰性删除过期堆条目，N 第一次出堆即得答案，复杂度 O(M log M)。

把道路建成无向带权图，答案即单源最短路；用堆优化的 Dijkstra 在每个点定型时松弛出边，复杂度 O((T+C)log C)。

将同一线路所有前后站点对连单向权值 1 边转化为无权图单源最短路，通过 BFS 求解最少乘车次数。

Floyd 求全源最短路，记 R(i) 为 i 到本牧场最远点的距离；枚举连接两个牧场的边 (i,j)，答案为 max(原最大直径, R(i)+|p_ip_j|+R(j)) 的最小值。

以 B 序列每个位置作为结尾维护 LCIS 长度与方案，扫描 A 序列时复用当前最优前驱，O(n²) 完成并直接输出序列。

两条 (1,1)→(n,n) 的单调路径按步数同步推进，压成反对角线上的三维 DP f[i][j]，重合格用 i≠j 去重。

枚舉子矩陣上下邊界，把列壓成一位數組後用 Kadane 求最大子段和，O(N^3) 解決二維最大子矩陣。

区间 DP：把石子排列看作连续区间，dp[l][r] 表示合并区间 [l,r] 的最小得分，枚举最后一次合并位置转移。

二维费用 0/1 背包：状态按需求上限收拢，倒序转移保证每个气缸只用一次，dp[m][n] 即两种气体均达标的最小总重。

把每对友好城市看成点 (南岸, 北岸)，两条航道相交等价于坐标逆序；按南岸排序后求北岸序列的最长不下降子序列，用 tails 数组加二分做到 O(n log n)。

基于位运算状态压缩与最少剩余候选数（MRV）启发式剪枝的 DFS 回溯搜索，求解靶形数独最高得分。

三连判定只看相邻 3 列，把每列压成 3bit 图案加 3bit 已计入标记，做 3 列滑窗的带状状压 DP。

合法划分等价于全或 T 的每一位在 A、B 中都出现；容斥数坏事件，坏事件交集用并查集压成 2^连通块数。

f(i,j) 是 y_i、y_j 的加权平均，取值有界可二分；f(i,j)≥v 变形为两个序列的比较，排序后双指针 O(n) 计数求第 k 大。

树贪心：权和恰为 k 的连通块等价于权和 ≥k 且奇偶性与 k 相同，后序遍历维护未切区域 O(1) 摘要，能切就切。

网格 BFS 求单源单汇最短路，边权为 1，墙壁不可通过。

按 kirai、daishuki、shuki 的优先级检查子串并顺序模拟气压变化。

比较分段模拟和树状数组三种维护当前序列的方法，正式主解用树状数组 kth 定位动态排名。

把棋子更新转化为长度恰好 n 的反向可达，用有向环加通向 k 的路径构造方案。

引入偏移量，把每个砝码可放左边(-w)或右边(+w)转化成带偏移的可行性背包，dp[sum]=true 为初始，统计正可达重量数。

二分查找 lower_bound，返回第一个 ≥ target 的位置，即插入位置。

逐行放置皇后，用三个数组（列、主对角线、副对角线）检测冲突，回溯搜索所有合法方案。

回溯枚举每段终点，只递归回文前缀，预处理区间回文表加速判断。

回溯生成括号组合，open < n 放左括号，close < open 放右括号，保证前缀合法。

回溯枚举每个候选数选或不选、选几次，允许重复使用当前数后再推进到下一个候选数。

回溯枚举每个数字对应的字母选择，递归层数对应数字位置，每层分支数由按键映射决定。

两次二分分别找 target 的 lower_bound 与 upper_bound-1，组合得到起止位置。

固定长度滑动窗口维护 26 维字母计数，窗口进出各一次，O(n)。

滑动窗口记录字符上次出现位置，左指针直接跳到重复字符后，O(n)。

单调递减队列保存候选下标，过期从队首删，较小候选从队尾删，O(n)。

前缀和 + 哈希表统计历史前缀出现次数，边扫边累计答案，O(n)。

排序后固定第一个数，剩余区间用双指针，跳过相同值去重，O(n²)。

双指针维护区间，面积由短板决定，每次移动较矮一侧，O(n)。

双指针：write 指针收集非零元素，剩余补零，保持非零相对顺序。

放入集合，只从 x-1 不存在的起点向后扩展，每个数至多被访问一次，均摊 O(n)。

为每个单词构造 26 字母计数 key，哈希到同一组；异位词一定有相同的字母构成。

遍历数组时用哈希表保存值到下标的映射，在线查找当前数所需的补数。

二分允许的最高城市收费，用受限 Dijkstra 检查血量能否到达终点。

用位集传递闭包统计每头牛已知强于和弱于的数量。

从节点 1 运行 SPFA，以最短路边数达到 n 判断可达负环。

用全局增量抵消统一加 q，并以三个单调队列线性取当前最长蚯蚓。

按截止时间扫描，最大堆维护已选工期；超时则用更短任务替换最长任务。

求字符串的最小周期长度。用整个字符串的最长 border 求能够生成接收片段的最短信号周期。

统计每个数值的出现次数，再把每个除数的频次累加到它的所有倍数。