CF1687
Scintilla
·
·
个人记录
blog
被 hzr 和 xzy 出的题吊打力 /kk/kk
A (\texttt{Easy} \ 1 / 0)
如果 k < n，那么肯定是选长度为 k 的最大子段和；否则显然从 n - k 秒开始走一遍是最优的。
时间复杂度 \mathcal{O}(n)。
B (\texttt{Easy} \ 2 / 0)
先用 m 次询问求出每条边的边权，然后做 Kruskal。判断一条边的两个端点是否已经连通的方法是判断加入它后最大生成树权值和的增量是否恰好为该边边权。
时间复杂度 \mathcal{O}(m)。
C (\texttt{Easy} \ 3 / 1)
首先令 a_i \leftarrow a_i - b_i，s_i 为 a_i 的前缀和，那么我们的操作等价于：对于任意给定的 (l, r)，若 s_{l - 1} = s_r = x，则可以把 s_{l \sim r} 都变成 x。
我们的目标状态是 s_i = 0，所以我们只进行 x = 0 的染色操作，贪心染色即可。具体地，把一个区间 [l, r] 挂在 l - 1 处和 r 处，维护一个操作队列，首先把所有可以在初始序列上操作的区间加入队列，如果一个 s_i 变成 0 了，则把挂在 i 处的所有区间拿出来判断能否对这个区间进行操作，能的话就加入操作队列，一直循环直到队列为空，用一个 set 维护 s_i \ne 0 的位置。
时间复杂度 \mathcal{O}(n \log n)。
D (\texttt{Medium} \ 4 / 1)
首先答案上界显然不超过 a_n^2，所以 f(a_1 + k) \le a_n。
枚举 f(a_1 + k) = w，并维护 k 可能的取值区间 [l, r]。因为 r - l \le w 并且 a_i \ge a_1，所以不存在 f(a_i + k) 有两个可能的取值的情况，换言之，固定 w 时所有的 f(a_i + k) 就已经确定了，所以我们可以方便地维护 [l, r]，这样直接做是 \mathcal{O}(na_n) 的。
发现对于 f(a_i + k) = v 的一段区间 [L, R]，可以只保留 a_L 和 a_R，所以我们维护的时候可以不枚举 i 而枚举 v，因为可能的 v 有 \mathcal{O}(\frac{a_n}{w}) 个，所以总的时间复杂度为 \mathcal{O}(a_n \log a_n)。
如果 l > r 了要马上退出，不然会寄。
E (\texttt{Medium} \ 6 / 3)
令 v_p(n) 表示最大的 k，满足 p^k \mid n。
对于所有质因子 p，设 v_p(a_i) 中最小值和次小值为 x_p, y_p，则我们的目标值就是 \prod_p p^{x_p + y_p}。
根据提示， 我们考虑扩展 \min - \max 容斥
\min_k(S) = \sum\limits_{T \subseteq S} (-1) ^ {|T| - k} \binom{|T| - 1}{k - 1} \max(T)
我们可以类似得到
\gcd_k(S) = \sum\limits_{T \subseteq S} \text{lcm}(T) ^ {(-1) ^ {|T| - k} \binom{|T| - 1}{k - 1}}
所以
\prod\limits_p p^{x_p + y_p} & = \gcd(a) \times \gcd_2(a) \\
& = \sum\limits_{T \subseteq S} \text{lcm}(T) ^ {(-1) ^ {|T| - 1}} \times \text{lcm}(T) ^ {(-1) ^ {|T|} (|T| - 1)} \\
& = \sum\limits_{T \subseteq S} \text{lcm}(T) ^ {(-1) ^ {|T|} (|T| - 2)} \\
\end{aligned}
但是这个做法的操作方案还是指数级别的。这个式子已经没有什么优化的空间了，我们不妨换个方向，尝试寻找目标值与原序列相等的长度能承受指数复杂度的序列。
不难发现，我们可以进行两次「找到一个和当前序列 \rm gcd 相同的短子序列，然后把子序列从序列中丢掉」的操作，那么两次丢掉的数就能构成我们要找的序列了。事实上，因为 2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 > 10^6，可以证明每次丢掉的序列长度最小值不超过 7，所以我们构造的序列长度不超过 14，这是可以接受的。
那么怎么找出一个 \gcd 与当前序列相等，并且长度 \le 7 的子序列呢？考虑随机化。首先对序列去重，然后对于数 u，如果序列中存在 v 使得 v < u, v \mid u，那么我们就忽略 u，在剩下的数里面一直随 7 个，直到随到合法的情况。
这样看上去很对，写出来也跑得挺快，正确性我不会证，欢迎大哥来叉。
还有题解的做法：设选出的子序列为 S。任选一个数 x = \prod_i p_i^{k_i}，把 x 加入 S，并对于所有 i，把 v_{p_i}(a_i) 最小的数 y 加入 S，然后若 |S| = 8 则去掉 x，正确性不难证明。
F
哈哈，我一 sb 还想会 F？