Namomo Winter Camp 2

排名	当场过题数	至今过题数	总题数
3/54	9	10	12

A

solved by 2sozx

题意

大模拟

题解

大模拟

B

solved by 2sozx

题意

签到

题解

签到

C

upsolved by

题意

题解

D

upsolved by

题意

题解

E

solved by

题意

题解

F

upsolved by

题意

题解

G

solved by JJLeo

题意

有 \(n\) 个人，每个人有一个坐标 \(a_i\)，现在想让第 \(i\) 个人距离第 \(i+1\) 个人距离恰好为 \(d\) (\(1 \le i < n\))，最小化每个人移动距离的最大值。(\(1 \le n \le 10^6\))

题解

先考虑第 \(i\) 个人在第 \(i+1\) 个人的左边，右边的同理，两者取最小值即可。

设第 \(1\) 个人移动到 \(x\)，则第 \(i\) 个人移动距离为 \(|a_i-x+(i-1)d|\)，相当于有 \(n\) 个点要移动到 \(x\)，显然最小值为 \(\dfrac{\max(a_i(i-1)d) - \min(a_i(i-1)d)}{2}\)。

H

solved by JJLeo

题意

FFT 模板题。

题解

卷！

I

upsolved by JJLeo

题意

给定长度为 \(n\) 的序列 \(a_1,a_2, \cdots,a_n\)，\(m\) 次询问区间 \([l_i,r_i]\) 内所有区间和不超过 \(u_i\) 的最大值。(\(1 \le n \le 2000, 1\le m \le 2 \times 10^5\))

题解

离线所有询问，按 \(u_i\) 从小到大排序，题目转化为 \(A_{n \times n}\) 矩形中修改某个数，以及查询 \(\max \limits _{l_i \le x,y \le r_i} A_{x,y}\)。注意到只有 \(x \le y\) 才是有效区间，因此所有 \(x > y\) 的点值均为负无穷，所以上述查询等价于 \(\max \limits _{x \ge l_i, y \le r_i} A_{x,y}\)，两个维度维一个是后缀和另一个是前缀和，可以使用二维树状数组维护，复杂度为 \(O((n^2+m) \log ^2 n)\)。究极卡常，如果第二个性质使用了线段树套线段树，就会 TLE on test 5 到自闭。

J

solved by JJLeo

题意

矩阵求逆模板题。

题解

消！

K

solved by

题意

题解

L

solved by

题意

题解

记录

总结