2021牛客暑期多校训练营2
仍然是单打的一场。
这场题目还很恶心，全是工地英语和毒瘤题，体验极差。
AC Codes
C. Draw Grids
容易发现能画的边数一定是 $nm-1$ ，判一下奇偶性就好了。
D. Er Ba Game
小模拟。
F. Girlfriend
注意到题目中的定义与阿波罗尼斯圆是一致的（因为 $\frac{AP}{PB}=k$ 包含所有 $\frac{AP}{PB}\geq k$ 的情况）。因此本题就是求两个球的相交部分体积，分三类讨论。
I. Penguins
所有状态不超过 $20^4$ ，因此直接暴搜。
K. Stack
这题是今天做过的题目里面唯一一个比较有趣的题。
首先，虽然题目中只有 $k$ 个限制，但是我们可以扩充至 $n$ 个限制，假设第 $i$ 位上的限制是 $lim_i$ 。然后，最核心的一点是注意到：如果存在合法的构造，那么 $lim_{i+1}-lim_i<1$ 。这个条件的充分性的证明很容易：每个元素入栈后，栈中元素数量最多增加 $1$ 。必要性可以构造证明：我们可以从小到大枚举 $lim_i$ 的数值，并从后往前依次填入排列中的数字。举个例子：1 2 3 2 3 1 ，我们可以这么填：
- 先从 $lim_i=1$ 开始：
2 x x x x 1； - 然后是 $lim_i=2$ ：
2 4 x 3 x 1； - 最后是 $lim_i=3$ ：
2 4 6 3 5 1。