【比赛记录】CFR956（Div.2）

· · 个人记录

记录

ABCD 都切了，但是 CD 出现了低级错误，已经记录了。

题解

A. Array Divisibility

考虑直接赋 a_i=i，这样下标为 k 的倍数的数同样为 k 的倍数，符合题意。

B. Corner Twist

先处理出 r_{i,j}=b_{i,j}-a_{i,j}，考虑由上到下，由左到右将 r_{i,j} 归零，每次只用其下面和右面最近的三个格子。每行这样处理到 (i,m-1)，如果 r_{i,m}\ne0 即无解。处理完 n-1 行后若最后一行不全为 0 则无解。

正确是因为每种大于 2\times 2 的操作都可以转化成若干个 2\times 2 的操作，所以只用这一种操作推平即可。

C. Have Your Cake and Eat It Too

考虑若区间在中间的人选择 [l,r]，那么另外两个人分别选 [1,l-1],[r+1,n] 一定最优。所以分别以三个人为中间，枚举 l 二分最小的合法 r，再判断另外两个人能否填进去即可。预处理一下前缀和即可实现，时间复杂度 O(n\log n)。

D. Swap Dilemma

首先是特殊情况，若两个数组元素不同则无解，否则若同时有两个或以上相同元素则有解，因为可以在一者中交换相同元素来随意改变另一个数组。

接着可以转化，发现任意交换操作均能通过若干次交换相邻两个元素来达成，所以就转化为两个数组分别做若干次交换相邻元素。另外发现如果合法，就可以把数组交换成任意形态，所以转化为使其单调递增。

那么就有一个性质，每次交换可以消掉一个逆序对。那么求出逆序对数就是需要的最少交换次数。求出两个数组需要的次数 x,y，若 x,y 同奇偶则有解，否则无解。因为多的偶数次可以通过两次相同的操作消除掉。

E. I Love Balls

考虑把球按最终取出的顺序排成一个序列。先只考虑非特殊球，发现奇数位上是先手，偶数位上是后手，那么就能算出先手所占的比例，每个球都有同等的概率被先手取到，所以用这个比例乘上所有非特殊球的权值和就能求出先手这一部分的期望。

对于特殊球，考虑把它们插入非特殊球形成的空中，共有 (n-k+1) 个空，同样奇数位是先手，偶数位是后手。那么同样计算即可。可以算出先后手中一者的期望，用总和减去就是另一者的。

F. array-value

考虑二分答案，变为检验所有区间中权值不超过 mid 的数量是否达到 k。考虑枚举 r=j，找合法的 (l,r) 个数。首先找到最后一个 a_k\oplus a_j 的 k，那么所有 l\in[1,k] 均有 k,r 合法。保留下所有 r<j 的 r 对应的 k，那么这些 k 前面都合法，取最大值即为最靠右的合法位置 l 使 l,j 合法。

依次枚举 r=j 统计答案总和即可。那么问题变成了求出编号最大的 l 使 a_l\oplus a_r\le mid 的 l。考虑用 01Trie 维护目前所有的数，如果 mid 该位为 1 就跳到与 a_r 不同的子树，并记录另一子树的答案。否则直接跳到与 a_r 相同的子树。只要在 Trie 上维护目前子树内的编号最大值即可。