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)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------