Educational Codeforces Round 7 题解

__vector__ · 2025-01-08 10:05:32 · 题解

A

每个序列的长度递增的，容易证明只需要 O(\sqrt n) 个序列，总长度就能超过 n。

B

scanf("%d:%d") 可以较为快捷的读入。

C

求给定子数组中哪个位置上的数不等于给定的数 x。

考虑预处理每种数字在哪些区间没有出现过，并以端点升序记录。

查询的时候，如果存在一个合法的区间，那么右端点大于等于 l 的最小的区间一定是合法的。

D

长度为 2n 的数列，包含 [1,n] 的数，每个数出现了两次，令 d_i 为 i 的两次出现位置的差。

求如何排列这个序列，使得 \sum\limits_{i=1}^n (n-i)|d_i+i-n| 最小。

注意到原式的每一项都大于等于 0，总和也大于等于 0。

猜想存在一种构造方案使得这个值是 0。

这就要求每一项都构造出 0。

由此可得 d_1=n-1,d_2=n-2,d_3=n-3,\cdots,d_{n-1}=1，d_n 可以等于任何值。

首先将两个 1 放到 1,n 的位置，两个 3 放到 2,n-1 的位置，依次类推。

然后把两个 2 放到 n+1,2n-1 的位置，两个 4 放到 n+2,2n-2 的位置，依次类推。

最后如果剩下两个位置，那就用来放 n。

E

给定一棵树，每个叶子节点有一只蚂蚁。

每秒可以同时移动一些蚂蚁，但要求除了 1 以外任何节点不能有超过两只蚂蚁，求最少多少秒将所有蚂蚁移动到 1。

注意到 1 的每个子树都是独立的，可以对于每个子树单独算答案，最后取 max。

考虑单个子树内部，让深度最浅的蚂蚁先去。

随后，深度第 2 浅的蚂蚁至少在前一只蚂蚁的下一秒才能到达终点，这个时间与自己原本与 1 的距离取 max 就是真实时间。

后面依次类推就可以。

本题思路在于先将整个问题拆分为多个同类的子任务。

对于单个子任务，考虑实际顺序是怎么样的，根据这个过程去逐步递推求解。

F

给定 n,k，求 \sum\limits_{i=1}^{n} i^k \pmod {{10}^9+7}，n \le 10^9,k \le 10^6。

本题的答案是一个 k+1 次多项式，但是我不会证明，这个坑以后再填。

拉格朗日插值的复杂度是 O(k^2) 的，但是可以带入一些特殊值优化计算过程，此处代入 1,2,\cdots,k+2。

回想一下拉格朗日插值的形式，给定 n 组 x_i,y_i，代表 f(x_i)=y_i。

然后 f(p) = \sum\limits_{i=1}^n \frac{\prod\limits_{j \in [1,n],j\neq i}(p-x_j)}{\prod\limits_{j \in [1,n],j\neq i}(x_i-x_j)} y_i。

回到本题，式子变为：