ACM-ICPC 2018 Beijing Online Contest

From EOJ Wiki
Jump to navigation Jump to search

ECNU Foreigners

ultmaster: 感觉去年现场赛,也是这个风格吧。。。所以今年,不去北大了啊。。。

zerol: 还好抢了个签到,不然零贡献了。

Problem A

Solved by ultmaster. 01:25 (+)

题意:复杂得一批。

题解:最多只能携带五个氧气瓶可以把氧气瓶个数记在状态里。加速药丸必须要在出这个格子的时候用掉(反正早用晚用都一样)。然后会产生不同权的边,所以要使用 Dijkstra 而不是 BFS。

Problem B

Solved by zerol. 00:45 (+)

题意:求若干个很短的字符串的循环最长子序列(可不连续),长度一样则要求字典序最小。

题解:枚举第一个串的所有子序列,判断可行性,最后把可行的子序列的所有旋转和答案比较。

Problem C

Upsolved by ultmaster. (-3)

ultmaster: 这题目出得真好!给验题人点赞!

做这个题不但不会给我带来任何好处,而且会增大我的工作量呢。。。所以我为什么要做这个题呢?

更新:踏破铁鞋无觅处,得来全不费工夫。

Problem D

Solved by kblack. 00:23 (+)

温暖的签到

Problem H

Solved by kblack. 02:37 (+2)

题意:k 维空间,求点到曼哈顿距离球的最短欧几里得距离。

题解:先纠正到原点,广义的第一象限,然后垂直下去(所有维同时减),有减成负的就不要了(当0),减到超平面上,就好了。

One,Two,Three,AK

Xiejiadong:久违的自闭场。

Problem A

Solved by Xiejiadong. 1:32:22 (+)

Problem B

Solved by Xiejiadong. 1:02:57 (+)

Problem C

Upsolved by Xiejiadong. (-8)

Problem D

Solved by dreamcloud. 1:04:45 (+)

Problem G

Unsolved. (-23)

Problem H

Solved by oxx1108. 3:20:27 (+2)

题意:k 维空间,求点到曼哈顿距离球的最短欧几里得距离。

题解:可以换元之后发现是个类似均值不等式的东西(或者说方差最小?),然后对于每一维都是独立的,那就sort一下,然后使得最大的尽可能小,如果全部变成0了,那就剩下多余的等分。类似于去年蓝桥杯初赛最后一题。