好题分享（持续更新中...）

近期遇到的好题，值得反复回味。
持续更新，最新的在前面。
本文由AI分析题解后经个人修改而成

组合博弈 + DAG 上的 N/P 判定

来源：1103d3-D — Codeforces Round 1103 Div.3

技巧：组合博弈，逆向归纳，奇偶性分析，树状数组，DAG

思路：博弈规则是每次选的数必须 ≥ 上一个数且差值 ≤ k。将相同值聚合压缩（出现次数 cnt），排序后从大到小逆向判定每个值 v 的 N/P 状态。判定规则：

若在 v 可达的范围内存在必败态 P，则一步走到 P 交给对手 → v 是必胜态 N。
若范围内全为必胜态 N，则看 cnt(v) 的奇偶性——偶数时可镜像策略保持控制权（N），奇数时被迫交控制权（P）。

区间查询"是否存在 P"用树状数组 O(log N) 完成。全部判定后检查是否存在 N → 有则先手胜。

核心：将相同值聚合成桶、从终点逆向归纳判定 N/P，是组合博弈中"DAG 博弈"的入门典范。

→ 我的题解

质因数分解和互质分析

来源：1103d3-F — Codeforces Round 1103 Div.3

技巧：质因数分解，计数原理（乘法原理）

思路：条件 $x \cdot \text{lcm}(p_1,\dots,p_n) = \prod p_i$ 且 x=1，等价于所有 $p_i$ 两两互质。每个 $a_i$ 只能选其因数为投票值，但两个不同的人不能选有公共质因数的值。将每个 $a_i$ 质因数分解后，对每个质数 P 统计它在序列中出现的总幂次 k（跨所有元素）。质数 P 在每个位置可出现 0~k 次，总贡献为 $D = 1 + \sum k$ （1 表示完全不出现在任何 $p_j$ 中）。答案 = $\prod D$ 。

核心：将 LCM 的约束转化为互质条件，再对每个质数独立计算乘法贡献。

→ 我的题解

双向贪心 + 从最大值断开

来源：1102d2-C/F — Codeforces Round 1102 Div.2

技巧：贪心，单调栈，“从最大高度处断开成链”

思路：n 个环形连通器，问桶 i 空着时最多能装多少水。对每个桶，顺时针方向和逆时针方向各贪心地构造一个"单调不减序列"（能加多少加多少，但不允许水往身后溢），取两个序列每个位置的 min 即为正解。
hard version 的优化：找到最大高度 H，从 H 处把环断开成链，就变成了一段单调不减的后缀 + 一段单调不增的前缀，用单调栈预处理即可。这样复杂度从 O(N²) 降到 O(N)。

核心：环形问题"从最大值处断开"是一个经典思路——最大值处天然形成屏障，断开后问题退化为线性。双向贪心 + 取最小值保证了既不向左也不向右溢出。

→ 我的题解

子区间和等于 K

来源：ABC461-D — AtCoder Beginner Contest 461

技巧：前缀和，滑动窗口 / 双指针，哈希表

思路：求矩阵中和等于 K 的矩形数量。O(N⁴) 暴力不可行（N≤500），用前缀和优化到 O(N³)：先对每行做前缀和，然后 O(N²) 枚举左右列边界 [l, r]，固定列区间后每行的区间和可以 O(1) 求出，问题转化为一维序列中求区间和等于 K 的个数。对于一维版本，数据为正用双指针，数据非负需要额外指针处理 0 区间，通用解法是用哈希表记录前缀和计数。

核心：一题吃透"区间和等于 K"的三种场景（正数 / 非负 / 通用），并展示了如何用前缀和将二维退化为一维。这是前缀和技巧的综合训练题。

→ 我的题解

树状数组 + 时间戳

来源：ABC461-E — AtCoder Beginner Contest 461

技巧：树状数组（BIT），时间戳，区间查询 + 单点修改

思路：N×N 网格，操作 1 将第 R 行全涂黑，操作 2 将第 C 列全涂白，每次操作后输出当前黑色格子总数。关键洞察：行涂黑增加的白格子数 = 该行上一次被涂黑到当前时刻之间，列被涂白的次数。同理列涂白减少的黑格子数 = 该列上一次被涂白到当前时刻之间，行被涂黑的次数。于是问题变成"统计时间区间内的操作次数"——用树状数组维护时间戳，支持单点插入新时间戳、区间查询两个时间戳之间的操作数。

核心：将"涂色计数"转化为"时间维度上的区间统计"，这是树状数组的一种不那么直白的应用。时间戳 + 去重的技巧在许多二维操作题中都通用。

→ 我的题解

先算复杂度上界，再写 DP

来源：ABC461-F — AtCoder Beginner Contest 461

技巧：01 背包，因数分解，双 DP 状态

思路：求所有"互异因数乘积为 N"的序列的分数总和。N ≤ 10¹⁰，看起来很大，但关键洞察是 $13! > 10^{10}$ ，所以序列长度不超过 13。把 N 的因数（最多约 2304 个）排序后，在因数序列上做 01 背包： $F_{x,j}$ 表示选 j 个因数乘积为 x 的方案数， $G_{x,j}$ 记录对应总分数。选入因数 $B_i$ 时，乘积 x·B_i 的新分数 = 原分数 + 原方案数 × B_i，最后乘以阶乘（因为序列有序）。复杂度约 $O(2304^2 \times 14)$ ，可过。

核心：复杂度计算是这是整题的关键，如果因为觉得复杂度太高而不可过，以至于不敢写，就失败了。当然，本题的暴搜方法只是数据太弱了。

→ 我的题解

线段树动态维护树的直径

来源：ABC460-F — AtCoder Beginner Contest 460

技巧：线段树，LCA（倍增），树的直径

思路：树的直径可以线段树维护。对于线段树的每个区间，记录该区间内黑色顶点集的最远两点 (u, v) 及其距离。合并两个区间时，新区间的直径端点一定在原左右区间的四个端点之中（枚举 4 选 2 取最大距离即得）。支持单点修改（白变黑 / 黑变白），修改叶子后向上更新到根即可，根节点记录的距离即为全局直径。两点距离通过 LCA + 深度公式 O(log N) 计算。

核心：把"求树的直径"转化为"区间最值合并"问题，利用直径的可合并性使得动态维护成为可能。线段树通常用于序列，这里是树上问题序列化的经典范例。

→ 我的题解

反悔贪心

来源：1101d2-C — Codeforces Round 1101 Div.2

技巧：反悔贪心，模拟

思路：三种性格的人排队入座——I 必须坐空桌，E 必须坐有人的桌，A 随意。桌子有限、座位有限，求最多入座人数。贪心策略：A 人能坐就坐，E 人优先坐已有人的桌子（不够则让 A/I 开辟新桌），I 人需要新空桌。核心在于 A 和 I 的"反悔"机制：如果因为 A 占了桌子导致 I 无法入座，可以舍弃这个 I（两者贡献都是 1），等价于"反悔"了放 A 的决策。

→ 我的题解

严格递增转化为非递减

来源：ABC459-F — AtCoder Beginner Contest 459

技巧：数学转化，归并，前缀和，单调栈

思路：每次可将 $A_i$ 减 1、 $A_{i+1}$ 加 1，要使 A 严格递增。核心转化：令 $D_i = A_i - i$ ，则 $A_i < A_{i+1}$ 等价于 $D_i ≤ D_{i+1}$ ，且一次操作等价于 $D_i - 1$ 、 $D_{i+1} + 1$ 。问题变为让 D 非递减的最小操作数。将 D 按均值分成若干非递减块（用栈维护块的大小与均值），最优 D’ 构造完成后，答案 = Σ(原前缀和 − 新前缀和)。

核心：将"严格递增"转为"非递减"的 $D_i = A_i − i$ 是一个通用 trick，在很多递增约束题中都能用。

→ 我的题解

Dilworth 定理的完美应用

来源：ABC457-G — AtCoder Beginner Contest 457

技巧：Dilworth 定理，最小链覆盖，最长下降子序列（LDS），偏序

思路：机器人收集苹果，约束为 $T_j − T_i ≥ |X_j − X_i|$ 。拆开绝对值移项得 $T_j − X_j ≥ T_i − X_i$ 且 $T_j + X_j ≥ T_i + X_i$ 。定义二元组 $(T−X, T+X)$ ，则机器人能按顺序收集的条件是二元组非递减。问题转化为：最少需要多少条非递减链覆盖所有点。由 Dilworth 定理，最小链覆盖数 = 最长反链长度，即求二元组的最长下降子序列。LIS/LDS 的标准 $O(N log N)$ 解法即可。