2017-2018 ACM-ICPC German Collegiate Programming Contest

Problem A

Solved by kblack. 03:43 (+1)

题意：给三种颜色 $N$ 个点，要求搞两个不相交的多边形，使得每种颜色被隔开。

题解：上下分别开一个矩形当总线，当一列中有点需要接收时，拉一个矩形上去，分别从左侧和右侧连接（包含），与官方题解的方法 2 一致。

Problem B

Solved by ultmaster. 00:32 (+)

温暖的 Burnside 签到。

Problem C

Solved by ultmaster. 01:04 (+)

题意：非常繁琐。反正是跑一个每个点拆成 $x$ 个时间点的最短路。

题解：如题意。注意每个点可以待在上面不动（不然过不了样例）。

Problem D

Solved by kblack. 00:40 (+)

题意：给一些有向边，询问一对点之间有无偏序。

题解：$N$ 很小，Floyd 一下把所有的顺序求出来。

Problem E

Solved by zerol. 01:47 (+6)

题意：有向图判负环。

题解：用 spfa 判负环。注意对于每个点都必须访问过，即使在一个联通快里。

zerol: 我有向图建成无向图了，spfa 还写错，罚钱。

Problem F

Solved by ultmaster. 02:29 (+)

题意：二分图匹配。左边可以选一个点配右边三个点。

题解：朴素的想法就是跑完一遍匹配之后把遍历左边的点，然后依次把每个点的容量改成 3，再改回去。这样做居然是能过的。（不知道为什么）

Problem G

Solved by kblack. 00:12 (+)

温暖的皮克定理签到，签这么慢，这锅我背了。

Problem H

Solved by zerol. 04:14 (+5)

题意：树上有松鼠被两只乌鸦追。每回合乌鸦起飞并确定落点，松鼠每回合可以到树上的任意位置只要不经过那个没飞的乌鸦，然后飞起来的乌鸦落地。松鼠被乌鸦踩了或者无路可走就挂了。问乌鸦最少几步逼死松鼠。

题解 1：

四次方的 dp。注意状态的循环依赖问题。（然而没过）

题解 2：

首先发现乌鸦要逼死松鼠，从第二部开始就是交替往松鼠所在的联通块压缩活动区域。步数就是以某只乌鸦为根，松鼠所在的那一支的最大深度。但是乌鸦也可以以一步的代价改变位置，可以枚举前两步或者直接飞到重心（按深度而不是子树大小）。

Problem I

Solved by zerol. 00:23 (+)

简单 dp 签到。

Problem J

Upsolved by ultmaster.

题意：把 $n$ 个单词放进一个 $h \times w$ 的方格纸，求方案。

题解：先把一个单词包含另一个单词的情况吃掉。然后记 $f(state, i)$ 为已经用过 state 的单词，最后一个单词是 $i$，最少需要多少行，以及在行数最少的前提下最后一行又多少列。预处理单词的重叠情况后，暴力转移即可。最后求方案回溯可能略有点麻烦。

Problem K

Solved by kblack. 00:18 (+)

温暖的签到。