2020 ICPC 南京

排名	当场过题数	至今过题数	总题数
7/549	7	10	13

A

upsolved by

题意

题解

B

upsolved by

题意

题解

C

upsolved by JJLeo

题意

二维平面上有 $n$ 个点，初始在 $(0,0)$，只能向上下左右四个方向移动，走到与某个点横坐标或纵坐标相同就可以吃到它，问吃掉所有点最少走多少距离。($1\le n\le {10}^5$)

题解

先按横坐标排序，显然此时必然是选择一个区间用横坐标吃，然后前缀后缀没选的用纵坐标吃。考虑当选择区间的左端点为 $1,2,\cdots ,n$ 时最小值分别是多少，再取全局最小值即可。

前缀后缀的纵坐标最大最小值可以用单调栈+线段树维护，左端点向右向右移动时相当于把左边的一个元素移动到最右侧，用单调栈更新区间即可，时间复杂度为 $O(n\log n)$。

需要注意的是当横（纵）坐标的最大最小值分别上述 $M,m$ 时，令 $M^{\prime }=max(0,M),m^{\prime }=min(0,m)$ 答案为 $min(2M^{\prime }-m^{\prime },M^{\prime }-2m^{\prime })$，维护的时候注意一下细节即可。

D

upsolved by JJLeo

题意

给出一个 $n$ 个节点 $m$ 条边的图，求出一个所有节点的度都不超过 ${\displaystyle \frac{n}{2}}$ 的生成树，或判断无解。

题解

先随便求出一个生成树，如果符合条件直接结束。

否则可以证明最多存在一个点的度超过 ${\displaystyle \frac{n}{2}}$，以这个点为根，枚举所有非树边，如果它们两个属于根节点不同的子树，那么就可以连接这条边，删掉某一条和根相连的边，使根的度数减少 $1$，直到最终符合条件。

可以发现，每次相当于合并两个子树，需要使用并查集来完成，如果最终所有边都用过了还是不满足条件，那么必然是不存在解的。

另外，有可能根节点合法了，但是另一个节点度数太大了，可以证明因为当根节点恰好满足条件时就结束，如果此时有一个点的度数过大，那么它必然与根节点相连，所以我们只需要删边时需要注意一下：如果非树边的两个节点一个与根相连一个不与根相连，则删掉前者与根相连的边；如果两个节点都与根相连，则选择度数小的那一个。

可以发现，当 $n=3$ 时必然无解，当 $n>3$ 时不可能存在有 $2$ 个以上与根相连的子树度数都为 ${\displaystyle \frac{n}{2}}-1$ 的情况，因此这样做只要有合法解就一定可以将其构造出来。

E

solved by Bazoka13

题意

题解

F

solved by 2sozx JJLeo

题意

求 $f(x)={\displaystyle \frac{nx+m}{1-{(1-{\displaystyle \frac{p}{10000}})}^x}},x\in N$ 的最小值。

题解

导数单调，先减后增，二分即可。

G

upsolved by

题意

题解

H

solved by 2sozx Bazoka13

题意

$n\times m$ 二维矩阵，每个位置有 $3$ 种颜色，问有多少种染色方式使得存在一种合法情况。一种合法情况定义为存在4个点在一个矩形的四个顶点，并且上面两个点颜色相同并且下面两个点颜色相同或者左侧两个点颜色相同并且右侧两个点颜色相同。$n,m\le 2\times {10}^3$

题解

$min(n,m)=1$ 时答案为0需要特判
我们取其中两行考虑是否有情况可以快速统计，两列同理
显然两行最多只存在 $3\times 3=9$ 种排列方式，因此 $m>9$ 时无论如何填都会有合法情况
再仔细考虑这9种排列，显然 $(1,1),(2,2)$ 如果同时出现就是一种合法情况，因此其实最多只有 $2\times 3+1=7$ 种排列，$m>7$ 时就一定会有合法情况

因此对于 $max(n,m)\le 7$ 时可以打表，否则答案即为 $3^{nm}$

I

upsolved by JJLeo

题意

二维平面上给出 $n$ 条线段为障碍，一个点从最下方走到最上方，横坐标绝对值不能超过 $m$，$y$ 方向速度分量恒为 $1$，问 $x$ 方向速度分量的最大值最小为多少。($1\le n\le 100$，$1\le m\le {10}^4$)

题解

可以证明最优方案一定是沿着线段端点的折线走，直接暴力处理任意两点间是否合法，然后 dfs 即可，需要注意如果一条线段端点在边界处，那么不能卡着它向上走，要特判掉。

J

solved by 2sozx JJLeo

题意

$n$ 堆石子，第 $i$ 堆石子数量为 $a_i$。$q$ 次询问，有以下两种操作：

• 区间取 $max$。
• 选取一个区间里面的石子，再额外加一堆有 $x$ 个石子的石子堆。用上述这些石子堆开始玩 nim 游戏，问先手第一次操作有多少种不同的方案保证他能必胜。

($1\le n,q\le 2\times {10}^5$)

题解

Warning

这个吉司机线段树是假的，而且不好写，虽然能过本题，但复杂度未知。

nim 游戏先手必须保证操作后异或和为 $0$ 才能获胜，因此方案即为有多少堆的石子数二进制表示下有异或和最高位 $1$，因为这一位必须要由 $1$ 变为 $0$，变完后低位后可以任意变，且只有唯一一种方案。

题目转化为，区间取 $max$，区间求异或和，区间求某一位 $1$ 的数量，可以用吉司机线段树来完成。

吉司机线段树要维护四个量，最大值，次大值，最小值，最大值的个数，up 的时候直接来就可以，cover 的时候分为三种情况：

• 最大值小于等于要取 $max$ 的值，直接全部覆盖，并终止向下递归。
• 次大值小于等于要取 $max$ 的值，因为有最大值的数量，也可以进行修改，并终止向下递归。
• 否则不做修改，继续向下递归。

另外，递归过程如果最小值大于等于要取 $max$ 的值，则直接终止递归。down 时并不需要额外打标记，只需要判断自己的最小值是不是大于儿子的最小值，如果大于某个儿子说明自己更改过且没有往下传，此时 cover 该儿子即可。

本题额外维护的量也应该在 cover、up 时进行对应的更改。

K

solved by 2sozx JJLeo

题意

求一个 $1$ 到 $n$ 的排列，使得恰有 $k$ 个 $i$ 满足 $gcd(i,p_i)=1$。($1\le n\le {10}^6,0\le k\le n$)

题解

如果 $k=0$ 显然无解，因为 $1$ 与任何正整数互质。

否则，如果 $k$ 是奇数，$p_1=1$，之后 ${\displaystyle \frac{k-1}{2}}$ 对互换；如果 $k$ 是偶数，直接 ${\displaystyle \frac{k}{2}}$ 对互换。

L

solved by 2sozx JJLeo

题意

数轴上有红点和蓝点，你需要找到一个位置，使得尽可能多的红点满足到该位置的距离小于任意一个蓝点到该距离的位置。

题解

等价于求最大连续红点的数量，如果蓝红重合，则红点作废。

M

solved by JJLeo

题意

给出一颗 $n$ 个节点的树，每个点有一个生命值，每个点的权值为自己的生命值加上所有活着的子节点的生命值。你可以事先恰好杀死 $0,1,2,\cdots ,n$ 个节点，问对于上述 $n+1$ 种情况，所有活着的点的权值之和最小是多少。($1\le n\le 2\times {10}^3$)

题解

树形背包 dp，$f_{i,j,k}$ 表示以节点 $i$ 为根的子树中，杀了 $j$ 个点，$i$ 这个点有没有被杀，此时所有活着的点的权值之和的最小值。时间复杂度为 $O(n^2)$。

记录

0min：常规开题，MJX看过南京的榜感觉很自闭，CSK 码 E
12min：ZYF 冲 K，AC，冲L
20min：ZYF AC，CSK继续码E
33min：CSK AC，ZYF 暴力莽跑F
39min：ZYF WA F，二分导数后AC，冲M
72min：ZYF AC，MJX发现H可推结论打表，CSK打表，MJX冲J
176min：MJX 离谱了两次后AC，MJX冲J，寄
210min：MJX现场教ZYF segment tree beats，ZYF AC
till end：CSK疯狂写A，ZYF疯狂写C，MJX疯狂挂机
after end：ZYF if判断写错了，寄

总结

• MJX 玛丽不足，自闭
• ZYF 玛丽也不足，也自闭