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)

题意：给 $n$ 个点，问是否有至少 $P%$ 个点在同一直线上。

题解：哈尔滨一半在圆上的出处，随机取两点验证即可，期望 $({\frac{100}{P}}^2$ 次，根据 $n$ 的大小选尝试次数即可。注意 CF 的随机范围是 short，要拼接，否则会导致后面的无法随机到。

Problem G

Solved by kblack. 04:56 (+6)

题意：网格图上到所有点的曼哈顿距离和的最小值，要求最大距离不大于 $d$。

题解：曼哈顿距离和最小有经典结论，最大距离限制可以得到一个斜着的矩形区域，如果矩形区域与最小值的矩形区域（或点）有公共格点，那么就是最终答案，否则最小值一定出现在边界上，边界上扫描一下就好了。由于限制矩形的顶点可能不是格点，处理起来就很麻烦，公共区域又变成了计算几何，写起来十分刺激。

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 (+)

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

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