2018 ICPC Asia Singapore Regional Contest

Problem A

Solved by Kilo_5723. 00:59:24 (+)

Problem B

Solved by Xiejiadong. 00:35:08 (+)

题意：可以在 $n$ 个点中选择一个点作为信号基站，信号的传递是跳边（间隔传递）的，求添加最小数量的边，使得消息传遍全图。

题解：显然如果图中有 $n$ 个联通块，我们需要用 $n-1$ 条边将他们连接起来。

而此时无法把信息传遍全图的情况，只剩下了，这张图是二分图的情况。显然在不同联通块之间加边并不会影响是否是二分图，直接判断即可。

Problem C

Solved by Weaver_zhu. 00:43:14 (+)

Problem D

Solved by Kilo_5723. 04:44:16 (+11)

Problem E

Unsolved.

Problem F

Solved by Xiejiadong. 02:56:54 (+5)

题意：给出长度为 $n$ 的数列，求字典序最小的长度为 $4$ 的子序列，满足 $ABAB$ 的形式。

题解：如果我们把每个数所有的位置取出来，假设数字 $x$ 出现了 $y$ 次，位置分别是 $x_1,x_2,\cdots ,x_y$ ，可以发现满足 $ABAB$ 的形式的长度为 $4$ 的子序列一定是两个连续位置的 $A$ 和连续位置的 $B$ 组成的。

于是我们考虑组成数对 $(x_1,x_2),(x_2,x_3),\cdots (x_{y-1},x_y)$ 于是就是找对于不同的两个数 $a,b (a\neq b)$ ，满足 $a_1 < b_1 < a_2 < b_2$ 的最小字典序。

我们可以通过线段树维护第一维，插入第二维，维护 MAX ，于是可行性，可以通过查询区间 MAX 然后比较。

我们可以通过从小到大枚举第一维，然后判断可行性，一旦可行，直接暴力找到字典序最小的第二维，输出可行解。

Problem G

Unsolved.

Problem H

Unsolved.

Problem I

Unsolved.

Problem J

Solved by Weaver_zhu. 00:17:28 (+)

Problem K

Solved by Kilo_5723. 03:10:39 (+1)

Problem L

Solved by Kilo_5723. 00:15:15 (+)