2017-2018 ACM-ICPC, Central Europe Regional Contest (CERC 17)

From EOJ Wiki
Jump to navigation Jump to search

Problem A

Solved by ultmaster. 02:48 (+)

题意:飞机上选座位的模拟题。

题解:某人情境代入了,搞反了左右。(当然为什么会情境代入呢?主要是因为没读清楚题。)

Problem F

Solved by ultmaster & zerol. 03:20 (+13)

题意:定义一种新阶乘是 1 乘到 $n$,中有一个 $k$ 改成了一个比 $k$ 小的 $v$,求 $n$ 的新阶乘的结果能否模 $p$ 为 $r$,如果能要改哪一个。

题解:前缀后缀扫一下应该可以。不过非常不顺利(被卡常了)。搞了半天最后假算法过了。垃圾题,不想再看到它了。

zerol: 真的是浪费生命。反正标答就是把逆元乘了过去,可以少算一些东西。

Problem G

Solved by kblack. 03:38 (+)

题意:可以主动选择是否丢弃随机的方向的随机游走,问最低代价期望。

题解:定义 $a_i$ 为从位置 $i$ 到 $n$ 的期望代价,$a_i = \frac{\sum_{(i, j) \in E} min(a_j, a_i)}{d_i} +1 $,如果没有这个min,那这题就只能高斯消元解方程组才能得到答案。因为有这个 min,如果从小到大计算 $a_i$,方程就可以简化,步骤类似 Dijkstra 的松弛,从 $n$ 开始,通过方程已经计算的值,假设剩余未计算的都大于 $a_i$ 去估计 $a_i$,最小的一定是真的答案(发现选用大的一定不会让答案变得更小),set 维护即可。注意原图可能并不联通,可能影响迭代边界。

Problem H

Solved by ultmaster. 03:48 (+)

题意:给一系列目录,然后有一些规则,输出一下。

题解:建棵树,然后输出一下,没了。

Problem J

Solved by zerol. 01:30 (+3)

题意:给一棵树,问切成若干个大小相同的联通块共有几种切法。

题解:假算法过的,数据不行。真算法待补。

真算法:$O(\sigma_1(n) + n)$,假算法 $O(\sigma_0(n) n)$。能分解成 n/k 个大小为 k 的块,当且仅当有 n/k 棵子树的大小为 k 的倍数。

Problem K

Unsolved.

Problem L

题意:已知若干正着和斜着覆盖的正方形,求并的面积。

题解:坐标范围不大,不用离散化,直接记录左下角的顶点,然后用扫描线边扫边模拟就可以。注意每个地方都要取 max(见鬼了好久)。