Codeforces Round 945 (Div. 2) 记录

__vector__ · 2024-05-18 17:08:23 · 个人记录

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

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

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

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

有两种做法，我赛时写的是 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，可以通过本题。
赛后记录

这题感觉也就 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 符合要求。
赛后记录

暂时不会。