本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-18 17:08:23

废话区

真希望这场没读错 D 题，或者先去做 E。

选任意一个选项，用大号打都能紫，然而我用的小号，而且 D 读错题了，E 赛时直接没看，再加上 C 对着题目保证不存在的 $n$ 为奇数的情况分讨了很久，perf 只有 1700.

A

首先判定总和为奇数的情况无解。

然后每次贪心删最大的两个，由于数据小，懒得推式子的话，multiset 模拟就可以。

B

有两种做法，我赛时写的是 $O(n \log (\max a_i) \log n)$，另一种是 $O(n \log (\max a_i))$。

我赛后测试，看着差了一个 log，但后者速度是前者两倍。

• 做法 1： 如果写一个暴力程序模拟样例，那么会发现存在单调性，即存在一个分界点，$k$ 比这个小一定不符合要求，比这个大一定符合要求。
  关于证明，假设现在有一个 $k_1$ 满足 $k=k_1$ 满足条件，那么事实上，经过一定思考可以比较容易得出这个结论（下一个做法用到）：$\forall i \in [1,n-k_1+1] $，满足 $a_i | a_{i+1} | a_{i+2} | \cdots | a_{i+k_1-1} = a_1 | a_2 | a_3 | \cdots | a_n$。
  现在，每个位置开头的连续 $k_1$ 个的数的 or 值还要再 or 下一个数，而每个位置新 or 的数显然已经包含在自身了，所以不会改变自身原本的值。
  现在就可以二分求解本问题了。 赛时记录
• 做法 2：
  根据做法 1 的结论，对于一个合法的 $k$，$\forall i \in [1,n-k+1] $，满足 $a_i | a_{i+1} | a_{i+2} | \cdots | a_{i+k-1} = a_1 | a_2 | a_3 | \cdots | a_n$。
  可以提前计算出整体 or 值，然后对于每个位置，计算这个位置向后延申多少个位置，or 值等于整体 or 值，最后对于所有位置，这个值取 max 就是答案。
  赛后记录

C

我赛时的分讨结论：不论 $n$ 奇偶，最优答案一定是 $2,4,6,8,\cdots$ 位置为局部 max，或 $3,5,7,9,\cdots$ 位置为局部 max。

先假设已经选好了第一种还是第二种，最劣情况是选中的值是 $1,2,3,\cdots \lfloor \frac{n-1}{2}\rfloor$，而 $1,2,3,\cdots$ 紧挨着的是 $n,n-1,\cdots,\lfloor \frac{n-1}{2} \rfloor+1$。

由于值为 $1,n$ 相邻，导致无论如何值为 $1$ 的得放弃，如果不放弃，还会连锁反应导致其他的也废掉。

考虑第一种，如果第 $2,4,6,8,\cdots$ 位置中，不存在一个位置使得值为 $1$，且旁边有值为 $n$，那么第一种构造是最优解。

反之，如果存在呢？

那就跳过它就好了，选第二种构造，因为只要选中的数不存在 $1$，那么我们希望构造的局部最大值显然可以构造成全部为 $n+2$，然后将非局部最大值全部弄成小于等于 $n-1$。

赛时记录

D

赛时看成了所有加起来等于 $m$，非常遗憾没有通过这道送分题。

看到这题，我第一个想到的是根据最大值。

事实上可以通过 $n$ 次询问求出最大值。

然后，注意，划分成 $k$ 段，每段的值都等于 $m$，且同时取决于它的最大值和它的长度。

那么注意，整体最大值肯定也是它所属的段的最大值。

所以，只需要枚举整体最大值所在段的长度，并判定是否合法就可以。

比较容易得出，整体最大值所在段的长度一定不超过 $\frac{n}{k}$

然后，每次判定需要 $k$ 次询问，将前后询问总数加起来，$\lfloor \frac{n}{k} \rfloor \cdot k + n \le 2n$，可以通过本题。
赛后记录

E

这题感觉也就 1800 难度，为啥放 E 啊赛时没机会看。

考虑 $3$ 个数 $a \lt b \lt c$。
其中 $a,b$，$a,c$ 可以交换，而 $b,c$ 不能交换。
草稿纸上模拟一下，可以发现事实上 $a,b,c$ 可以通过一定操作任意交换！

然后就有了本题解法。

将能交换的两个数放到同一个连通块，最后同一个连通块内的所有数都可以互相交换。

草稿纸上模拟一下 $l \neq r,l \le n+1$ 的情况。

然后发现了一个惊喜： $\forall i \in [1,r-1]$ 都处于同一个连通块！

那么对于 $l \neq r$ 且 $l \gt n+1$ 呢？

略微思考可得 $\forall i \in [l-n,r-1]$ 处于同一个连通块。

所以说，对于 $l \neq r$ 的部分，只需要枚举 $r$，那么 $l$ 就是从 $1$ 开头的一段合法的区间，使得需要囊括所有的错位的数字值域，很容易计算。

再来想想 $l = r$ 的部分。

考虑先找出任意一对原序列中需要互相交换位置的数字 $x,y$。

如果存在 $l=r$ 的解，那么这个 $r =x+y$ 即 $r = x+y$

接下来，就是对于所有需要互相交换的数字，判断和是否为 $x+y$。

如果全部满足，那么存在一组 $l=r = x$ 符合要求。
赛后记录

F

暂时不会。