ACGO 巅峰赛#17 题解
本场巅峰赛的所有题目的难度评级为：
题目编号 题目标题 难度 A. 纪念品商店 入门 B. 删除元素使数组去重 入门 C. 摩天轮 普及- D. 线性探查法 普及 E. 统计 acgo 出现的次数 普及 F. 美丽数 II 普及 G. 数的集合 普及+/提高 H. 巨大的表格 提高+/省选-
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题解简述
以下提供每道题目的思路简述，详细题解的AC代码包括复杂度分析，请点击题目标题查看。
A - 纪念品商店
模拟；数学
我们可以实现一个函数 int clamp(v, lo, hi)。
这个函数会返回 [lo,hi]\tt{[lo, hi]}[lo,hi] 区间内，距离 v\tt{v}v 最近的点。
那么显然，如果 v\tt{v}v 在 [lo,hi]\tt{[lo, hi]}[lo,hi] 内，函数返回 v\tt{v}v；若不在区间内，则有两种情况：
1. v<lo\tt{v \lt lo}v<lo，此时显然返回 lo\tt{lo}lo；
2. v>hi\tt{v \gt hi}v>hi，此时显然返回 hi\tt{hi}hi；
有了这个函数我们就可以判断 [A,B]\tt{[A, B]}[A,B] 内离 C\tt{C}C 最近的点和 C\tt{C}C 的距离是否小于等于 D\tt{D}D，从而得出答案。
* 在 C++17 此函数已加入标准库，定义在头文件 <algorithm> 中。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
B - 删除元素使数组去重
模拟
本题数据范围比较小，做法很多。这里使用一种时间复杂度较小，且通用的方法。
我们从后到前考虑整个数组中的元素，不断将元素添加至集合中，直至某个元素已经在集合中出现过。
此时数组中剩下的未被遍历的元素数量即为最小操作次数。
此方法时间复杂度 O(NlogN)\mathrm{O}(N\log{N})O(NlogN)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
C - 摩天轮
模拟；数学
对于任意时刻 SiS_iSi ，我们考虑小码君的位置为 (X0,Y0,Z0)(X_0, Y_0, Z_0)(X0 ,Y0 ,Z0 )，小码酱的位置为 (X1,Y1,Z1)(X_1, Y_1, Z_1)(X1 ,Y1 ,Z1 )，那么二者之间的俯角或仰角度数为：
arctan(∣Z0−Z1∣(X0−X1)2+(Y0−Y1)2)⋅180π\arctan\left(\frac{\vert Z_0 - Z_1 \vert}{\sqrt{(X_0 - X_1)^2 + (Y_0 - Y_1)^2}}\right) \cdot \frac{180}{\pi} arctan((X0 −X1 )2+(Y0 −Y1 )2 ∣Z0 −Z1 ∣ )⋅π180
我们假定摩天轮的位置都是 (0,0)(0, 0)(0,0)，然后根据计算出的位置，加上原来的位置，就可以得出实际的位置。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
D - 线性探查法
数据结构（哈希表，平衡树）
我们考虑维护所有的为空的单元；对于「线性探测法」本质上就是找到 第一个大于等于 XXX 的空单元，若不存在这样的空单元，则寻找 第一个大于等于 000 的空单元。
那么我们可以考虑使用 std::set 来维护所有的 NNN 个空单元，并使用 std::map 来记录所有已经插入哈希表的元素分配到的位置即可。
时间复杂度：O(QlogN)\mathrm{O}(Q\log{N})O(QlogN)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
E - 统计 ACGO 出现的次数
动态规划；
我们考虑使用动态规划来统计所有的以 a，c，g，o 结尾的子序列的数量。
令 A,C,G,OA, C, G, OA,C,G,O 分别表示 a，c，g，o 结尾的子序列的数量。
遍历字符串 SSS，对于字符串 SSS 中的每个字符 SiS_iSi ，若其为 a，则将 AAA 加一；若其为 b，则将 BBB 更新为 B+AB + AB+A； 若其为 c，则将 CCC 更新为 C+BC + BC+B； 若其为 d，则将 DDD 更新为 D+CD + CD+C； 若为其他字符，则不做任何处理。
最终 DDD 即为所求的答案。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
F - 美丽数 II
质因子分解；
我们可以把 10510^5105 内所有的 959295929592 个素数预处理，来加速质因数分解，使其复杂度降为 O(π(⌊max(Ai)⌋)\mathrm{O}(\pi(\lfloor\sqrt{\max(A_i)}\rfloor)O(π(⌊max(Ai ) ⌋)。这样整个算法时间复杂度为 O(N×π(⌊max(Ai)⌋))\mathrm{O}\left(N \times \pi(\lfloor\sqrt{\max(A_i)}\rfloor)\right)O(N×π(⌊max(Ai ) ⌋))；其计算量大约为 104×104=10810^4 \times 10^4 =
10^8104×104=108，可以在时限内通过题目。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
G - 数的集合
质数筛；并查集；前缀和
本题有两种方法可以解决，前者的切入点更平滑，后者更偏向于数学直觉一些。
方法一（并查集）
比较直接的一个想法，从 NNN 开始执行搜索，把 [2,N−1][2, N - 1][2,N−1] 中未加入集合且与当前元素不互质的元素加入集合 SSS。
那么显然我们的目标就是如何快速地找到与 NNN 不互质的元素集合 S′S'S′，对于 S′S'S′ 中的每个元素，再找到与其不互质的元素，以此类推。
由于本题中的操作具有传递性质：XXX 与 YYY 不互质；YYY 与 ZZZ 不互质，那么 XXX，YYY，ZZZ 都属于同一个集合。
我们可以从小到大考虑每个元素 XXX，令 XXX 的最小质因子 P(X)P(X)P(X)，那么有：
1. 若 XXX 为质数，显然集合中只有 XXX 本身。
2. 若 XXX 不为质数，那么显然我们将其拆分为 P(X)P(X)P(X) 与 XP(X)\dfrac{X}{P(X)}P(X)X ，那么二者所在的集合可以借助 XXX 合并起来。
我们将处理到元素 XXX 时，其所在的集合的大小设为 f(X)f(X)f(X)，那么对应的操作次数为 f(X)−1f(X) - 1f(X)−1。
所以我们可以预处理 3×1063 \times 10^63×106 中的所有元素，然后依次回答每个查询即可。
令 M=max(Ni)M = \max(N_i)M=max(Ni )，此方法时间复杂度为 O(Mα(M)+MloglogM+T)\mathrm{O}(M\alpha(M) + M\log{\log{M}} + T)O(Mα(M)+MloglogM+T)。
并查集每个操作平均时间复杂度为 α(M)\alpha(M)α(M)，其中 α\alphaα 为阿克曼函数的反函数，其增长极其缓慢，也就是说其单次操作的平均运行时间可以认为是一个很小的常数。
方法二详情点击标题链接查看。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
H - 巨大的表格
递推；矩阵快速幂
我们可以先计算出 111 列的所有元素的值，然后考虑表格中每一列元素的值，可以发现，对于 i(i>1)i(i > 1)i(i>1) 列的 NNN 个元素的值，可以完全由 i−1i - 1i−1 列的元素得到：
A0,i=A0,i−1+1\begin{split} A_{0, i} = A_{0, i - 1} + 1 \end{split} A0,i =A0,i−1 +1
A1,i=A0,i×S+A1,i−1×T=(A0,i−1+1)×S+A1,i−1×T=A0,i−1×S+A1,i−1×T+S\begin{split} A_{1, i} &= A_{0, i} \times S + A_{1, i - 1} \times T \\ &= (A_{0, i - 1} + 1) \times S + A_{1, i - 1} \times T \\ &= A_{0, i - 1} \times S + A_{1, i - 1} \times T + S \end{split} A1,i =A0,i ×S+A1,i−1 ×T=(A0,i−1 +1)×S+A1,i−1
×T=A0,i−1 ×S+A1,i−1 ×T+S
A2,i=A1,i×S+A2,i−1×T=(A0,i−1×S+A1,i−1×T+S)×S+A2,i−1×T=A0,i−1×S2+A1,i−1×ST+A2,i−1×T+S2\begin{split} A_{2, i} &= A_{1, i} \times S + A_{2, i - 1} \times T \\ &= (A_{0, i - 1} \times S + A_{1, i - 1} \times T + S) \times S + A_{2, i - 1} \times T\\ &= A_{0, i - 1} \times S^2 + A_{1, i - 1} \times ST +
A_{2, i - 1} \times T + S^2 \end{split} A2,i =A1,i ×S+A2,i−1 ×T=(A0,i−1 ×S+A1,i−1 ×T+S)×S+A2,i−1 ×T=A0,i−1 ×S2+A1,i−1 ×ST+A2,i−1 ×T+S2
A3,i=A2,i×S+A3,i−1×T=(A0,i−1×S2+A1,i−1×ST+A2,i−1×T+S2)×S+A3,i−1×T=A0,i−1×S3×A1,i−1×S2T+A2,i×ST+A3,i−1×T+S3\begin{split} A_{3, i} &= A_{2, i} \times S + A_{3, i - 1} \times T \\ &= (A_{0, i - 1} \times S^2 + A_{1, i - 1} \times ST + A_{2, i - 1} \times T + S^2) \times S + A_{3, i - 1} \times T\\ &=
A_{0, i - 1} \times S^3 \times A_{1, i - 1} \times S^2T + A_{2, i} \times ST + A_{3, i - 1} \times T + S^3 \end{split} A3,i =A2,i ×S+A3,i−1 ×T=(A0,i−1 ×S2+A1,i−1 ×ST+A2,i−1 ×T+S2)×S+A3,i−1 ×T=A0,i−1 ×S3×A1,i−1 ×S2T+A2,i ×ST+A3,i−1 ×T+S3
AN−1,i=AN−2,i×S+AN−1,i−1×T=A0,i−1×SN−1+A1,i−1×SN−2T+A2,i−1×SN−3T+⋯+AN,i−1×T+SN=A0,i−1×SN−1+∑j=1N−1Aj,i−1×SN−jT+SN−1\begin{split} A_{N - 1, i} &= A_{N - 2, i} \times S + A_{N - 1, i - 1} \times T \\ &= A_{0, i - 1} \times S^{N - 1} + A_{1, i - 1} \times S^{N-2}T + A_{2, i - 1} \times S^{N - 3}T +
\cdots + A_{N, i - 1} \times T + S^N \\ &= A_{0, i - 1} \times S^{N - 1} + \sum_{j = 1}^{N - 1} A_{j, i - 1} \times S^{N - j} T + S^{N-1} \end{split} AN−1,i =AN−2,i ×S+AN−1,i−1 ×T=A0,i−1 ×SN−1+A1,i−1 ×SN−2T+A2,i−1 ×SN−3T+⋯+AN,i−1 ×T+SN=A0,i−1 ×SN−1+j=1∑N−1 Aj,i−1 ×SN−jT+SN−1
由于 000 号元素每次加 111，所以我们可以考虑在最后给表格加一行全为 111 的元素作为 NNN 行上的元素，接着可以把转移写成矩阵的形式。
那么我们有：
[1SS2S3S4⋯SN−100TT×S1T×S2T×S3⋯T×SN−2000TT×S1T×S2⋯T×SN−30000TT×S1⋯T×SN−400000T⋯T×SN−50⋮⋮⋮⋮⋮⋮⋮00000⋯T01SS2S3S4⋯SN−11]\left[ \begin{matrix} 1 & S & S^2 & S^3 & S^4 & \cdots & S^{N - 1} & 0\\ 0 & T & T \times S^1 & T \times S^2 & T \times S^3 & \cdots & T \times S^{N - 2} & 0 \\ 0 & 0 & T & T \times S^1
& T \times S^2 & \cdots & T \times S^{N - 3} & 0\\ 0 & 0 & 0 & T & T \times S^1 & \cdots & T \times S^{N - 4} & 0 \\ 0 & 0 & 0 & 0 & T & \cdots & T \times S^{N - 5} & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & 0 & \cdots & T & 0\\ 1 & S & S^2 & S^3 & S^4 &
\cdots & S^{N-1} & 1\\ \end{matrix} \right] 10000⋮01 ST000⋮0S S2T×S1T00⋮0S2 S3T×S2T×S1T0⋮0S3 S4T×S3T×S2T×S1T⋮0S4 ⋯⋯⋯⋯⋯⋮⋯⋯ SN−1T×SN−2T×SN−3T×SN−4T×SN−5⋮TSN−1 0000001
由于 MMM 很大，对于每个查询 (Ri,Ci)(R_i, C_i)(Ri ,Ci )，我们可以使用矩阵快速幂来计算出表格中 CiC_iCi 上的所有元素。
整个算法时间复杂度：O(QN3logM)\mathrm{O}(QN^3\log{M})O(QN3logM)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
