AGC055
第一次打AGC，好难受。
T1 看了一眼题解，没看懂……但是还是做出来了。
T2 感觉比 T1 简单，构造很好猜。
其他的没时间思考，T1 花了我 2h30min，难受。
A.ABC Identity
翻译：
给定长度为 $3n$ 的序列，其中字母 ABC 各有 $n$ 个。
一个合法序列 $T$ 满足以下条件：
其长度为 $3k (1 \le k \le n)$。
$T_1 = T_2 = ... = T_k$
$T_{k + 1} = T_{k + 2} = ... = T_{2k}$
$T_{2k + 1} = T_{2k + 2} = ... = T_{3k}$
$T_1, T_{k + 1}, T_{2k + 1}$ 互不相同。
求一个把这个序列分成不多于 $6$ 个合法的序列的方案。
可以证明，一定存在一种合法的划分。
分三段考虑。
std 做法是关于 ABC 的 6 种排列，依次枚举，贪心选择。
我在考场上是：先考虑前两半，相异配对，网络流解决。
不会产生相同配对的正确性？由于是相异配对，如果产生相同配对，则某一个一定超过了 $n$ 个，不符合题意。所以网络流可以解决，贪心选择没问题。
网络流只有 $6 + 2$ 个点，所以可以看作常数，复杂度 + O(1)
所以整体复杂度 $O(n)$
妈的，傻逼网络流，真的服……
B.ABC Supremacy
考虑如下转化：
$$A \overline{ABC} \to \overline{ABC} A \\ B \overline{ABC} \to \overline{ABC} B \\ C \overline{ABC} \to \overline{ABC} C $$
也就是我们贪心把所有的 $\overline{ABC}$ 放在最前面即可。（相当于删除）
由于拼接后也可能存在 $\overline{ABC}$，所以利用栈的思想处理。
复杂度 $O(n)$。
C.Weird LIS
方法1：组合
参考 AGC055C - Legitimity 的博客 - 洛谷博客 和补充 题解：AGC55C Weird LIS - Edward1002001 的博客 - 洛谷博客
这里再做一点说明。
无用点为什么不可连续？考虑
4 3 5 2 1 7 6，也就是非 非 必 无 无 非 非。这个排列和2 1 3 7 6 5 4，也就是非 非 必 非 非 非 非是等价的。也就是说，连续的非会使得我们重复计数。所以不可以连续。ans初始设置？其实枚举的是没有必经点的情况（全是非必经点），需要满足：$k \le \lfloor \frac n2 \rfloor$
$k \le m$
$k \ge 2$
所以才有 $\min(m, \lfloor \frac n2 \rfloor) - 1$。但是我们还需要考虑当 $m = n - 1$ 时，可以存在全是必经点的情况，也就是
1 2 3 ... n的情况。为什么 $\min(m, x + y) - \max(x, 3) + 1$？这里枚举的是 $k$，$k$ 的下界确定了，因为存在 $k - 1$，所以 $k - 1 \ge 2 \iff k \ge 3$。
其他部分最终式子为：
$$\sum_{x = 1}^{\min(m, n - 1)} \sum_{y = 0}^{\lfloor \frac {n - x}2 \rfloor} {x + y \choose x} {x + 1 \choose n - x - 2y} (\min(m, x + y) - \max(x, 3) + 1) $$
方法2：自动机
参考 at_agc055_c Weird LIS 题解 - juruo - 洛谷博客
这里做一点解释：
状态机的设定，4种状态：
除了
CAN，都能放只能放
CAN可以放
MUST或者USELESS，之后MUST还可以跟MAY可以放
MUST或者USELESS，之后MUST不可以跟MAY
为什么有状态4？因为
k确定了红黑对的数量，而我们是贪心的把所有红黑对尽可能放在前面。而可能存在只有非 非 无 必的情况，所以有状态 3，通过MUST转移到 1，通过USELESS转移到 4，但是不能再来一个MAY！
D.ABC Ultimatum
一道猜结论的题。
观察三个串，有 ABC，BCA，CAB，我们考察能划分成这三种串的串的性质。
考虑每一个字母出现的次数：由于 B 只在 BCA 中在 A 前面，其他的类似。我们考虑定义 $M_B = \max S_B - S_A$，其他的类似。
可以发现，$M_B \le C_{BCA}$，同理，得到 $M_A + M_B + M_C \le C_{ABC} + C_{BCA} + C_{CAB} = N$。
这是必要条件，所以考虑证明充分性（不会。
所以我们可以设出一个 $O(n^7)$ 的 DP，令 $f_{a, b, c, x, y, z}$ 表示 ABC 的数量以及 $M_A, M_B, M_C$。
不过考虑 $a + b + c = i$ 的时候才有贡献，所以可以省一维，变为 $O(n^6)$。
E.Set Merging
神仙思路题。
我们把整个序列看作一个排列，每一次的合并相当于交换排列中的两个位置。
而最终 $S_i \to [ \min_{j = i}^n P_j, \max_{j = 1}^i P_j]$，一个后缀 $\min$ 和一个前缀 $\max$。
考虑归纳法，分 $P_i > P_{i + 1}$ 或者 $P_i < P_{i + 1}$ 讨论。
最终就是求合法序列的最小逆序对数。考虑贪心放置，用数状数组求。
总复杂度 $O(n + n \log n)$，可以通过6指针的方法优化到 $O(n + n)$。