题目列表

区间翻转 + 单点查询，用异或差分把区间翻转降成两次单点翻转，再用异或树状数组在线维护前缀异或，O((n+m) log n)。

把单词看成首字母到末字母的有向边，欧拉路径判定：非零度点弱连通，且入出度差只出现 0 与至多一对 ±1。

Tarjan 求割点与点双后按分量内割点数三分类计数：叶子点双放 1 个出口、无割点连通块任选 2 点，各块方案相乘。

Tarjan 缩点把环内收益合并为分量点权和，再在缩点 DAG 上按分量编号降序做最长路 DP，线性时间求出起点到任意酒吧的最大收益。

无权图最短路计数：BFS 按层求距离的同时递推 cnt[v]，首次到达赋 cnt[u]、同层前驱累加 cnt[u]，边算边对 100003 取模，O(N+M)。

把状态扩成 (格子, 钥匙位掩码)，在无权状态图上 BFS 求从 (1,1) 到 (n,m) 的最短路。

以环上编号最大的点拆环，用 Floyd 并入该点前的受限最短路闭合成环，再沿后继表回溯输出方案。

非树点对只能补“路径最大边权+1”的边；按边权升序并查集合并，用块大小乘积批量累计所有点对的路径最大边权，O(n log n) 求最小完全图边权和。

把病毒串建成 AC 自动机并标记危险节点，在安全节点的转移子图上拓扑判环：有环输出 TAK，无环输出 NIE。

状压 DP 用位掩码记录已用串集合并以结尾串为附加状态，转移按最大后缀-前缀重合补尾拼接，终点按长度与字典序取最小。

树上前缀异或把任意路径异或化成两端点 d 值异或，问题坍缩为序列最大异或对，再用 01 字典树 O(31n) 贪心求解。

查询词全部插入 Trie 建 AC 自动机，扫描文章只标记到达状态，再沿 fail 树自底向上合并命中，一次 O(|S|) 扫描统计出现过的查询词个数。

把全部信息插入 01-Trie，节点记录经过数与终止数；查询密码时沿路径累加终止数，走通再补上经过数减终止数，把两两前缀比较降为一次树上行走。

两段不相交子数组异或和之和：用分割点拆成前后缀各自的最大子数组异或，01-Trie 贪心求与历史前缀的最大异或后合并。

把每个数按 30→0 位序插入 01 字典树，查询时每位优先走与 x 相反的边，O(31N) 求出最大异或对。

屏蔽词建 AC 自动机，逐字符扫描并用栈平行保存字符与每个前缀的自动机状态；命中词尾就按词长整段弹出并恢复状态，均摊 O(|S| + 26·∑|t|)。

把反对称子串改写成缝隙两侧逐位互不相等，套用 Manacher 的镜像继承与右端截断，把逐缝隙暴力扩展均摊成 O(n)，按半径求和计数。

把“愿意拷贝”建成有向图，一张光盘覆盖放置者可达的所有人；bitset 传递闭包求 SCC，能到 i 的点都能被 i 反达即源分量，答案就是源分量个数。

把「所选糖果总数模 K 的余数」作为背包状态，每个余数只保留最大总和：dp[j] = max(dp[j], old[(j - a%K)%K] + a)，答案取 dp[0]。

把一次单向滑翔拆成两个方向的最长下降子序列：高度取负后就是标准 LIS，用 tails 数组按长度维护最小结尾、二分定位，每个方向 O(N log N)，两方向取较大值即为答案。

把「最长复制时间最小」转成判定问题：二分上限 L，用贪心数出 L 下最少的段数；再倒序贪心让后面的人尽量多抄，重建出前面人少抄的字典序最小方案。

外层枚举组、容量倒序、内层枚举组内物品，容量倒序保证每轮只读上一组的旧值，同组物品不会叠加。

分组背包 DP：f(i,j)=max_k f(i-1,j-k)+a[i][k] 求前 i 家恰好分 j 台的最大盈利，并用 res 记录决策 O(N) 回溯输出分配方案。

数塔 DP：自底向上递推 f(i,j)=a[i][j]+max(f(i+1,j),f(i+1,j+1))，滚动一维数组即可。

第一问最长不升子序列，第二问由 Dilworth 定理等于最长严格上升子序列；两问共用一个二分 LIS 函数，O(n log n)。

把坐标看成顶点、三种操作看成边权为 1 的边，BFS 逐层扩展，首次到达 K 的层号即最少分钟数；起点大于等于终点时答案直接是 N-K。

固定 5×5 迷宫 BFS 求唯一最短路，入队时记录前驱并兼作访问标记，到终点后回溯再反转输出路径。

棋盘上马的最少步数就是隐式无权图的单源最短路：边权全为 1，按步数分层 BFS，首次到达终点即答案。

网格 BFS：从左上角 BFS 到右下角，按层扩展，首次到达时的层号就是最少经过的格子数（含起点终点）。

把方块看成顶点、相邻且公共边无墙时连边，问题化为无向图连通分量个数与最大分量大小，一次洪水填充即可 O(mn) 求出。

三维网格建成无权图，可通行格是顶点、六方向相邻连边，BFS 入队即标记，命中 E 的层号就是最短分钟数。

弧长与弦长固定时圆心角唯一，二分求角后代弓形高公式输出偏移。

对答案二分：可行性随要求跳跃距离单调变差，判定用左端贪心扫一遍，越过 L−mid 的岩石必删以保住最后一跳，O(n log L) 求最长的最短跳跃。

取 n 的末四位作为指数，用快速幂求 2011^n mod 10^4。

枚举行区间把二维压成一维：先用列前缀和得到每列在该行区间内的和，再对这一维数组跑 Kadane 求最大子段和，O(N³)。

把分组抽象成冲突图染色：不互质就连边，一组是一个独立集，用 2^n 子集 DP 求最小染色数。

预处理每对单词的最小合法重叠增益，再按增益降序做带上界剪枝的 DFS 回溯，每词最多用两次，搜出最长接龙。

设 f(n,lo) 为把 n 拆成不小于 lo 的因子之积的方案数，按首因子 d 分类递推 f(n,lo)=1+Σf(n/d,d)（d≤√n 且 d|n），记忆化即可

链上选 n 个村建小学：前缀和定位后，“去最近学校”等价于把链切成 n 个连续段，每段代价是到中位村的距离和，O(m^3) 区间划分类 DP 直接转移。

按天同步传播就是网格上的多源 BFS：一天对应一层，每轮按当前队列长度成批出队，入队时就地标记患病格。

按 (成绩降序, 报名号升序) 排序，第 floor(m*150/100) 名的成绩即分数线，所有不低于该分数的选手构成排序前缀，一并输出。

滚动维护阶乘并高精度累加 1! 到 n! 的和。

枚举 a 用真因数和 σ(n) 判定亲和数，σ(σ(a))=a 且 σ(a)≠a 即命中。

正难则反：指定坏点后序列碎成段内同值的独立段，容斥计数，再用单调栈维护后缀最小值阶梯把转移压成 O(1)。

从每个格子沿 8 个方向 DFS 游走匹配单词，用标记记录是否已转过一次 90° 弯。

单窗口内按 b 降序排队可证最优，全体排序后退化为 0/1 分配问题，用背包式 DP 求最小完成时间。

经典 LIS 贪心表的变体：同一位置的候选值先统一评估再统一写回，避免同一位置的候选值互相接龙。

必选边先全部累加并缩成连通块，再对可选边按费用做 Kruskal 最小生成树补齐连通：缩点 + MST。

把「剩余数字多重集」当状态预处理余数分布，再按位试填，用可被 17 整除的后缀方案数逼近第 K 小数。

按列回溯放皇后，行与两条对角线各压成一个 8 位掩码，靠 avail&-avail 取最低可行行同时定出输出顺序，得到全部 92 个解。

状态二元组只有 P² 种且 P≤10007，Y≠0 时转移可逆、序列从第 1 项起纯周期（K≤P²），Y=0 时退化为一阶带尾巴；预先扫出一圈的命中位置，再用「尾巴 + 完整周期 + 残缺周期」的前缀计数 O(1) 回答每次 [L,R]。

快速排序相关计数：双树状数组维护差分实现区间加、区间和，前缀和还原区间贡献，O(m log n)。

三位评委两两排序结论的合成判定计数：把 6 种合法全序编码成位掩码，枚举判定函数 g 对每对评委结论的映射，计数一致性方案与全部方案，O(1) 枚举。

位数区间先转成数值区间 [k^(l-1), k^r)，再对数位和模 60 的分布做循环卷积快速幂，两次合法计数相减即得答案。

体积价值均不超过 100 的完全背包：同体积去重后取密度最大物品贪心装满 ⌊m/a1⌋−100 件，剩余不超过 10099 的容量交给一维完全背包修正零头，绕开 10^16 的容量上限。

利用 H[i] 是团的性质，把每个点 i 对应到团 P(i)={i}∪H[i]，用最大前驱与入度的一次比较判定 P(i) 是否被包住，未被标记的点数即极大团个数。

抛硬币移宝石的期望回返时间：把游戏看成带反射壁的随机游走，用 Kac 定理化简成几何级数，整数通分精确求值。

把终值拆成 a_i·P/q_i，公共因子藏进各 q_i 免费复用，推出答案 = ΣΩ(a_i) − n·Ω(gcd)，筛法预处理后单遍扫描求得。

基于重链剖分（树链剖分）将树上路径映射为连续区间，并使用线段树维护单点修改与路径权值和、最大值查询。

将三颗棋子的跳动建模为二叉树结构，利用最近公共祖先（LCA）思想求两状态间最少跳动次数，用批量倍增加速收缩求根。