Difference between revisions of "2017-2018 ACM-ICPC German Collegiate Programming Contest"
(3 intermediate revisions by 2 users not shown) | |||
Line 32: | Line 32: | ||
Solved by zerol. 01:47 (+6) | Solved by zerol. 01:47 (+6) | ||
+ | |||
+ | 题意:有向图判负环。 | ||
+ | |||
+ | 题解:用 spfa 判负环。注意对于每个点都必须访问过,即使在一个联通快里。 | ||
+ | |||
+ | zerol: 我有向图建成无向图了,spfa 还写错,罚钱。 | ||
== Problem F == | == Problem F == | ||
Line 50: | Line 56: | ||
Solved by zerol. 04:14 (+5) | Solved by zerol. 04:14 (+5) | ||
+ | |||
+ | 题意:树上有松鼠被两只乌鸦追。每回合乌鸦起飞并确定落点,松鼠每回合可以到树上的任意位置只要不经过那个没飞的乌鸦,然后飞起来的乌鸦落地。松鼠被乌鸦踩了或者无路可走就挂了。问乌鸦最少几步逼死松鼠。 | ||
+ | |||
+ | 题解 1: | ||
+ | |||
+ | 四次方的 dp。注意状态的循环依赖问题。(然而没过) | ||
+ | |||
+ | 题解 2: | ||
+ | |||
+ | 首先发现乌鸦要逼死松鼠,从第二部开始就是交替往松鼠所在的联通块压缩活动区域。步数就是以某只乌鸦为根,松鼠所在的那一支的最大深度。但是乌鸦也可以以一步的代价改变位置,可以枚举前两步或者直接飞到重心(按深度而不是子树大小)。 | ||
== Problem I == | == Problem I == | ||
Solved by zerol. 00:23 (+) | Solved by zerol. 00:23 (+) | ||
+ | |||
+ | 简单 dp 签到。 | ||
== Problem J == | == Problem J == | ||
+ | |||
+ | Upsolved by ultmaster. | ||
+ | |||
+ | 题意:把 $n$ 个单词放进一个 $h \times w$ 的方格纸,求方案。 | ||
+ | |||
+ | 题解:先把一个单词包含另一个单词的情况吃掉。然后记 $f(state, i)$ 为已经用过 state 的单词,最后一个单词是 $i$,最少需要多少行,以及在行数最少的前提下最后一行又多少列。预处理单词的重叠情况后,暴力转移即可。最后求方案回溯可能略有点麻烦。 | ||
== Problem K == | == Problem K == |
Latest revision as of 11:38, 28 September 2018
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 (+)
温暖的签到。