NEUQ 2025 Winter Contest 1 Solution

· · 题解

Problem A. 查找数字

stl 做法 1：

使用 map<int,vector<int>>。对于每个值记录每次出现的位置，询问时直接输出即可。

stl 做法 2：

使用 map<pair<int,int>,int>。对于序列 a 中每个数用另一个 map 求出它当前是第几次出现在序列 a 中，与这个数的值组成一个 pair，用 map<pair<int,int>,int> 记录当前 pair 对应的下标，询问时直接输出即可。

以上两种做法时间复杂度均为 \Theta((n+q)\log n)。

非 stl 做法众多，不在题解中阐述。

Problem B. 打印文件

枚举先将文件传输至哪一台打印机，分别计算可以打印的文件数，取较大值输出即可。

时间复杂度为 \Theta(1)。

Problem C. 信号干扰

定义一个区间结构体，包含两个元素 l 和 r，代表一段区间，对于两个区间结构体 x,y，定义 x<y 当且仅当 x.r<y.l。

用 set 储存以上区间结构体，称 set 的名字为 s，对于一个区间结构体 x，它与 set 中所有区间均不相交当且仅当 s.find(x)==s.end()。

对于一个 i，我们从第 i 个区间开始，往 set 中插入区间，直到下一个区间与 set 中的区间相交为止，此时加到的区间下标即为 a=i 时的答案。

从 a=i 的情况变为 a=i+1 的情况，只需要在 set 中删除第 i 个区间，然后重复执行以上过程即可。

于是可以在 \Theta(n\log n) 的时间复杂度内解决该题。目前没有更快的做法。

这是一个非常实用的 trick，建议大家学习。

Problem D. 关机 BOT

显然，两个 BOT 会相撞当且仅当它们的 c 不同且 p-t 相等。

对于不同的 c，记录每种 p-t 的出现次数。最后对于每种 p-t，取两种 c 中出现次数的较小值相加即可。

实际实现时可以提前开一个大数组，取中间的地址，用指针访问负下标。也可以每次加一个固定值，将负下标转移为非负下标。也可以使用 map，直接访问负下标。

认为 n,p,t 同级，则时间复杂度为 \Theta(n) 或 \Theta(n\log n)。

Problem E. 优美区间

注意到：对于一个 r，不同的 \gcd(a_l,a_{l+1},\dots,a_r) 至多只有 \lfloor\log a_r\rfloor+1 种。

当我们对于一个 r=x 求出了所有不同的 \gcd(a_l,a_{l+1},\dots,a_r) 并找到了与之对应的最小的 l 后，要求出 r=x+1 的情况。只需要在 l 的集合中插入 x+1，并将对应的 \gcd 相同的 l 只保留最小的即可。

于是对于每个 r，我们都可以求出所有不同的 \gcd(a_l,a_{l+1},\dots,a_r) 和与之对应的最小的 l，依次对这些区间中长度至少为 k 的区间计算优美程度，并取最大值即可。

时间复杂度为 \Theta(n\log^2 a)，常数较小，可以通过本题。精细实现或使用科技可以做到 \Theta(n\log a) 的复杂度。