AtCoder Grand Contest 014

A - Cookie Exchanges

看到这种题一般能想到直接枚举一定次数,不行就输出无解。

可以证明是 \(\log n\) 次,没想过证明。

B - Unplanned Queries

观察样例容易发现,或者这类题我好像见过类似的,结论就是如果所有端点都被取偶数次,那么就是可行的,反之不行。

考虑把路径的性质反映到点上,如果有一个点被取了奇数次,那么一定不满足要求。

如果所有顶点都被取了偶数次,那么就不存在一个点被取奇数次。(口胡证明)

C - Closed Rooms

显然除了第一次要特殊考虑一下之外,剩下的完全可以走最短的直线,也就是从第二轮开始,一直朝着某一个方向走直线到达边界。

那么第一次我们要求出 \(k\) 步之内,能走到的离四边界最近的点,\(BFS\) 求一下最短路即可。

然后求答案也很好求,具体见代码输出部分。

D - Black and White Tree

首先可以知道的是,如果这棵树存在完美匹配,那么先手必败。

因为如果存在完美匹配,那么每当先手选择一个点,后手就可以直接选择其树上的匹配点,这样最后树一定会被染黑。

接下来考虑不存在完美匹配的情况。

我们发现对于先手来说,如果染一个叶子的父亲结点,那么后手就必须染这个叶子,同时,我们可以把已经染过的这些“匹配点”都删掉(同时删掉染的这黑白两个点,显然对原问题没有影响)。

那么因为原树不存在完美匹配,所以删到最后必然是一条只有三个结点的单链的形式。此时先手选择中间的点,后手无论怎样选择都必败。

求树上完美匹配直接 dp 一下就好了。

E - Blue and Red Tree

首先我们直接模拟这个操作显然看上去就很不太行。

然后可以想到,对于每一条目标树上的边,一定是存在这样一次操作是选择了路径:\((u,v)\) 的,因为只有这样才能让 \((u,v)\) 连上一条红色边。

那么我们可以把这些边全部反映到原树上的路径去,显然,就是要让我们每一条路径去选一条边断开,并且先断开的边不能在后来的路径上面。

接下来又根据这道题的性质,我们可以知道始终存在某一条边,其当前被1个路径覆盖,于是我们把这条路径视为在这条边断开,并对路径区间减1,并寻找新的值为1的边。可以直接树剖维护。

于是这道题就做完了,需要注意的是实现。

同时std是高妙的启发式合并办法,也就是倒过来考虑路径,暂时没看懂。

F - Strange Sorting

还不会证,待补。

上一篇:jQuery实现发送验证码倒计时60秒


下一篇:The 16-th BIT Campus Programming Contest - Online Round--Easy Nim