Virtual PTS 2020 Day 2 总结

``` --- layout: post title: Virtual PTS 2020 Day 2 总结 date: 2020-06-15 updated: 2020-06-15 katex: true categories: 总结 tags: [总结, Virtual PTS, 数据结构, 计数] --- ``` 这套题总体难度稍正常，T1 比较简单，T2 思路不是特别困难但细节较多，T3 较难。 ### GCD 与 LCM 题意：给出一个长度为 $n\ (2\le n\le 10^6)$ 的数列 $a\ (1\le a_i\le 10^6)$，求在 $\gcd(a_i,a_j)\ (i\neq j)$ 最大的前提下，$\operatorname{lcm}(a_i,a_j)$ 的最大值。 首先，由于 $\operatorname{lcm}(a_i,a_j)=\dfrac{a_ia_j}{\gcd(a_i,a_j)}$，而 $\gcd(a_i,a_j)$ 是一个定值，因此只需要在 $\gcd(a_i,a_j)\ (i\neq j)$ 最大的前提下使 $a_ia_j$ 最大就可以了。 $a_i\le 10^6$ 的范围一下子让我们想到了枚举因数。从 $1$ 到 $10^6$ 枚举因数 $d$，看它的倍数在数列中出现了几次；那么倍数在数列中出现至少两次的最大的数就是 $\gcd(a_i,a_j)$ 的最大值（最大的公因数一定是最大公因数的最大值）。在找的过程中维护 $a_ia_j$ 的最大值即可。时间复杂度 $\mathrm{O}(n\log n)$。 ### 项链染色 题意：有 $k\ (k\in \{1,2\})$ 串项链，每串项链上各穿着 $n$ 颗珠子，这 $kn$ 颗珠子的形状两两不相同（也就是说，$k$ 串项链有标号，珠子也各有标号）。现在有 $m\ (1\le m\le 3000)$ 种颜色可用，要给珠子染色，求方案数。 染色方案有以下两条要求。 - 同一串项链上，（环上）距离不超过 $2$ 的任意两颗珠子不同色。 - 若 $k=2$，则同一种颜色不能同时在两串项链上出现。 这道题的要求是“距离不超过 $2$ 的任意两颗珠子不同色”，和我们做过的“邻位不同色”有些类似。我们可以设计状态，保留最后一个和倒数第二个珠子的颜色状态。 颜色可以分为三种：第一个珠子的颜色（1）、第二个珠子的颜色（2）和其他颜色（0），那么我们的染色方案数就是 `f[n][0][0]+f[n][0][2]`。转移比较复杂，需要仔细推敲，结果如下： ```text 00 01 02 10 12 20 21 00 t-4 t-3 t-3 01 t-3 t-2 02 t-3 t-2 10 1 1 12 1 20 1 1 21 1 ``` 表中的行表示“$i$ 时的状态”，列表示“$i-1$ 时的状态”，如 00 行 01 列为 $t-3$ 表示 `f[i-1][0][1]` 对 `f[i][0][0]` 的贡献是 $t-3$ 倍的。$t$ 表示可用的颜色数。 这样我们计算完了“有 $t$ 种颜色可用”时的染色方案数，就解决了 $k=1$ 的问题。 如果 $k=2$，还要把上面的结果换算成“恰用了 $t$ 种颜色”的方案数，只需要用组合数减一下就好了。接下来再枚举两个项链各自使用的颜色数，乘上两个组合数（相当于组合问题中的分两组，有组名）即可。 此外，这道题的模数是运行时已知的，因此可以尝试使用 [Barrett Reduction 乘法取模加速](https://www.luogu.com.cn/blog/Sweetlemon/barrett-reduction)，优化效果非常显著，从 [$4.55 \mathrm{s}$](https://www.luogu.com.cn/record/34419578) 优化到了 [$927 \mathrm{ms}$](https://www.luogu.com.cn/record/34419557)（两次提交均为 `O2`）。 ### 信号覆盖 题意：在一个包含了 $[1,n]$ 的整数的数轴上，给出 $m$ 个基站，每个基站的位置是 $q_i$，且会给到基站距离不超过 $p_i$ 的所有点**加上** $p_i-d$ 的增益（其中 $d$ 是这个点到基站的距离）。此时，每个点的总增益是所有基站给这个点增益的和；整个方案的瓶颈增益是所有点总增益的最小值。 现在允许移动一个基站的位置，要**分别**求出可以移动第 $i$ 个基站时，瓶颈增益的最大值。 每个基站相当于给两个区间分别加上了等差数列，因此使用二阶差分数组就可以求出每个点的初始增益。 对每次查询（即可以移动某个基站时），可以先把这个基站的贡献消除，接着二分答案；而每个增益不到 $\mathrm{mid}$ 的点，都会要求基站到它的距离不大于某个值，从而规定了基站位置的取值区间；把所有有要求的区间交起来，如果非空，就说明这个答案可行。这样可以做到 $\mathrm{O}(nm\log n)$。 正解需要进行一定的分类讨论，并做一些类似矩形内查最大值的操作；需要用到可持久化线段树，在此不再叙述。