2018 ICPC Asia Singapore Regional Contest

From EOJ Wiki
Jump to: navigation, search

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 (+)