QOJ 4th cup 补题计划 Stage 1~3

· · 算法·理论

本补题计划面向的是 4th-cup 中所有赛事通过人数 [100,300) 的题目，所有题目都在 NOIP 范围内，难度大约橙到蓝。

Stage 1: Grand Prix of Korolyov (CDEFK)

QOJ14428 Staple Stable (C)

我们枚举切除的矩形的最长的一条边 x，则另一条边为 y=\lfloor \frac{s}{x}\rfloor，则此时矩形的答案为 \min(\lfloor\frac{h-1}{x}\rfloor+\lfloor\frac{w-1}{y}\rfloor,\lfloor\frac{w-1}{x}\rfloor+\lfloor\frac{h-1}{y}\rfloor)，枚举 x 的复杂度是 O(s)，但由于 x>y 是无意义的，通过交换 x,y 可以变成之前讨论过的情况，故讨论 x<y 即可，时间复杂度 O(\sqrt s)。

QOJ14429 Sequence Is Not Subsequence (D)

发现 s_n 一定会出现，考虑 s_n 最后一次出现在 t_i，则 t_{1\sim i-1} 不会存在 s_{1\sim n-1}，则根据贪心，t_{1\sim i-1} 一定存在 s_{1\sim n-1} 的所有子序列，不然你构造 s_n 无用。

由于要构造 s_{1\sim n-1} 出现，因此如果 s_n\not= s_{n-1}，则 s_n 需要在 t_i 后额外出现一次。

很容易想到构造出 s_2s_1s_3s_2s_4s_3\dots s_ns_{n-1} 的方案，再将相同字符排除即可。

QOJ14430 Coffee Shops (E)

考虑贪心，将 a 序列中偶数项填最大的 \frac{n}{2} 个数，这样的话你 b 序列接下来无论填什么都是最大的，接下来考虑将 a 序列中奇数项的位置产生贡献，即 a 中奇数项 1,3,\dots 就填比 i 和 i+1 小的数即可，可以倒着从 n\to 1，每次从大往小填 b_i 然后填 a_i。

注意 n 为偶数的情况你的 a_1 没有填最大的数，导致围成环后 b_1,b_n 都无法获得贡献，考虑将 a_1 补上即可。

QOJ14431 Yet Another MST Problem (F)

遇到 mex 考虑枚举边权 x 然后将所有不包含 x 的区间合并。每次合并的左右区间形如 [1,x'),(x',n]，容易发现此时的区间是递增的，所以只用双指针维护一下当前扫到了 [1,pl),(pr,n] 然后暴力维护一下即可，时间复杂度是 O(n\alpha (n)) 的。

QOJ14436 Robot Construction (K)

我们发现最终答案的取值一定是一个连续的区间 [0,x]，我们考虑分析一下在高度区间为 [0,h] 时遇到障碍高度为 a_i 时的影响：

考虑扫描右端点 r，然后维护 l\in [1,n] 的值域 [0,V]，则加入点 a_r 对 V\in [0,a_i) 无影响，V\in [a_i,2a_i) 是赋值为 a_i-1，V\in [2a_i,+\infty) 是减去某个数。

注意到 V 随着 l 的增大而增大，故 [0,a_i),[a_i,2a_i),[2a_i,+\infty) 都是连续的区间，考虑线段树上二分维护，时间复杂度 O((n+q)\log n)。

Stage 2: Grand Prix of Paris (ABFHK)

QOJ14130 Apple Tree (A)

假设离节点 i 距离为 k 的点有 d_i 个，则答案为 \sum \binom{d_i}{k}，则现在需要求出 d_i。

显然可以直接点分治做，给出一种不同于点分治依赖 k 的大小的做法。

我们注意到每个节点的直接子节点数量都严格少于其父亲节点的直接子节点数量，说明树的高其实是非常小，约为 O(\sqrt n) 的，所以只有 k\le 2\sqrt n 时才有答案。

考虑树形 DP，f_{u,d} 表示 u 子树内距离为 d 的节点个数，g_{u,d} 表示不在 u 子树内距离为 d 的节点个数。

则有 f_{u,d}=\sum\limits_{v\in son_u} dp_{v,d-1}，g_{u,d}=g_{fa_u,d-1}+f_{fa_u,d-1}-f_{u,d-2}，时间复杂度 O(nk)，要剪枝并使用 vector 来存 DP 数组。

QOJ14131 Balatro (B)

由于 k 和 \min(a_i,b_i) 很小，考虑从这两个方面入手。

考虑将牌堆分成两堆，分别表示 a_i<b_i 的牌堆 1 和 b_i<a_i 的牌堆 2，则答案即为从 1 中选 x 张再从 2 中选 k-x 张牌的最大值。

考虑 f_{i,j} 表示从 1 中选择 i 张牌的 a_i 之和为 j 时 b_i 之和的最大值，故有转移 f_{i,j}=\max(f_{i,j},f_{i-1,j-a_i}+b_i)，2 牌堆同理构造 DP 数组 g，最后的答案即为 \max (y_1+g_{x,y_2})(y_2+f_{k-x,y_1})，时间复杂度为 O(V^2k^3)，其中 V 是指 \min(a_i,b_i) 的值域，为 100。

QOJ14135 Framboise 2（F）

首先每个植物连向自己所相邻的边界是一定可以的，方案数为 2^k。

由于 r=1 的植物向下连和 r=2 的植物的情况是一样的，这里只讨论 r=1 的情况。

一棵植物向下连的充分条件是下方没有植物，假设有 m 棵下方没有植物的植物，则方案数为 2^m。

考虑向左连和向右连的情况，则显然只有最左端和最右端才能连出去（假设最左端为 l'，最右端为 r'）：

故方案数为 2^k(2^m+2^{m-x}+2^{m-y}+2^{m-x-y}，交换 r=1,2 后再处理一遍即可。

QOJ14137 Heure de Rush (H）

考虑现将每个位置减 k，变成将所有元素变成 0。

考虑第 i 位 <0，则一定找 a_j>0 的最小的 j 来补上这一块，这个可以双指针实现，则答案即为 \max \lceil \frac{j-i}{d}\rceil。

QOJ14140 k Operations (K)

贪心一下很容易发现相当于是每次减最小的数一直到 1，然后再减第二小的数，以此类推，直到减了 k 次或者无元素可减。

考虑对于每一次操作 [l,r,k]，二分 x 使得区间 1\sim x 小的数全部减到 1，第 x+1 的数还没减到 1，则相当于 \sum\limits_{1\le i\le x} (a_{\text{kth}(l,r,i)}-1)\le k\le \sum\limits_{1\le i\le x+1} (a_{\text{kth}(l,r,i)}-1)，很显然，答案为 \prod\limits_{x+2\le i\le r-l+1}a_{\text{kth}(l,r,i)}\times (a_{\text{kth}(l,r,x+1)}-(k-\sum\limits_{1\le i\le x} (a_{\text{kth}(l,r,i)}-1))，则用权值主席树维护一下值域和和值域积，可以做到 O(q\log^2 n)，使用线段树上二分可以做到 O(q\log n)。

Stage 3: Polar Grand Prix (DGI)

QOJ14417 Roman Numerals (C)

挺好的一个笛卡尔树题。

根据性质 \max(v_l,v_{l+1},\dots,v_r)=v_{lca(u,v)}，这个 f(l,k-1) 和 f(k+1,r) 就很像递归笛卡尔树，由于贡献是 a_k-f(l,k-1)+f(k+1,r)，也就是你每次往左子树走一次你的贡献会乘 -1。

因此贡献就是 \sum\limits_{l\le i\le r} a_i(-1)^{f(i)}，其中 f(i) 表示 lca(l,r) 走到 i 要往左走的次数。

这个东西显然是可以优化的，你考虑与处理一下 b_i= a_i(-1)^{f'(i)}，其中 f'(i) 表示笛卡尔树根到 i 要往左走的次数。

然后答案就是 (-1)^{f'(lca(l,r))}\sum\limits_{l\le i\le r} b_i，前缀和搞一下就做完了，复杂度可以做到 O(n+q)。

QOJ14418 Disjoint Set Splitting (D)

这期神了。

注意到答案具有单调性，想到二分但由于强制在线无法进行。

但是这个题的答案只有 0 和 1，故你的强制在线的系数是可以提前算出来的！然后就可以离线了，强强。

QOJ14421 Far Away (G)

对于一个询问 (u,v)，我们发现如果答案为 Yes 且两个点在一个联通块，则相当于两点的最短路径为 d>20000，也就是说至少有 \frac{1}{5} 的点都在路径上，故考虑随机化枚举一个点 x，然后跑最短路，判断 d_u+d_v，单次正确的概率为 (1-0.8^x)^q，跑大概 O(1) 次就可过了，时间复杂度是 O(n\times t),t\in [75,300]。

QOJ14423 Two Permutations (I)

考虑从大到小维护这个序列，由于支持 O(n^2) 构造，显然每一个元素移动 O(n) 次是可以的。

则假设维护到 x，x 在 A 中是 pa_x，B 中是 pb_x，则由于 x\sim n 都被固定了，所以 x 是不能向后换的，故 pa_x<pb_x，则是无解的。

然后考虑构造 pb_x\le pa_x 的情况，故考虑每次操作的代价最小，即按照一个尽可能长的序列进行交换，容易发现构造 (y_1,y_2),(y_2,y_3),\dots,(y_i,y_{i+1}) 可以做到循环移位的效果，这样代价是 O(1) 的，不然肯定会导致这个上升子序列破坏掉，肯定不优。