2024.6-2024.8 刷题笔记
ARC179C
题意
【交互题】有一个只能写 $[-R,R](R\le 10^9)$ 范围内的数的黑板，黑板上起初有 $n(n\le 1000)$ 个数 $a_i$，满足 $|a_i|\le R,|\sum_{i=1}^na_i|\le R$。现在支持以下两种交互操作：
- 指定黑板上两个不同的数，用它们的和替换它们
- 指定黑板上两个不同的数，查询它们的大小关系
已知 $n,R$，要求用不超过 $25000$ 次操作使得黑板上只剩下 $|\sum_{i=1}^na_i|$。
做法
- 首先发现 $|\max{a}+\min{a}|\le R$，可以分类讨论证明：
- 若 $\max{a}$ 和 $\min{a}$ 同号，则 $|\max{a}+\min{a}|\le |\sum_{i=1}^na_i|\le R$；
- 若 $\max{a}$ 和 $\min{a}$ 异号则 $|\max{a}+\min{a}|\le \max{|\max{a}|,|\min{a}|}\le R$。
- 比较次数不能超过 $25000$，恰好是 $2n\log n$ 左右。因此可以考虑维护黑板上所有数的最值，每次取出最大值和最小值相加并写回黑板。
- 但是用平衡树或堆都有 $2n$ 个数需要插入和删除，比较次数是 $4n\log n$ 左右，容易超限。
- 注意到虽然操作次数的限制是 $\Theta(n\log n)$，但时间允许 $O(n^2)$。因此可以直接用数组维护黑板上数的有序序列，只有插入新数二分时需要比较，次数约 $2n\log n$。
CF1986G2
题意
给定一个长度为 $n(n\le 5\cdot 10^5)$ 的排列 $p$，求满足 $p_i\cdot p_j$ 是 $i\cdot j$ 倍数且 $i<j$ 的 $(i,j)$ 对个数。
做法
- 单独考虑每个 $i$ 和 $p_i$ 的组合，每个组合需要其他组合提供 $x_i=\frac{p_i}{\gcd(p_i,i)}$，能给其他组合提供 $y_i=\frac{i}{\gcd(p_i,i)}$，两个组合若希望配对需要互相满足对方的需求。
- 考虑将 $y$ 按值分类：对于每个 $y$ 的值，枚举能满足其的 $x$ 的值，即其倍数，找到对应的下标 $i$，这样可以预处理出二维表 $u$，$u_j$ 保存所有能满足 $y=j$ 的下标 $i$ 对应的 $x_i$，此举时空复杂度为 $O(n\log n)$。
- 先枚举 $y$ 的值，再枚举对应的下标 $i$ 和 $p_i$，再枚举 $p_i$ 的因数的时间复杂度也是 $O(n\log n)$。
- 根据上面的分析，可以将答案按照其中一个 $y$ 的值划分，分别计算并求和：枚举 $y$ 的值 $j$，动态维护一个计数数组为 $u_j$ 计数，然后枚举 $y=j$ 对应的 $p_i$，再枚举 $p_i$ 的因数，将因数的计数贡献给答案，总时间复杂度 $O(n\log n)$。
- 还需要排除自我配对的情况。
CF1988D
题意
给定一棵 $n(n\le 3\times 10^5)$ 的树，每轮可以任选不相邻的任意多结点删除，并受到删除前所有结点权值和的伤害，问最少受到多少伤害可以删除所有结点。
做法
- 考虑树形 DP，记 $dp(i,j)$ 为结点 $i$ 在第 $j$ 回合被删除的情况下 $i$ 的子树对答案的贡献，则 $dp(i,j)$ 可以由 $\underset{k\neq j}\min\text{ }dp(u,k)$ 贡献，其中 $u$ 为 $i$ 的邻接点。
- 通过前后缀预处理和差分可以将贡献复杂度压缩至 $O(n)$，但也可以根据下面的结论 $O(n\log^2 n)$ 暴力转移。
- 重要结论：若结点 $i$ 在第 $r_i$ 轮被删除，则 $r_i$ 不会超过 $i$ 所有邻接点 $r$ 的 MEX，由此可知 $r_i$ 不会超过 $\log n$。证明：假设存在 $r_i=x$ 最少需要的结点数为 $f(x)$，则 $i$ 邻接结点的 $r$ 覆盖了 $[1,x]$，结点数 $f(x)\ge \sum_{u=1}^{x-1}f(u)$，易得 $f(x)=\Theta(2^x)$。
CF1995D
题意
给定一个长度为 $n(n\le 2^{18})$，包含前 $c(c\le 18)$ 种大写字母的字符串，将其任意分割为若干个长度小于等于 $k(k\le n)$ 的单词，求单词尾字母的种类最少会有多少种。
做法
- 问题相当于选择一个满足要求的最小字母集 $S$。
- 每当遇到 $S$ 中的字母就作为单词结尾一定是最优的，因此 $S$ 需要满足：串中长度为 $k$ 的子串一定含有 $S$ 中的字母，且串的末字母一定在 $S$ 中。
- 将每个子串分开来考虑，分别得到需求集合，作为对 $S$ 的约束条件，此时 $S$ 只需要满足与所有需求集合都相交即可，所以问题转化为在 $O(2^c)$ 种集合的范围内找到与 $O(n)$ 个集合都相交的最小集合。
- 逆向考虑上述问题，找出所有与某个需求集合不相交的集合，即所有需求集合反集的所有子集，通过从大到小状压 DP 即可完成。
ABC368E
题意
有 $n(n\le 2\times 10^5)$ 个站点和 $m(m\le 2\times 10^5)$ 班火车，第 $i$ 班火车在 $s_i$ 时刻从 $a_i$ 出发，在 $t_i$ 时刻到达 $b_i$。现在第 $1$ 班火车延迟了 $x_i$ 出发，求为了使得原本能够换乘的班次对都依然能够换乘，其他每班火车分别需要延迟多久。
做法
- 如果建立线图利用其拓扑关系求解，时间复杂度很难低于 $O(m^2)$，因此可能需要抛弃基于图的思路。
- 将所有的出发和到达事件按照时间顺序排序，则对于每一个出发事件，其左边位于同一站点的到达事件即其需要考虑的所有事件；而实际上出发事件只需要考虑其所在站点此时的最晚实际到达时间即可。
- 对于出发事件，用站点最晚实际到达时间来计算班次的延迟时间；对于到达事件，用班次延迟时间来更新站点的最晚实际到达时间。总时间复杂度 $O(m\log m+n)$。
2024.6-2024.8 刷题笔记