Codeforces Round 1066 (Div. 1 + Div. 2)
A. Dungeon Equilibrium
定义“平衡”为：如果某个值 \(x\) 在数组中出现，则它必须恰好出现 \(x\) 次。
给定一个数组，问最少删除多少个元素后数组能变得平衡。
直接用桶来统计，出现次数大于 \(i\) 的删到 \(i\)，小于 \(i\) 的抹除。
B. Expansion Plan 2
有一个无限网格，初始只有 \((0,0)\) 是黑色。
给定一个由'4'和'8'组成的操作序列：
'4'：与黑色单元格正交相邻（上下左右）的格子变黑；'8'：与黑色单元格正交或对角相邻（周围 \(8\) 格）的格子变黑。- 问：执行完所有操作后，某个给定坐标 \((x,y)\) 是否是黑色。
- 操作具体的顺序不重要，我们只关心个数。
- 其他方向也不重要，我们只关心最短的路线，因此只考虑右上的方向。
- \(x\) 和 \(y\) 的正负和顺序而不重要，考虑将其取绝对值，并使较小值为 \(x\)，较大值为 \(y\)。
一个'8' 可以右一上一，一个'4' 可以右一或者上一，判断是否够用就好。
C. Meximum Array 2
构造一个长度为 \(n\) 的数组，满足若干约束：
约束 \(1\)：区间 \([l,r]\) 的最小值等于 \(k\)；
约束 \(2\)：区间 \([l,r]\) 的 MEX（最小未出现非负整数）等于 k。
要求输出任意一个满足条件的数组（保证有解）。
这个保证有解居然是最重要的性质。
转化一下约束：
- 约束 \(1\)：区间 \([l,r]\) 中的数均在 \([k,+\infin)\)，且 \(\exist i \in[l,r]\) 使 \(x_i=k\)。
- 约束 \(2\)：区间 \([l,r]\) 中出现了 \([0,k-1]\)，同时数 \(k\) 不出现。
对每个位置可能的情况分讨：
- 需要满足约束 \(1\) 和 \(2\)：相当于 \([0,k]\) 都不可取，不妨取 \(k+1\)。
- 需要满足约束 \(1\)：取值 \([k,+\infin )\)，不妨取 \(k\)。
- 需要满足约束 \(2\)：需要与其它位一起满足，不妨取 \(i \bmod k\)。
- 没有约束：随意。
解释一下满足约束 \(2\) 时的取法，因为保证有解，约束 \(2\) 的区间至少长度为 \(k\)，坐标取模后显然可以满足。
考试时就是没有想到这一点，打了个 \(O(qn^2)\) 的程序还没调出来。