AGC033

agc033 · 浏览次数 : 5

小编点评

## Summary of A, B, C, D, E, and F for AGC033: **A. Darker and Darker BFS:** - Can be used for both first and second player. - Simple and effective, but might not be the most efficient for large problems. **B. LRUD Game:** - Two different approaches, one for first and one for second player. - Second player needs to ensure the range is not extended past its maximum. **C. Removing Coins:** - Focuses on minimizing the diameter of the tree. - Only relevant when there is only one or two nodes. - Can be solved using dynamic programming or memoization. **D. Complexity:** - Can be solved with O(n^4) memory using brute force. - However, the interesting solution focuses on specific cases and uses a more efficient approach. **E. Go around a Circle:** - Uses a generating function approach to solve the problem. - Can be used to solve problems where the state space is limited. **F. Adding Edges:** - A novel approach that uses the concept of chain-of-thought to optimize the solution. - Might be difficult to come up with on the spot.

正文

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相似的内容: