一些从做题记录中翻出来的题解

Posted on Disqus:

QAQ

CF1687E

两两乘积的 gcd⁡\gcd 每个质因数的指数就是所有数这个质因数的最小值和次小值，在指数上 kth-min-max 容斥就可以把这东西用所有子集的 gcd⁡\gcd 表示，考虑减少集合大小，设 g(x)g(x) 为 x 的一个子集使得 gcd⁡(g(x))=gcd⁡(x)\gcd(g(x)) = \gcd(x)，那么 g(x)∪g(S−g(x))g(x) \cup g(S - g(x)) 答案一定和 S 相同（因为每个质因数指数的前两小都被取走了），考虑怎么求 g(x)g(x)，考虑任取一个 a，a 最多有 8 个质因子，我们从小到大考虑每一个，如果这一项的指数和 gcd 不同就找一个最小值加进去，考虑如果加了 8 个那么 a 一定没用，考虑否则 p1p_1 （第一个加入的数）能被 p2…p8p_2 \dots p_8 和 p′p'(只有 a 没有的质因子乘除），于是 p1×p1\times最小的质因子 ≥p1×⋯×p8∗p′\ge p_1\times\dots\times p_8*p'，最小的质因子 ≥\ge 11,乘积不可能小于 10610^6。

P8861

考虑那个 subtask，因为所有线段都包含同一点，而这个点永远不会被删除，所以可以只用堆维护左右端点到中间的哪一段，而对于一般情况我们可以建出一颗线段树，把每一条线段插到第一个包含 mid 的区间，对于包含 mid 的修改用上面的方法改，不包含 mid 的暴力改然后重新插入，一条线段最多 log 次，因为有重新插入的情况还需要开一个并查集维护每条线段的左右端点，卡时限过了，可能有更好的做法。

P8860

如果我们把所有没询问过的边在最后询问一次，那么最后只会剩下一条路径，考虑这是哪一条，把每条边的权值定为一个字符串，第 i 位是这个路径是否包含在第 i 个时刻被第一次问的边，那么权值最小的那条路径一定会留下（因为剩下的路径都会在删除第一个不同位的时候因为存在另一条路径而被删除），发现加入一条边不会使权值变小，于是 dij + 线段树维护哈希值做比较。

P8859

对原排列，我们固定 n ，发现最终状态在 1 前的都需要一次交换，在 1 后的只有前缀最大值不用交换，于是答案就是所有所有后缀的前缀最大值个数的 max = n-k 的排列个数 n^3 dp 每次插入最大的。

P1232

如果树无标号，那么我们可以将 bfs 序划分成若干层，那么只要 dfs 序相邻的点层数不增加 1 以上就合法，至于有标号就需要保证 bfs 序上同层的点依次出现，第一个限制就是某段区间中必须分割，第二个限制就是某个点必须分割，发现第一个限制的区间中一定有第二个限制的点。

ARC089D

发现每一个有蓝色的连续段都可以用 r b + (连续段内极长蓝色子段个数-1) 个 r/b 完成，证明可以归纳，于是可以贪心的选这些位置，我们只需要搜出 (连续段内极长蓝色子段个数）这个序列，是划分数级别的，但我们目前求出了一个压缩后的序列，用插板法扩回去就行。

区间最近点对

维护 log⁡108\log10^8 个题解中称为 “cell system” 的东西，实际上第 k 个就是整个平面每 (2k)∗(2k)(2^k)*(2^k) 分一个格子，对于一个点，所有距离它 ≤2k\le 2^k 的点都一定在它 3*3 的格子邻域中可以找到，我们把询问离线，每次右端点 i + 1 并加入所有以它为端点可能作为答案的点对，发现如果我们在第 k 个 cell system 中发现存在 (j,i) 使得 dis(j,i)≤2(k−1)dis(j,i) \le 2^(k-1) 那么我们就可以在第 k 个 cell system 中将 j 删除，因为之后所有包含 j 的询问都一定包含 (i,j)，可以前 k-1 个 cell system 中更新答案，于是可以推出每个格子内只有 O(1) 的格子，每次也只会对于右端点加入 O(log) 个点对，树状数组维护前缀最小值即可。

CF1768F

发现如果 minai>Amin_{a_i} > \sqrt{A} 的话区间长度不可能超过 A\sqrt{A} （否则不如一个一个跳），这些可以暴力，只需要考虑 minai<Amin_{a_i} < \sqrt{A}，而一个转移区间的最小值也一定只能在区间端点处出现（否则在中间的最小值处停一下一定更优），于是同时符合两个条件的区间只有 nAn \sqrt{A} 个（分别为每个点和它左边 1…A1\dots\sqrt{A} 的第一次出现位置）。

…\dots