2023NOIP A层联测32

文章目录

2023NOIP A层联测32
- A flandre
- B.meirin
- C.sakuya
- D. 红楼 ~ Eastern Dream
- 总结

A flandre

有 $n$ 种烟花，每种烟花有两个参数 $a ， b$ ，你要构造一种燃放顺序，使得 $b$ 的和最大， $b$ 会改变，具体来说：设 $i$ 在 $j$ 前燃放，那么。

$a_i < a_j$ ，则 $jb_j +k \to b_j$
$a_i = a_j$ 则 $b_j$ 不变
$a_i >a_j$ 则 $jb_j – k \to b_j$

$1\le n \le 10^6$

这个题考场就想到了正解。思考一下，最优方案满足一个性质，将 $a$ 从小到大排序，依次燃放。暴力求答案，然后选出最优的方案就好了，可惜有一个变量没有给初始值挂了 $70$ 分，关键是大样例还过了。

B.meirin

给定两个序列 $a, b$

$q$ 次操作，每次把 $b$ 的 $[l, r]$ 的每个值加上 $k$ ，每次操作后查询：
$9+7)\sum _{l = 1} ^n \sum_{r = l}^n(\sum_{i= l}^r a_i) \times (\sum_{i= l}^r b_i) \mod (10^9 + 7)$
$\le 5 \times 10^5$

因为修改的是 $b$ 的值，我们就可以考虑把 $[l, r]$ 里面的值对答案的影响算出来。

设 $sum1_i$ 是 $\times a_i$ 的前缀和， $sum2_i$ 就是 $\times a_i$ 的前缀和。

每个 $b_i$ 的贡献就是 $)sum1_{i – 1}\times (n – i + 1) +sum2_{i + 1} \times i +a_i \times i \times(n – i + 1)$

用一个前缀和维护一下这个值就可以做到 $O (1)$ 修改。

考场最后 $30 min$ 才想到正解，但是码了 $15 min$ 发现只能过小样例过不了大样例，考后才发现是快写打错了。

C.sakuya

有 $n$ 个房间构成了一棵树，边有边权。树上有 $m$ 个特殊的房间，求走完这些房间的期望。

每次修改会使得连接 $x$ 的所有边加上 $k$

$\le 5 \times 10^5$

考虑修改一条边的影响，就是这条边两端的特殊房间的数量的乘积。

先把答案求出来，每次修改的时候就是把答案加上这个影响乘上 $k$ 就好了。

D. 红楼 ~ Eastern Dream

给出一个长度为 $n$ 的序列 $a$ ，有 $m$ 次操作，格式如下：

$1, x, y, k$ 对于所有满足 $\mod x \le y$ 的 $i$ ，将 $a_i$ 加上 $k$
$2, l, r$ 求 $i\sum_{i= 1}^r a_i$

$\le 2 \le 10^5$

根号分治。维护两个数组 $v_{i , j} , vs_i$ ，表示对于所有 $\mod i = j$ 的 $x$ ， $a_x$ 要加上的值， $vs_{i , j} $ 是 $v _{i , j}$ 的前缀和，即对于所有 $\mod i \le j$ 的 $x$ ， $a_x$ 要加上的值。

$x\le \sqrt n$ 可以直接修改。

$x\ge \sqrt n$ 需要用分块维护差分

总结

期望得分： $100 + 100 + 0 + 25 = 225$

实际得分： $70 + 30 + 0 + 25 = 115$

这次本来是一个信心场，但还是失误了。两个题想到正解都挂了，一个是忘记设初值，一个是快写打错，就是自己的代码实现能力不足了。而且码完一个题可以考虑先检查一小会。 $T 3$ 还没有拿到暴力分，遇到这种自己不熟练的题目，可以打打暴力，而不是直接就跳了。

2023NOIP A层联测32