2014-2015 Northwestern European Regional Contest (NWERC 2014)

From EOJ Wiki
Revision as of 00:55, 19 June 2018 by Ultmaster (talk | contribs)
Jump to navigation Jump to search

特别简单、特别适合双开的场。

Problem C

Solved by ultmaster. 00:38 (+1)

题意:超市买东西价格四舍五入,要求在物品之间插隔板尽可能逃钱。

题解:某人没有注意到是已经排好序的,想了半天贪心。然后,就没什么好说的了。

Problem D

Solved by kblack. 01:13 (+3)

Problem E

Solved by kblack. 01:28 (+)

Problem F

Solved by kblack. 02:09 (+4)

Problem G

Solved by kblack. 04:56 (+6)

Problem H

Solved by ultmaster. 01:56 (+1)

题意:对一棵树的边染色,使得每一点相邻的边的颜色数量不超过两种。求最多可以用多少种颜色。

题解:就是我最不会的那种贪心。想烦了,写了好久。后来想想其实就是尽量染新的就好了啊?跟起始位置没啥关系。

Problem I

Solved by ultmaster. 04:19 (+)

题意:找一个 14 个点欧拉回路,使得边权和恰好为 $L$。

题解:很自然的想法是状压 DP,但没法记录可以到达的长度。$L$ 大得很,似乎也不可以利用。给的图还满足 $d_{ij} \le d_{ik} + d_{kj}$,一直在想这个东西怎么用。

我们先固定两个点 (13),然后把路径劈成两半 ($\binom{12}{6}$),然后枚举一边的排列 $6! \times 6$,在另一边所有的排列可能导致的和中搜索 ($\log 6!$)(对,就是那种套路)。总复杂度是 $13 \times \binom{12}{6} \times 6! \times (6 + \log 6!) \approx 8 \times 10^7$。时限大得很,随意冲。

Problem J

Solved by kblack. 00:09 (+1)

Problem K

Solved by ultmaster. 02:55 (+)

题意:要给传送带搬东西,然后选起始位置什么的,复杂得很,不想写了。

题解:暴力模拟,实现难度稍微有一点。