AtCoder Grand Contest 033 题解
A - Darker and Darker
题意
有一个 \(H\times W\) 的网格，每个格子有黑白两种颜色。初始颜色是给定的。
你需要不断执行以下操作，直到所有格子全黑（保证一开始有黑色格子）：
- 对于每个和黑色格子有公共边的白色格子，变成黑色。
求操作次数。
\(H,W\le 1000\)
题解
直接将所有黑色格子作为起点进行 BFS 即可。
时间复杂度 \(O(NM)\)。
B - LRUD Game
题意
有一个 \(H\times W\) 的网格，有一个棋子，一开始在 \((s_r,s_c)\)。
A 和 B 玩游戏，执行 \(N\) 次操作。A 和 B 每人有一个长度为 \(N\) 的字符串，分别为 \(S,T\)。第 \(i\) 次操作如下：
- 首先，A 进行游戏。A 可以选择将棋子按 \(S_i\) 的方向移动一格，或不移动；
- 然后，B 进行游戏。B 可以选择将棋子按 \(T_i\) 的方向移动一格，或不移动。
A 的目标是在某一次操作将棋子走出棋盘，B 的目标则相反。
判断两个人采取最优策略时棋子是否会在某一次操作走出棋盘。
\(H,W,N\le 2\times 10^5\)
题解
倒着考虑，维护不能走出棋盘的所有起点，可以发现这些起点一定是棋盘的一个子矩形。
倒着考虑时，每次 B 进行游戏会使该矩形的某一边界向外移动，而 A 进行游戏会使该矩形的某一边界向内移动。
注意矩形边界不能移出棋盘，并且若中途矩形变空，那么就再也不能向外移动了。
时间复杂度 \(O(N)\)。
C - Removing Coins
题意
给定一个 \(N\) 个点的树，每个点上有一个棋子。
A 和 B 轮流进行以下操作，A 先手：
- 选定一个有棋子的节点 \(v\)，取走 \(v\) 上的所有棋子；
- 将剩余的所有棋子向靠近 \(v\) 的方向移动一条边。
不能操作的人输。
求两人采取最优策略时的胜者。
\(N\le 2\times 10^5\)
题解
注意到操作相当于选择一个节点作为根，然后将叶子结点删去。
考虑对于一次操作，若选择的不是度为 \(1\) 的点，那么直径会减小 \(2\)；否则直径要么减 \(1\)，要么减 \(2\)。
于是我们只要在状态里记录直径上的点数即可。
时间复杂度 \(O(N)\)。
D - Complexity
题意
定义一个黑白网格的 complexity 为：
- 若网格全黑或全白，则为 \(0\)。
- 否则，我们用一条水平的直线或竖直的直线将网格分成两个子网格，令两个子网格的 complexity 分别为 \(c_1,c_2\)，则原网格的 complexity 为 \(\max(c_1,c_2)+1\) 的最小值。
给定一个 \(H\times W\) 的网格，求该网格的 complexity。
\(H,W\le 185\)
题解
考虑有两个简单的性质：
- 一个 \(H\times W\) 的网格的 complexity 不超过 \(\lceil\log_2 H\rceil+\lceil\log_2 W\rceil\)。
- 一个网格在最后加入一行或最右边加入一列，complexity 不小于原网格的 complexity.
于是我们设计状态 \(f_{c,i,j,k}\) 表示操作次数为 \(c\)，左上角为 \((i,j)\)，下边界为 \(k\) 时，右边界的最大值。\(g_{c,i,j,k}\) 同理表示操作次数为 \(c\)，左上角为 \((i,j)\)，右边界为 \(k\) 时，下边界的最大值。
根据第二个性质，我们可以直接用双指针优化转移。
时间复杂度 \(O(HW(H+W)\log HW)\)。
E - Go around a Circle
题意
有一个 \(N\) 个点的环，点编号 \(1\) 到 \(N\)。给定一个长度为 \(M\) 的只包含 R 和 B 的字符串 \(S\)，你需要给环上每条边填上 R 或 B，使得对于任意 \(1\le i\le N\)：
- 假设初始有一个棋子在第 \(i\) 个点。你可以执行 \(M\) 次操作，每次沿一条边将棋子走到一个相邻的点。你需要满足存在一种操作方案使得第 \(j\) 条经过的边上的字符等于 \(S_j\)。
求方案数。对 \(10^9+7\) 取模。
\(N\le 2\times 10^5\)
题解
不妨假设 \(S\) 的第一个字符为 R。显然环上不能有连续两个 B 出现。
那么我们考虑根据 B 将环分成若干个 R 的连续段。若 \(S\) 中的字符不全是 R，那么一定有每个 R 的极长连续段长度一定是奇数。这个可以用反证法证明。
另外，显然每段连续段还会有一个长度的限制。
这样我们就可以每次去掉开头的一段 RR..RRBB..BB，转化成一个类似的子问题。
注意「类似」是因为这个子问题的起点一定是每段 R 的两个端点，所以若该子问题开头的 R 的长度是偶数，该段 R 的长度并不会对环上每段 R 连续段的长度产生限制。
可以发现环上 R 的连续段只需要满足奇数和每个子问题产生的长度限制，就一定满足原问题中的限制。
于是直接 DP 即可。注意由于是环，可以把分界点取在最后一段的任意位置，所以最后统计答案时需要乘上最后一段的长度。显然这样做不会算重。
F - Adding Edges
题意
给定一个 \(N\) 个点的树 \(T\) 和 \(N\) 个点 \(M\) 条边的图 \(G\)，你需要不断执行以下操作：
- 选择三个点 \(a,b,c\) 满足 \(G\) 中存在边 \((a,b),(b,c)\) 但不存在边 \((a,c)\)，若 \(T\) 中存在一条同时包含 \(a,b,c\)（任意顺序）的简单路径，则在 \(G\) 中加入边 \((a,c)\)。
求最终 \(G\) 的边数。可以证明最终的 \(G\) 唯一。
\(N,M\le 2000\)
题解
若题目中的条件为 \(a,b,c\) 必须按该顺序排列，设原图为 \(G_0\)，那么 \((x,y)\in G\) 当且仅当存在序列 \(x=v_1,v_2,v_3,\ldots,v_k=y\)，满足 \((v_i,v_{i+1})\in G_0\) 且 \(v_1,v_2,\ldots,v_k\) 按顺序被包含在树上的某条简单路径上。证明较为简单，不再展开。
现在的问题是原题目中 \(a,b,c\) 可以按任意顺序排列。考虑对于三个点 \(a,b,c\)，若这三个点在树上按该顺序被包含在同一条简单路径上，且 \((a,b),(a,c)\in G_0\)，那么我们可以把 \((a,c)\) 删去，加入 \((b,c)\) 而不影响答案。我们把这样的操作称为压缩。
若我们不断对原图进行压缩，直到不能被压缩，那么可以证明最终的图一定满足以上 \(a,b,c\) 必须按顺序排列时的性质。
那么问题是如何压缩。考虑依次加入边，我们记录 \(top(a,b)\) 表示 \(T\) 以 \(a\) 为根时，\(b\) 的祖先中离 \(b\) 最近且在由当前 \(G_0\) 生成的最终的 \(G\) 中与 \(a\) 有边的点。
假设当前加入边 \((a,b)\)，若有 \(top(a,b)=b\)，那么无需再加入。若 \(top(a,b)\) 存在，则我们可以转化成加入边 \((top(a,b),b)\)。
否则，我们加入边 \((a,b)\)，更新 \(top(a,b)\)。然后我们需要 DFS 更新以 \(a\) 为根时 \(b\) 子树内点 \(v\) 的 \(top(a,v)\) 值。
假设当前更新到了点 \(v\)，若 \(top(a,v)\) 存在，由于是从上往下更新的，一定有 \(top(a,v)=v\)。此时我们需要将 \((a,v)\) 压缩，即我们需要再更新完后递归调用加边操作加入边 \((b,v)\)。这种情况下我们不需要再更新子树的 \(top\) 值，可以直接退出。
否则，我们将 \(top(a,v)\) 更新为 \(b\)，继续更新子树。
压缩完后，我们只要从每个点开始 DFS 统计以这个点为边的一个端点的边的数量即可。
我们每次更新时，若 \(top\) 值不存在，我们会更新并继续递归；若存在则会压缩边。\(top\) 值一共只有 \(N^2\) 条，而边一共只有 \(M\) 条，每条最多被缩 \(N\) 次，所以时间复杂度为 \(O(N^2+NM)\)。
