2018-2019 ACM-ICPC, Asia Nakhon Pathom Regional Contest

Problem A

Unsolved.

Problem B

Unsolved. (-2)

Problem C

Solved by Xiejiadong. 00:24 (+)

简单的 dp 签到。

Problem D

Solved by Xiejiadong. 00:08 (+)

题意：要使得每个地点的 $10$ km 范围内有一个公交车站，求最少需要的公交车真。

题解：贪心。对地点的距离排序以后，每一次公交车站一定放在一个没有公交车站的最靠前的地点之后 $10$ km 处。扫一遍即可。

Problem E

Upsolved by Xiejiadong. (-1)

题意：如果任意元素满足 $|x-y|\le 2$ ，那么元素 $x$ 和 $y$ 输入同一类，类关系可以传递，允许将两个数 $+1/-1$ 操作，求最大的类元素个数。

题解：排序以后，每次的改变都只会影响到周围的数。

因为如果数相同的话，改变以后仍然为一类；如果数不相同，改变并不会使得排序的结果发生变化。

于是就可以考虑 dp 。 $f[i][j][k]$ 表示处理到第 $i$ 个数，已经修改了 $j$ 次，第 $i-1$ 个数的状态是 $k(0/+1/-1)$ 。

枚举 $9$ 种状态的转移即可，需要注意 $f[i][0][k\neq 0]=0$ ，因为修改了 $0$ 次，最后一位状态不可能非 $0$ 。

比赛的时候尝试大讨论，看起来讨论不清楚。

Problem F

Solved by Kilo_5723 && Xiejiadong. 04:16 (+1)

题意：求杨辉三角中前 $n$ 行中能被 $7$ 整除的数的个数。

题解：杨辉三角模素数的余数是分形，用分形的规律做。

Problem G

Solved Weaver_zhu && Kilo_5723. 01:02 (+)

题意：给定有向图，求强连通分量个数。

题解：Tarjan 裸题。

Problem H

Solved by Kilo_5723. 01:42 (+)

题意：给出 $x^3$ 对三个互素的数的余数，求 $x$。

题解：枚举 $x$，逐个判断。

Problem I

Unsolved.

Problem J

Solved by Kilo_5723. 00:20 (+)

题意：求 $\sum_{i=low}^{high} (\sqrt[3]{i+10^{-15}}-\sqrt[3]{i})$。

题解：由于 $10^{-15}$ 很小，令 $f(x)=\sqrt[3]{x}$，相当于求 $10^{-15} \cdot\sum_{i=low}^{high} f'(i)$。

Problem K

Solved by Xiejiadong && Weaver_zhu. 04:21 (+)

题意：每个数有出现的一个时间区间，每次询问一个时间点的第 $k$ 大数。

题解：会有重复的数，没法 pb_ds 。

对时间离散以后，用平衡树维护即可。

Problem L

Solved by Weaver_zhu. 00:53 (+)