AGC029 题解

· · 个人记录

AtCoder Grand Contest 029

A - Irreversible operation

统计每个 W 之前有多少个 B 。\mathcal{O}(n) 扫一遍即可。

code

B - Powers of two

对于每个 a_i，先找到一个正整数 k 满足 2^{k-1}\leq a_i<2^k。

不妨先考虑 a_i 都不同的情况。

如果 2^k-a_i 在序列中存在，那么就将 a_{i} 与 2^k-a_{i} 连一条边。由于 2^k-a_i\leq a_i ，所以最后连出来的一定是个森林。

求森林的最大匹配就直接从叶子节点往上贪心匹配就行。

如果 a_i 有重复的，仍然可以想上面所说的贪心匹配（相当于一个节点可能可以匹配多次），不过需要特判一下 a_i=2^{k-1} 的情况。

code

C - Lexicographic constraints

先二分一波答案，然后通过贪心来判断是否可行。

显然第一个数每一位都是 0，然后考虑后面的数：

如果 a_i>a_{i-1}，那么第 i 个数只需要在第 i-1 个数后面补 a_i-a_{i-1} 个 0 即可。

如果 a_i\leq a_{i-1}，那么第 i 个数需要在第 i-1 个数的基础上删掉末尾的 a_{i-1}-a_i 个数，然后再整体 +1（注意可能会进位多次）。如果最前面的一位还需要进位，那就不合法了。

可以用栈轻松维护。

还需要特判一下答案为 1 的情况。

时间复杂度：\mathcal{O}(n\log n)。

code

D - Grid game

憨憨题。

每一列开个 vector 记录哪些位置有障碍，然后枚举最后停在第几列，在 vector 中二分出最后停的位置（第几行）即可。

code

E - Wandering TKHS

求出了每个节点 u 到根（1 号节点）这条路径中（包括 u）节点编号最大值，设为 top_u。

对于所有满足 top_u=u 的节点，显然除了 u 子树以外的节点都不可能拓展到 u。

再仔细观察会发现，对于一个点 u，如果 top_u\neq u，设 b_u 为 top_u 的儿子中里 u 最近的那个儿子，显然 u 可以拓展到 b_u 子树内所有满足 top_x=top_u 的节点 x，设为 siz_{b_u}。

然后再考虑从 u 爬到 fa_{top_u} 之后的情况。显然会被 top_{fa_{top_u}} 挡住，然后在回到 top_u 的除 b_u 以外的其它子树中进行拓展。这个可以直接在 top_u 中搜索，也就是对所有满足 top_x=u 每个节点 x 设一个 t_x 表示如果从 top_u 往上爬，被 top_{fa_{top_u}} 挡住后能往 x 子树中拓展多少个节点。

最后 dfs 统计一遍，dfs 的过程中进行累计答案。

具体就是，假设当前 dfs 到了节点 u，设 u 以上 u 能拓展到 now 个节点。如果 top_u=u，那么 now\leftarrow t_u；如果 u=b_u，那么 now\leftarrow siz_u-t_{u}（因为在 top_u 的时候加上的 t_{top_u} 到 b_u 的时候需要容斥掉）。u 节点的答案就是目前的 now。

时间复杂度：\mathcal{O}(n)。

code

F - Construction of a tree

先建一个二分图。左部 n 个点表示原图的点，右部 n-1 个点表示原图 n-1 条边。

如果第 i 个集合里有点 j，那就 j 向 i 连一条边。

考虑一棵树删去任意一个节点，剩下的每个节点唯一与一条边匹配。

也就是说，在这张二分图上，删掉左部的任意一个点后都存在二分图完美匹配。设右部第 i 个点匹配左部第 match_i 个点。显然 match_i 就是原图该边的一个端点了。

换句话说，类似于 Hall 定理，对于左部的任意一个点集 S，设与它们至少有一条边相连的右部的点的集合为 f(S)，必须满足 |f(S)|>|S|（否则一定存在环了）。

随便一个点当作根，然后求出任意一个完美匹配。然后从这个点开始 bfs。具体做法：维护一个队列，每次取队首然后 u 遍历和它相连的右部点（原图的边），对于之前没有被遍历到右部点 v，把这条边的另一个端点设成 u，然后把 match_v 塞到队列里。

如果某一时刻还没有遍历完所有点但是队列空了，那说明无解了，因为剩下的图满足了 |f(S)|\leq |S|。

KM 艹过去了？是我没能想到的。

其实应该用 Dinic 复杂度才是对的。

时间复杂度：\mathcal{O}(m\sqrt{n})。（用 Dinic。）（m=\sum|E_i|）

code