AGC033 题解

· · 个人记录

AtCoder Grand Contest 033

A - Darker and Darker

跑个多源最短路就好了。由于边权都为 1 所以直接 bfs。

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

code

B - LRUD Game

容易发现，4 个方向是独立开来的。

举个例子，如果第一个人最终想让棋子从上边出去，那么他肯定会一直 U，然后第二个人会一直 D。

四个方向都判一遍就好了。

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

code

C - Removing Coins

先转化一下题意：每个人可以选择一个点然后删掉以这个点为根的叶子节点。

换句话说，每个人可以选择无根树的一个叶子节点（或者都不选）不被删掉，然后把剩余的叶子节点都删掉。

先考虑一条链的情况：

设链的长度为 L。由于每个人每次操作可以选择 L 减去 1 或者 2（链的长度为 \leq 2 的情况除外），所以容易发现，当 L\equiv 2\pmod{3} 的时候后手必胜，否则先手必胜。

对于一般情况，发现每次操作可以选择把直径长度减 1 或者 2，这样就化成了链的情况。那么找到树的直径的长度就好了。

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

code

D - Complexity

显然有种很朴素的时间和空间都会炸掉的 \mathcal{O}(n^5) 的做法。

容易发现答案的上界只有 \log H+\log W，考虑枚举答案的过程中 dp。

不妨设枚举的答案为 ans。

设 f_{i,j,k} 表示左上角为 (i,j)，右上角为 (i,k) 的矩形最多能覆盖多少行。（满足这个矩形的复杂度 \leq ans）

每当 ans\leftarrow ans+1 的时候，显然有 2 种转移：

横着切：这种比较 easy，直接转移即可：

f_{i,j,k}\leftarrow f_{i,j,k}+f_{i+f_{i,j,k},j,k}

竖着切：首先有一种朴 \mathcal{O}(\log n) 的转移方法就是二分出竖着切的位置（它显然是凸的）。

不过有种 \mathcal{O}(1) 的转移就是在设一个 g_{i,j,k} 表示左上角为 (j,i) 左下角为 (k,i) 的矩形最多能覆盖多少列。（同样需要满足这个矩形的复杂度 \leq ans）

这样 f 和 g 其实就能交错更新了。

当 f_{1,1,m}=n 的时候停止答案自增就行了。

时间复杂度：\mathcal{O}((H+W)^3\log HW)。

code

E - Go around a Circle

不失一般性，假设 S 的第一个字母为 R，那么显然不可能出现连续两个弧上都是 B。

考虑把 B 看成分割符后把整个圆分段，然后寻找其它限制。

如果 S 全是 R，那么就没别的限制了，直接 dp 就行了（dp出来其实就是个斐波那契数列）。（可以参考代码）

否则，S 显然是一段 R，一段 B，一段 R，一段 B……

考虑如果一种染色方案存在一段弧上有偶数个 R，那么这种方案一定不合法，因为容易发现这段弧上相邻两点到弧的两端最短距离的奇偶性不同。

然后考虑棋子的运动过程：首先有一段 R，显然这段 R 结束的时候棋子需要在一个红色弧和蓝色弧的交界处，这会对圆上每段 R 的长度产生限制。然后是一段 B，容易发现棋子只要在那条 B 的弧上来回走就行。接着是又一段 R，如果这一段长度为偶数，那么还是来回在一条 R 的弧上来回走就好了；如果长度为奇数，那么就需要到现在所在的 R 段的另一端，显然这段弧的长度不能超过 S 的这段 R 的长度，否则就走不过去了，这又会对圆上每段 R 的长度产生限制。后面的情况类似。

注意如果 S 的最后一段是 R，那么最后的那段 R 就无需考虑了。

知道了圆上每段 R 最长是多少后，就可以 dp 了。令 dp_i 表示强制第 i 段弧的颜色为 B 时，前 i 段弧的染色方案数。用前缀和优化转移即可。

注意由于圆就算旋转后相同也算不同方案数，所以还需要根据最后一段 R 的长度来决定起点所在位置的方案数。（细节见代码）

code

F - Adding Edges

如果是强制必须按 a,b,c 的顺序的话就很好做了，就可以根据下面这个显然的结论以每个点为起点搜一下就好了：（具体 dfs 的方法在最后）（设最开始的图为 G_0，最终得到的图为 G。）

如果一条边 (u,v) 满足 (u,v)\in G 但 (u,v)\notin G_0，那么一定存在 k 个点 t_1,\cdots,t_k，满足 u=t_1,v=t_k 且 \forall 1\leq i<n，(t_i,t_{i+1})\in G_0。

为了化成这种情况，考虑如果某条链上的三个点 a,b,c 如果满足 (a,b)\in G_0 且 (a,c)\in G_0 ，不妨把 (a,c) 删掉然后把 (b,c) 加入到 G_0。不妨把种操作称为缩短。容易知道这种操作不会影响最终结果。

考虑分别维护以第 i 个点为根的树 T_i。

设 note(a,b) 表示 T_a 上离 b 最近的且由目前 G_0 产生的图 G 中与 a 相邻的祖先。（如果不存在则为 0）。

假设现在要把一条边 (a,b) 加到 G 中，该如何处理。

首先要把 (a,b) 这条边缩短，也就是说 a\neq b 且 note(a,b) 不为 0，那么就让 a\leftarrow note(a,b) 。（对于 b 同理进行操作）

然后尝试更新 note。考虑 T_a 中以 b 为根的子树。从 b 往下 dfs，如果遇到一个点 c 满足 note(a,c)=0，那么就让 note(a,c) 赋为 b；否则，那么说明此时 a,b,c 顺次在一条链上且 (a,b)\in G，(a,c)\in G，需要把产生的新边 (b,c) 拉出来进行如上所说的处理。

最终枚举以每个点为边的一个端点的边的数量即可。

具体方法就是在 T_u 中 dfs，刚开始去边的端点 b=u，当遇见一个点 v 满足 note(b,v)=v 的时候就说明 (u,v)\in G，然后再令 b=v 然后继续 dfs 找边即可。

最终别忘了把答案除以 2。

标记的总点数最多只有 n^2 个，并且 m 条边每条边只会被缩 \mathcal{O}(n) 次，所以总时间复杂度是 \mathcal{O}(n^2+nm)。

code