ACM-ICPC 2018 Beijing Online Contest

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 E

Upsolved by OEIS.

题意：$n$ 节点有标号 2-regular 有向图计数 * n!。

题解：A007107 * n!

Problem H

Solved by kblack. 02:37 (+2)

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

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

One,Two,Three,AK

Xiejiadong：久违的自闭场。

Problem A

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

题意：求最少的花费，从$S$到$T$。

题解：显然$P$是没有作用的，唯一的作用就是经过$P$不需要花费。

对于每一个位置拆成*氧气瓶数量个点，直接跑SPFA即可。

Problem B

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

题意：求多个循环串的最长公共子序列。

题解：感觉好神啊。怎么做多串的最长公共子序列啊...然后发现数据规模小的温暖。

不怎么温暖的签到题，巨难写。

暴力枚举第一个串的子序列，判断在下面的串里面能不能作为子序列。

循环串的处理方式是，暴力旋转。

Problem C

Upsolved by Xiejiadong. (-8)

题意：四个智商不同的人玩一个游戏，判断结局。

题解：巨恶心的模拟题。一道自闭两个多小时的模拟题。注意order和rank的区别，注意rank和我们认知之中大不相同。然后就是码。码了250+行。

Problem D

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

题意；给你一个圈，圈上有n个点，每个点有个权值，问你从哪个点开始，满足前缀和始终大于某个值。

题解：枚举每个点，求出最小值。

Problem G

Unsolved. (-23)

Problem H

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

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

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