10
ACGO 巅峰赛#18 题解
本场巅峰赛的所有题目的难度评级为:
题目编号 题目标题 难度 A. 数组中未出现的 K 的最小倍数 入门 B. 美丽数 III 普及- C. 元素距离积(简单) 入门 D. 元素距离积(困难) 普及 E. 最小化两数组的距离 普及+/提高 F. 统计操作后不同的序列 提高+/省选-
本场比赛题目侧重对于选手数学能力的考察,其中:
D\tt{D}D 题 和 E\tt{E}E 题考察了拆解「绝对值」和根据数据范围变换代数式求解的方法。
F\tt{F}F 题考察了对于「平均数」的处理技巧和方法。
以上方法皆为算法竞赛中常见的数学处理方法。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题目解析
A - 数组中未出现的 K 的最小倍数
模拟;枚举
我们可以直接从小到大枚举 KKK 的倍数 XXX,并检检查数组中是否存在 XXX 即可;
由于 K(≤9)K(\le 9)K(≤9) 和 Ai(≤100)A_i(\le 100)Ai (≤100) 的值域都比较小,所以 XXX 最多不会超过 108108108。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
B - 美丽数 III
数学;枚举
令 KKK 为「美丽数」的位数,不难发现 K≥2K \ge 2K≥2,同时 K=2K = 2K=2 的「美丽数」有 363636 个,K=3K = 3K=3 的「美丽数」也有 363636 个……
「美丽数」每增长 111 位,就会多出 363636 个「美丽数」,所以要想知道第 NNN 个「美丽数」,我们就可以先计算出其位数 KKK,再枚举 aaa 和 bbb 即可。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
C - 元素距离积(简单)
模拟;枚举
按照题意,使用双重循环枚举 iii 和 jjj 计算答案;计算绝对值可以使用内置函数 abs。整个代码时间复杂度为 O(N2)\mathrm{O}(N^2)O(N2)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
D - 元素距离积(困难)
数学;枚举;计数
我们先处理题目式子中的绝对值。
由于 ∑i=1N∣i−i∣×∣Ai−Ai∣=0\sum_{i=1}^N \vert i - i \vert \times \vert A_i - A_i \vert = 0∑i=1N ∣i−i∣×∣Ai −Ai ∣=0,所以原式可化为:
(∑i=1N−1∑j=i+1N(j−i)×∣Ai−Aj∣)×2\left( \sum_{i=1}^{N-1}\sum_{j=i+1}^N (j - i) \times \vert A_i - A_j \vert \right) \times 2 (i=1∑N−1 j=i+1∑N (j−i)×∣Ai −Aj ∣)×2
注意到,本题 Ai(≤500)A_i(\le 500)Ai (≤500) 的范围较小,我们可以围绕此,对上式进行变换,从而高速计算。
对于上式,我们考虑枚举 iii,同时
令 cntxcnt_xcntx 代表 iii 之前所有元素中值 xxx 出现的次数;
令 sumxsum_xsumx 代表 iii 之前所有元素中值为 xxx 的下标之和;
那么可以将上式转化为:
(∑i=1N∑x=0500(i×cntx−sumx)×∣Ai−x∣)×2\left( \sum_{i = 1}^{N} \sum_{x=0}^{500} (i \times cnt_x - sum_x) \times \vert A_i - x \vert \right) \times 2 (i=1∑N x=0∑500 (i×cntx −sumx )×∣Ai −x∣)×2
计算上式的时间复杂度为 O(N×max(A))\mathrm{O}(N \times \max(A))O(N×max(A)),这样我们便可以高效地计算出答案。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
E - 最小化两数组的距离
数学;枚举;二分
对于只交换 111 对二元组的情况,我们直接枚举 AAA 中要交换的二元组和 BBB 中要交换的二元组即可,时间复杂度 O(N2)\mathrm{O}(N^2)O(N2)。
我们主要考虑交换 222 对二元组的情况。
首先考虑 S\tt{S}S,在未交换交换元素时,令:
diffS=∑iNAxi−∑iNBxi\tt{diffS = \sum_i^NAx_i - \sum_i^NBx_i} diffS=i∑N Axi −i∑N Bxi
此时若交换的 111 对二元组分别为 AiA_iAi 和 BjB_jBj ,那么:
S=∣diffS−2×(Axi−Bxj)∣\tt{S = \vert diffS - 2 \times (Ax_i - Bx_j) \vert} S=∣diffS−2×(Axi −Bxj )∣
对于交换 222 对二元组的情况,我们只需要将 AAA 中的元素两两结合,BBB 中的元素两两结合,就可以把选择 222 对二元组交换转化为选择 111 对两两结合后的二元组交换。
那么对于上式,我们可以枚举 Axi\tt{Ax_i}Axi ,二分 Bxj\tt{Bx_j}Bxj 。
具体的,我们把 BBB 的两两结合的 Bxj\tt{Bx_j}Bxj 排序去重,然后找到最大的 Bxj\tt{Bx_j}Bxj 使得 diffS−2×(Axi−Bxj)<0\tt{diffS - 2 \times (Ax_i - Bx_j) \lt 0}diffS−2×(Axi −Bxj )<0,此时 Bxj\tt{Bx_j}Bxj 和 Bxj+1\tt{Bx_{j + 1}}Bxj+1 即为与 Axi\tt{Ax_i}Axi 交换后能够使得 S\tt{S}S 最小的两个元素,其中 Bxj\tt{Bx_j}Bxj 或 Bxj+1\tt{Bx_{j + 1}}Bxj+1
可能有一个不存在,要注意判别。
对于 T\tt{T}T 同理。
整个算法时间复杂度 O(N2logN2)\mathrm{O}(N^2\log{N^2})O(N2logN2)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
F - 统计操作后不同的序列
数学;前缀和;枚举;计数
每次操作后都可以得到一个序列,(L,R)(L, R)(L,R) 二元组的总数量是 N(N+1)2\dfrac{N(N + 1)}{2}2N(N+1) 。
我们考虑将其中操作后得到的重复序列去除掉。
令 X=∑i=LRAiR−L+1X = \dfrac{\sum_{i=L}^R A_i}{R - L + 1}X=R−L+1∑i=LR Ai ,那么对于 AL=XA_L = XAL =X 或 AR=XA_R = XAR =X 的情况,我们将 LLL 向右边移动 111 或将 RRR 向左移动 111,操作后的序列不会发生变化。
我们考虑找到那些使得 (AL,…,AR)(A_L, \ldots, A_R)(AL ,…,AR ) 的平均值与 ALA_LAL 或 ARA_RAR 相等的 (L,R)(L, R)(L,R) 将其从总数中去掉。
具体地,对于 x=1,…,maxAx = 1, \ldots, \max{A}x=1,…,maxA,进行如下操作:
定义 (B1,…,BN)=(A1−x,…,AN−x)(B_1, \ldots, B_N) = (A_1 - x, \ldots, A_N - x)(B1 ,…,BN )=(A1 −x,…,AN −x) 并构造 BBB 的前缀和序列 (S0=0,S1=B1,…,SN=∑i=1NBi)(S_0 = 0, S_1 = B_1, \ldots, S_N = \sum_{i=1}^N B_i)(S0 =0,S1 =B1 ,…,SN =∑i=1N Bi )。
对于 i=1,…,Ni = 1, \ldots, Ni=1,…,N:
* 若 Bi=0B_i = 0Bi =0,则从答案中减去满足 0≤j<i0 \le j < i0≤j<i 且 Sj=SiS_j = S_iSj =Si 的 jjj 的个数。
对应平均值为 xxx、右端为 xxx 而左端任意的情况。
* 若 Bi≠0B_i \ne 0Bi =0,则从答案中减去满足 0≤j<i0 \le j < i0≤j<i 且 Bj+1=0B_{j+1} = 0Bj+1 =0 且 Sj=SiS_j = S_iSj =Si 的 jjj 的个数。
对应于平均值为 xxx、右端不为 xxx 而左端为 xxx 的情况。
对于每个 xxx 的计算时间复杂度为 O(N)\mathrm{O}(N)O(N)。
因此,整体的时间复杂度为 O(NmaxA)\mathrm{O}(N\max{A})O(NmaxA)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
有帮助,赞一个