A
若存在答案则答案是 \(\mathcal{O}(\log a)\) 的，直接模拟即可。
B
可以发现有解当且仅当给出的 \(m\) 条边存在欧拉回路。
C \((\texttt{Easy} \ 1 / 0)\)
删掉的障碍是随意选的，所以等价于求出前 \(k\) 步能走到的离边界最近的距离。
D \((\texttt{Easy} \ 3 / 0)\)
考虑一个儿子全部为叶子的非叶结点。如果其有 \(> 1\) 个儿子，那答案就肯定是 First；否则可以把这个点和它的唯一的儿子去掉，答案是一样的。于是一直删点并判断，最后根节点特判一下即可。
事实上这个过程和求树的匹配很像。可以证明答案为 Second 等价于树存在完美匹配。
时间复杂度 \(\mathcal{O}(n)\)。
E \((\texttt{Easy} \ 3 / 1)\)
去掉一条蓝边意味着分裂了一个蓝树的连通块，而分裂之后的两个连通块在红树中必须要是连通块。
把这个过程倒过来，使用启发式合并维护即可。
F \((\texttt{Hard} \ 7 / 0)\)
这种题是怎么想到的啊！！！
基本上就是复读粉兔的题解
注意到 \(1\) 并不会影响其他元素是 high 或 low，我们不妨考虑去掉 \(1\) 以后的序列进行的操作。
假设 \(2 \sim n\) 用了 \(t\) 次排好序了，那么 \(1 \sim n\) 的答案就是 \(t\) 或 \(t + 1\)。怎么判断呢？若 \(t = 0\) 的话就看 \(1\) 是不是在序列的最前面；否则我们设 \(t - 1\) 次操作以后序列最前面的值为 \(v\)，不难发现 \(v > 2\)，所以 \(v\) 是 high 的而 \(1\) 和 \(2\) 是 low 的，那么答案为 \(t\) 等价于 \(1\) 在 \(t - 1\) 次操作之后位于 \(v\) 和 \(2\) 之间。
这个看起来变得更难判断了。但是我们给出如下结论：
- 在操作的过程中，\(1, 2, v\) 的循环顺序不改变。
证明的话，首先证明 \(v\) 作为 high 元素当且仅当它的位置在最前面，然后分类讨论即可证明。
发现对于 \(\forall i\)，考虑 \(i\) 和 \((i, n]\) 的序列，上面的结论都是成立的。这样我们就可以从 \(n\) 到 \(1\) 递推 \(t\) 和 \(v\) 了。具体地：
- 若 \(t_{i + 1} = 0\)：
- 若 \(i\) 在 \(i + 1\) 前面，则 \(t_i = 0\)，\(v_i\) 未定义。
- 否则，\(t_i = 1, v_i = i + 1\)。
- 否则：
- 若 \(i, i + 1, v_{i + 1}\) 的循环顺序是 \(1, 2, v_{i + 1}\)，则 \(t_i = t_{i + 1}, v_i = v_{i + 1}\)。
- 否则，\(t_i = t_{i + 1} + 1, v_i = i + 1\)。
最后的答案就是 \(t_1\)。时间复杂度 \(\mathcal{O}(n)\)。
标签：AGC014,答案,texttt,high,Easy,序列,mathcal From： https://www.cnblogs.com/Scintilla/p/16753325.html