题目列表

相邻交换算出差值 2(t_i c_j − t_j c_i)，按比值 t_i/c_i 升序排序后一次线性扫描即得最少体力。

把含数字 7 的数当作筛子做埃氏筛，预处理出全部禁报数；查询时从 x+1 扫到下一个未被标记的数，x 被标记则输出 -1。

成绩值域只有 0 到 600，用桶计数实时统计各分数人数，再从高分档向低分档累加到计划获奖人数，即得即时分数线。

并查集维护相切/相交的空洞，上下表面挂虚拟节点，平方比较后判断是否同根。

24 小时滑动窗口统计不同国籍数：船整进整出队列，国籍计数 +1/-1，减到 0 删键，答案 O(1)。

每轮所有人整体顺时针平移 m 格，10^k 轮后位置为 (x + m·10^k) mod n；只需 10^k mod n，用快速幂在 O(log k) 内求出。

Vigenère 解密即逐位模 26 减法 m = (c − k) mod 26，负数加 26 归正，密钥循环复用，大小写沿用密文。

模拟上楼：用楼梯总数的周期把指示牌数字化小，再用前缀和 O(1) 定位下一房间，逐层累加取模。

以「前 i 种花摆 j 盆的方案数」为状态，转移是长度 a_i+1 的滑动窗口和：前缀和把单格压到 O(1)，一维滚动 O(n·m) 完成计数。

对每个子表达式记录取 0/1 的填法数，用调度场双栈按优先级一次扫描、自底向上合并，O(L) 求出表达式取 0 的方案数。

固定右端点后，合法左端点只取决于它是否落在最近一家消费不超过 p 的客栈之前；一趟 O(n) 扫描按色调计数即可统计全部方案。

先取绝对值，再逐位取末位拼成反转数；负号最后拼回，原数为 0 时结果为 0。

按成绩降序、同分报名号升序排序后取第 ⌊1.5m⌋ 名的分数作分数线，再输出所有不低于分数线的选手。

环上传球计数：设 f(i,j) 为传 i 次后球在 j 手中的方案数，每步只能从左右邻居转移，答案 f(m,0)，O(mn) 递推。

用 map 计数把 n 个数压成『值 → 次数』，再按键升序输出，O(n log n)（不同值最多 1e4）。

排序后双指针贪心：每轮让最贵的纪念品与最便宜的凑组，凑不上就单独成组，交换论证保证组数最少，O(n log n)。

按花生数从大到小模拟采摘顺序，每次检查采摘后能否按时跳回路边，贪心即可；复杂度 O(MN log MN)。

位数用对数闭式一次算出，末 500 位用高精度快速幂模 10^500 求得。

递增下标 DFS 枚举全部 C(n,k) 个组合去重，对组合和试除到 sqrt(S) 判素（S ≤ 10^8），累加合法组合数。

把 n-1 次减操作看成符号模型 a1±a2±…±an，线性DP求一组可行符号，再按固定规则还原每次操作的位置。

完全背包计数：f[j] 表示用不大于当前上限的加数拆出 j 的方案数，正序枚举加数可重复，答案 f[N] 减 1。

01 背包计数：f[j] 表示和恰好为 j 的选数方案数，倒序转移统计方案。

每次只动一堆，故整局 SG 等于各堆 SG 的异或和；单堆 p 的后继是把真约数全摆上再删一个，故 SG(p)=mex(nx⊕SG(d))，nx 是全部真约数堆的异或和。

M 把一整列接到另一列尾部，列内顺序不变，名次只需整体加一个偏移：带权并查集把「前面有几艘舰」记在 front 上、列长记在根上，同列询问答 |front[i]-front[j]|-1。

期望线性性把总花费拆成相邻两门课的段费，DP 状态只需记住“上一门是否申请”与已用申请数，配合 Floyd 全源最短路 O(v^3+nm)。

把排序后的棋子间隙看成从右往左流动的石子堆，问题化为阶梯博弈，奇数段间隙异或和非零则先手必胜。

判断奇偶回答是否矛盾：把区间前缀异或化为带权并查集约束 kind[y]^kind[x]=parity，按出现顺序二分第一个矛盾位置（离散化+可撤销并查集），O(m log m)。

把「每条记录 = 一个线性等式」写成模 7 同余方程组，用高斯消元求解；3..9 天与 7 个剩余类一一对应，无解/自由元分别判 Inconsistent/Multiple。

「建 aᵢ 个棚剩 bᵢ 头牛」即同余式 x≡bᵢ (mod aᵢ)；维护不变量 x≡v (mod m) 逐条合并，由 x=v+mt 解出 t≡(b−v)·m⁻¹ (mod a)，用 pow 求模逆元，答案取最小正剩余。

把容量与残片合并成净余量，成功数、净余量都按阈值截断到 O(L·m)，再逐项做平移式概率 DP，复杂度 O(N·L·m)。

跳 t 次后两蛙位置为 (x+mt) mod L 与 (y+nt) mod L，相遇条件化为同余方程 (m-n)t ≡ y-x (mod L)：gcd 判可达性，约简后用模逆元求最小非负解。

王必须在翻开瞬间选花色，故状态取 (四堆张数, 两张王的指派) 并对王的分支取 min，自底向上逆推期望，O(15^4·25) 时间、约 10MB 空间。

剪纸博弈：每步沿格线把一张纸剪成两半，先剪出 1×1 者胜。把每张纸看作独立子游戏，SG 定理下整局 SG 为各纸 SG 的异或和；忽略会剪出 1×k 炸弹的必败剪法后，按面积递推 O(N³) 求出 sg[N][M] 是否为 0。

求 ∑gcd(i,N)：答案是积性函数，质因数分解后在每个质因子幂 p^a 上乘局部因子 p^(a-1)·(p+a(p-1))，O(√N) 单次求解。

把 3 个期望按 30 个二进制位拆开，每位的 xor/and/or 只需统计 0/1 连续段长度与前缀异或的取值次数，再用 2S-T 换算成有序对口径。

设 f[u] 为从 u 走到 N 的期望路径长，由全期望公式得 f[u]=(Σ边长+Σf[后继])/出度，DAG 上按逆拓扑序倒推一遍，时间 O(N+M)。

二项式定理通项给出系数 C(k,n)·a^n·b^m：用 math.comb 精确求组合数，两次 pow 快速幂分别取模。

轮换分解得 m=n-环数；最短方案每步分裂一个环，逆操作为 Dénes/Cayley 合并计数，答案 m!·∏ c^(c-2)/(c-1)!（模 1e9+9）。

把「每个开关最多按一次」的操作集合写成 GF(2) 线性方程组，用整数按位压缩整行做高斯消元：解数就是 2 的自由元个数次方，出现 0=1 则无解。

把每秒石头搬运写成带「外界」注入位的 65×65 矩阵，按序列长度的最小公倍数 ≤60 合成周期矩阵，再用矩阵快速幂把 t ≤ 1e8 秒压到 O(log t)。

把 x 限制在 b1 的约数上，再按质数位独立计数：每位由 gcd/lcm 条件解出一个指数区间，各位区间长度相乘即答案。

扩展欧几里得求 ax+by=1 的特解，对 b 取模即得最小正整数解（模逆元模板题）。

把 n 位全 8 数写成 8(10^n-1)/9，条件化为 10^n ≡ 1 (mod 9L/gcd(L,8))，答案即 10 的模阶，枚举 φ(m) 的因数加快速幂求出。

把 n! 的质因数分解转成逐质数统计：埃氏筛求出所有 ≤n 的质数，对每个质数 p 用勒让德公式 c_p = Σ⌊n/p^k⌋ 一次算出指数。

用位掩码抽象连通块状态，以剩余颜色数为可采纳估价函数做 IDA* 迭代加深，配合后继去重与分支排序求最少染色步数。

把两个工作变量的指数当作状态 (a,b)，用迭代加深 DFS 求最少步数，靠 a·2^rest<P 的上界剪枝和 P%gcd(a,b) 的整除剪枝把分支压到可跑。

逐日推进的可达性 DP：状态只保留云的位置和「最近 6 天雨迹」的 6 个 16 位掩码，用集合合并等价状态，判罚退化成一次位运算。

字符串改写求 10 步内最少变换次数：把规则看作有向图上的边，从 A、B 两端各做 5 层 BFS，用逆规则反向扩展，在两侧的交集里取距离和最小值。

BFS 求网格上马步最短路，首次到达草地即最少跳跃次数。

八连通网格上从起点做 BFS 求最晚被占领格子的层数，起点算第 0 周，答案即所有格子距离的最大值。

按字典序枚举移动做恰好 n 步 DFS，用「整体标记→消除→掉落」循环结算局面，再以颜色计数、同色空转、左移等价、失败记忆化四条安全剪枝压缩搜索树。

把行、列、宫的已用数字压成三个位掩码，DFS 时用 MRV 先填候选最少的空格，再用「剩余空格各填候选里最大数字」的上界剪枝，求带权数独的最大总分。

中央 8 格的“非众数格数”每步至多减 1（每次操作恰好替换 1 格），故可当 IDA* 的可采纳估价；按 A~H 迭代加深、命中即返回，即得最短且字典序最小的操作串。

把网格建模为火柴覆盖正方形的重复覆盖问题，用 IDA* 逐层加深，以最小正方形强制分支、互不相交正方形数做估价下界，求破坏所有正方形的最少抽火柴数。

每次取一段连续的书插入别处，用“坏相邻接口数除以 3 上取整”做可采纳估价，IDA* 迭代加深到深度 4 求最少操作数。

把（人，箱子）当作状态建图，边权为（推箱次数，走路步数）；反向 Dijkstra 求出每个状态到终局的最小代价，再正向只在紧边上按 NSWE、nswe 的优先级贪心，还原出字典序最小的最优动作串。

把格点当节点、斜线段当边，格子方向已对则边权 0、需要旋转则边权 1，用双端队列 BFS 求 0-1 最短路，O(RC)。

把 (城市, 剩余油量) 当作状态建分层图，加油是正权边、开车是零权边，每 个询问跑一遍优先队列 BFS（Dial 桶队列）最短路。

反图 Dijkstra 求到终点的最短路作为 A* 启发函数，按 f=g+h 扩展，第 K 次弹出终点即第 K 短路。

把 01 矩阵中所有 1 作为 BFS 源点，多源同时扩展，每个格子第一次被访问到的层数就是到最近 1 的曼哈顿距离。