2014-2015 Northwestern European Regional Contest (NWERC 2014)

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

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)

不看题上签到，是肯定会 WA 的。

Problem K

Solved by ultmaster. 02:55 (+)

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

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