ATC 颓废记录

当 hzr 与 zyf 两个工业大国进行 AGC 军备竞赛时，咱这个农业小国只会做 ABC 的签到题。

我草，鸽了。

AGC001~AGC010

AGC013C：

根据经典题独木桥的套路，将相遇看作交换编号并不改变方向，那么我们就是要求每个蚂蚁最后的编号。

蚂蚁的编号对应的位置顺序也是固定的，我们只需要将顺序进行循环移位即可，循环移位次数就是正方向越过 \(1\) 次数减去反方向越过 \(1\) 次数。

AC

AGC011~AGC020

AGC021~AGC030

AGC026E：

将序列划分成许多极短的，ab 数量相等的段，可以发现每一段之间独立，我们得到每一段的答案之后单调栈合并这些串即可。

考虑一段怎么求答案，我们可以将段分成两类：

• 所有 a 都在匹配的 b 前面的段：可以发现只能变成尽量多个 ab 串；
• 所有 b 都在匹配的 a 前面的段：贪心地保留一个尽可能长的全 b 前缀，剩下的答案是唯一的。实现只需要一对对删去，取字典序最大的字符串即可。

复杂度 \(O(n^2)\)。AC

AGC030C：

当 \(k\leqslant 500\) 时，可以直接构造一个 \(k\times k\) 的矩阵，第 \(i\) 行全为 \(i\)！

当 \(k>500\) 时，构造一个 \(500\times 500\) 且每条循环对角线颜色都相同的矩阵，然后把 \(k-500\) 个对角线改成颜色相间的形式就好了。

这凭啥铜牌。AC

AGC031~AGC040

AGC041~AGC050

AGC051~AGC056

表：