2019 - 2020 ICPC Southwestern European Regional Programming Contest

rank solved A B C D E F G H I J K L
10 8 O O O . . O O . O O O .

A

Solved by XLor (01:40).

由于欧拉距离和最大为 $100$,每个点记一下每个距离的最小花费,跑一跑最短路即可。

B

Solved by XLor (00:06).

签到。

C

Solved by XLor (00:13, +1).

签到。

F

Solved by XLor (00:21).

模板。

G

Solved by XLor (04:20, +3).

显然,从左到右扫一遍,把尽量小的放在前面。

值域只有 $200$,每扫到一个位置,按顺序遍历,找到第一个可以放过来的,放下。

如何检查能否放过来?可以对每个值维护一个最优匹配指针,指向这个值最优能匹配到什么位置,并标记出已被删除(拿到前面确定位置)。

我的做法是维护将每个值的第一个放到最前面,还需要移除多少个不相邻的元素。

I

Solved by XLor(00:03).

签到。

J

Solved by XLor(04:53).

给定一个中序遍历序列,数一下有多少个二叉树的中序遍历序列是这个,并且对所有点满足父亲小于等于儿子。

如果最小值只有一个,那么显然就是拿出最小值,左右两边是二叉树的儿子。但是如果最小值有很多个,这些最小值可以拿出来造一棵二叉树,分割开来的区间填成儿子。

$n$ 个点构成的二叉树有 $H(n)$ 个(卡特兰数),再乘上所有儿子的方案数,递归分治解决即可。

K

Solved by XLor(03:08, +5).

给定一个有向图,有一个关键点,对于它的所有出边,判断是否有不经过这个出边的路径,还能走到对应的点。

将它的所有出边删除,问题就等价于对每个与关键点相邻的点,是否能连到另外一个与关键点相邻的点。

从每个相邻点开始 dfs,对他们维护一下哪些点可以走到这里。如果除了这个点本身,还有其他点能进来,这个点就不行。