2021.10.11模拟赛

But it used to fly so high

2021.10.11模拟赛

A. F

F

因为 $a\ \mathrm{xor}\ b=x \Leftrightarrow a\ \mathrm{xor} \ x=b$

如果要检验一个 $x$ 只需要 $O(n\log n)$ 时间即可

而答案必然是在 $a_1 \ \mathrm{xor} \ b_i$ 中的，所以总复杂度 $O(n^2\log n)$

B. S

S

如果知道最后的序列求一下逆序对就知道交换次数

同时能发现性质，最终序列的每个字符的相对顺序和一开始序列的相对顺序不变

所以设 $dp[x][y][z][0/1/2]$ 表示选了 $x$ 个 $A$ $y$ 个 $B$ $z$ 个 $C$ ，当前位置是 $A/B/C$ 的答案，枚举下一位选啥即可

$O(n^3)$

C.Y

Y

利用均分纸牌的结论，每个人给下一个人的数量里一定有个 $0$ ，为了不重复，枚举最后一个是 $0$ 的人，把他和下一个人断开

记 $dp_{i,j}$ 表示第 $i$ 个人给了 $j$ 个的价值积之和，那么 $dp_{i,j}=\sum dp_{i-1,k}(a_i+k-j)$ 拆式子发现只需要维护 $\sum dp_{i,j}$ 和 $\sum dp_{i,j} \times j$

注意枚举的下界需要按照是不是大于当前枚举的最后一个是零的人决定

这样复杂度 $O(n^2)$

考虑每次断开只有初始值不一样，转移过程一样，预处理转移矩阵前后积即可，复杂度 $O(n)$

D. o

火事

如果以时间为 $y$ 轴画出所有的数

那么每个点的范围是个平行四边形，拆成三个等腰直角三角形，然后维护平行于 $x$ 轴和平行于 $y=x$ 的就行

然后你就口胡完了!