2018 ACM-ICPC Shenyang Regional Onsite

Replay

zerol: 没来

Problem C

Solved by zerol & ultmaster. 02:09 (+1)

题意：求有多少 $1$ 到 $n$ 的排列满足：将前 $k$ 个的数排列以后，最长上升子序列长度为 $n-1$ 以上。

题解：分四种情况讨论：

1. 排序之后整个就有序了：$k!$

2. 排序之后前面是 $1$ 到 $k$，后面最长上升子序列的长度是 $n-k-1$：$(n-k-1)^2 k!$

3. 前 $k$ 个数里有一个被换成了 $k+1$，被换的那个数可以插到后面里面去：$k! \cdot k(n-k)$。

4. 前 $k$ 个数里有一个（只能是 $k$）被换成了 $k+2$ 以上的数，后面 $n-k$ 个数必须有序：$k! (n-k-1)$。

综上，答案就是 $k!(1+(n-k-1)^2+k(n-k)+(n-k-1))$。

Problem E

Solved by kblack. 02:27 (+)

题意：平面上有 $N$ 个有颜色点，求第 $l$ 到 $r$ 的不同颜色点间的最远曼哈顿距离，修改位置和颜色。

题解：曼哈顿距离最远，肯定先转切比雪夫距离啦，然后用线段树维护区间内不同颜色的两个维度的最大次大就好了。

Problem G

Solved by ultmaster. 03:08 (+2)

题意：有四种操作：增加点、删除点、修改和一个点距离为 $\sqrt{k}$ 的所有点的点权，询问和一个点距离为 $\sqrt{k}$ 的所有点的点权。

题解：距离为 $\sqrt{k}$ 的所有点是不多的。直接暴力即可。注意判断差为正负或为 0 的情况。

Problem J

Solved by kblack. 00:16 (+)

温暖的签到题。

Problem K

Unsolved. (-4)

Problem L

Solved by kblack. 01:29 (+3)

题意：一个大圆，被几个圆咬几口，问剩下的直径。

题解：大讨论，整个圆被吃掉的时候答案是 $0$，其他情况直径来自于两个地方：原本圆的直径和交点之间的距离，把角度扔一起，扫描线一下就好了。