AGC033
听讲着感觉没有做的那套 AGC055 难。主要是套路比较多。
A.Darker and Darker
简单的 BFS 即可。
B.LRUD Game
有两种做法：
-
逆着考虑，还原可赢的初始区间。
-
对于先手，当前如果有一个向上走的，那么纵向上界便会被抬高。其他方向类似。
-
对于后手，与先手相反，会使得范围变小，但是注意一下边界（不可越界）
-
还要考虑一个问题，先手先走，逆着考虑，后手先走！
-
-
模拟博弈的过程：
-
如果先手确定了一个方向，那么一定不会走反方向。所以考虑枚举方向。
-
而在 博弈 过程中，后手需要保证，后面不会被先手顺势向同一个方向移出。也就是博弈时所累计的前缀和不能小于先手的后缀和。
-
C.Removing Coins
题意：
每次选择一个点作为根，删去其叶子结点。
如果只有两个节点，则都删。
我们考虑每一次操作对树造成的影响：影响直径。
如果选择了直径上的点作为根，则会使得直径减2，反之减1。
考虑最终剩余 \(\le2\) 的情况就赢。也就是说，只有直径为 \(1 + 3x\) 的情况，后手才可以胜利。(始终使得为 \(3\) 的倍数)。
D.Complexity
不难有 \(n^4\) 的记忆化搜索（或者DP）。
但是考虑答案的情况，不难得出答案的界为 \(O(\log W + \log H)\) 。
显然与状态不同界。所以考虑枚举答案。（经典套路）
于是可以有状态：\(f_{x, i, j, k}\) 表示答案为 \(x\)，上 \(i\)，下 \(j\)，做 \(k\) 时能达到的最大右界。
初始状态，贪心选。
考虑转移：
\[\begin{aligned} f_{x, i, j, k} &= f_{x - 1, i, j, f_{x - 1, i, j, k}} \\ f_{x, i, j, k} &= \max_{i \le m \le j} \min(f_{x - 1, i, m, k}, f_{x - 1, m + 1, j, k}) \end{aligned} \]考虑优化：
\(m\) 其实可以二分求，或者通过决策单调性：
- \(f_{x, i, j, p}\) 在 \(i, j\) 一定时，随着 \(p\) 单调下降。同理，所以 \(j\) 递增，\(m\) 递增。
E.Go around a circle
利用生成函数的做法可以参考：agc033_e - myee 的博客 - 洛谷博客
构造递推的方法可以参考：题解 [AGC033E] Go around a Circle - 菜鸟驿站 - 洛谷博客
要仔细分析题目性质，通过增加限制减少决策的方式，解决转化后的问题。
或者说利用限制，从充要条件下手。
F.Adding Edges
神仙做法。参考：AT4929 [AGC033F] Adding Edges - - 洛谷博客
本质上也就是通过链的传递进行优化。但这东西真难想的出来。
标签：洛谷,博客,先手,AGC033,考虑,直径 From： https://www.cnblogs.com/jeefy/p/17477606.html