Difference between revisions of "2018 ICPC Asia Singapore Regional Contest"

From EOJ Wiki
Jump to navigation Jump to search
(Created page with "== Problem A == Solved by Kilo_5723. 00:59:24 (+) == Problem B == Solved by Xiejiadong. 00:35:08 (+) == Problem C == Solved by Weaver_zhu. 00:43:14 (+) == Problem D ==...")
 
 
(2 intermediate revisions by the same user not shown)
Line 6: Line 6:
  
 
Solved by Xiejiadong. 00:35:08 (+)
 
Solved by Xiejiadong. 00:35:08 (+)
 +
 +
题意:可以在 $n$ 个点中选择一个点作为信号基站,信号的传递是跳边(间隔传递)的,求添加最小数量的边,使得消息传遍全图。
 +
 +
题解:显然如果图中有 $n$ 个联通块,我们需要用 $n-1$ 条边将他们连接起来。
 +
 +
而此时无法把信息传遍全图的情况,只剩下了,这张图是二分图的情况。显然在不同联通块之间加边并不会影响是否是二分图,直接判断即可。
  
 
== Problem C ==
 
== Problem C ==
Line 22: Line 28:
  
 
Solved by Xiejiadong. 02:56:54 (+5)
 
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 ==
 
== Problem G ==

Latest revision as of 07:18, 6 October 2019

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