AtCoder Beginner Contest 270

A. 1-2-4 Test

水题。

B. Hammer

分裂讨论。
code

C. Simple path

一遍 dfs 就完了，怎么还有这种搜索题！
code

D. Stones

观察数据范围，\(O(NK)\) 可过。

\(dp_i\) 表示 \(i\) 块石头，第一个玩家最多可以拿走的石头数量。

枚举当前玩家选哪一个数值进行转移即可。 \(dp_i=\max\{dp_i, i-dp_{i-a_i}\}\)。因为下一个操作的人是另一个玩家，每个人都采取最有策略，则第一个玩家最大拿到的就是 \(i-dp_{i-a_i}\)。

code

E. Apple Baskets on Circle

最大关键在于找到拿了多少圈才拿完 \(K\) 个苹果。

考虑二分，转化为判定性问题，拿了 \(x\) 圈拿了多少个苹果？拿 \(x\) 圈等价于每一个果篮都走过 \(x\) 次，但是不一定能拿到 \(x\) 个，因为一个果篮拿空了就不能再拿了。

注意，二分的时候二分出完整的圈数，剩下还有一点点（不到一圈）直接扫一遍计算即可。

code

F. Transportation

如果除开港口和机场只有道路等价于最小生成树问题。

于是可以开一个虚拟源点，所有港口和虚拟源点连一条边，连完之后可以保证所有港口相连。机场也类似。

但是，有一个坑点，可以不开任何港口或任何机场，所以不一定所有的边都需要连，可以讨论 \(4\) 次，具体看代码。

code