本来要打这场的,但由于某种原因鸽了.
vp 一看题发现全是神必构造,一道都不会,跑路了.题目一道都改不来,感觉要完蛋了.
A - Sign Flipping
让奇数位置上的 $a_i\ge 0$ ,偶数位置上的 $a_i\le 0$ 即可.
也可以脑瘫地去 dp, 设 $dp(i,j,0/1)$ 表示考虑了前 $i$ 个数,有 $j$ 个差分是 $\ge 0$ 的,第 $i$ 个数为 $a_i/-a_i$ 时是否合法.
若两个数相同,则既可以转移到 $j$ ,也可以转移到 $j+1$ ,最后让 $\ge 0$ 的差分数目恰好为 $\frac{n-1}{2}$ ,转移时要记录方案.
B - Neighbor Grid
角上填 $2$ , 边上填 $3$ ,中间填 $4$ ,再判一下是否合法即可.
C - Element Extermination
手玩一下,不难发现有解的充要条件是 $a_n>a_1$ .
D - Replace by MEX
为了方便,规定序列下标从 $0$ 开始.
若当前的 ${\rm mex}=n$ ,则随便找一个 $a_i\neq i$ 的位置进行操作,若找不到,说明已经符合要求,不用再进行操作.
若当前的 ${\rm mex}\neq n$ ,则对 $\rm mex$ 这个位置进行操作.
可以发现,这两种操作是交替进行的,且执行完两次操作后, $a_i\neq i$ 的位置数目会恰好减少 $1$ .
于是 $2n$ 次操作内一定可以让序列每个位置都满足 $a_i=i$ .
E - Inversion Swapsort
从前往后考虑每个位置 $i$ ,将所有 $j>i$ 的 $(i,j)$ 交换操作全部执行,需要给这些 $j$ 确定操作的顺序.
记原序列,即未进行任何操作的序列 $a$ ,为序列 $b$ ,不难发现将这些 $j$ 按照 $b_j$ 为第一关键字, $j$ 为第二关键字从大到小排序,依次执行这些 $(i,j)$ 操作即可,最后一定能得到单调不上升的 $a$ 序列.
F - Integer Game
结论是先手有三步必杀策略.
记 $k=10^9$ .
第一轮先手令 $y=k$ ,后手操作后变为 $a+k,b,c$ .
第二轮先手令 $y=2k+2a-b-c$ ,后手操作后变为 $a+k,2k+2a-c,c$ 或者 $a+k,b,2k+2a-b$ .
此时三个数从小到大形成了等差数列,并且上一次后手操作的一定是最大的数,第三轮先手令 $y$ 为公差即可取胜.
G - Tree Ｍodification
将树看作二分图,黑白染色,考虑一次操作 $(a,b,c)$ ,我们只反转 $a$ 的颜色,其他点的颜色就可以维持不变.
每次操作能让某种颜色点数 $-1$ ,且只要该颜色的点数 $\ge 2$ ,就一定能找到合适的 $(a,b,c)$ 使得它的点数 $-1$ .
最后要形成菊花图,即某种颜色只有一个点,于是答案就是初始时黑白点数目较小者 $-1$ .
H - Set Merging
I - Cubic Lattice