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

· · 个人记录

记录

AB 切，C 想很久以后吃一发切，D 想一小会后吃一发切，E 最后开始搞线段树，最后发现假了，其实不难。

题解

A. Alice and Books

显然不管怎么分，A_n 一定会贡献到答案中，因此只需要从其余元素中找到最大的单独分一组即可，答案为 A_n+\max_{i=1}^{n-1}A_i

B. New Bakery

推式子，当取 k 时，结果为 (n-k)a+\sum_{i=b-k+1}^bi，等差数列求和并合并同类项，整理为 {res}=-\frac12k^2+(b-a +\frac12)k+an，是 {res} 关于 k 的二次函数，当 k=b-a+\frac12 时取到最大值。由于 k 为整数，同时值域为 [0,min(n,b)]，取最接近对称轴的整数即可。

C. Manhattan Permutations

由于 p 是一个排列，如果由 i 向 p_i 连边，每个点的出度和入度都为 1，得到的一定为若干个环。考虑构造使得每个环中只有一个 i 满足 p_i\le i，因为如果有两个这样的 i，直接将其中一个拆出来答案不变，所以这样一定包含了所有方案。

考虑每个环对曼哈顿值的贡献，由于只有一个 p_i\le i 的 i，所以整个环的贡献就是 2(\max(i)-min(i))，因此最终值也一定是偶数。所以这里把 k 直接除掉了 2，只考虑一边的贡献。

之后考虑最大化曼哈顿值，发现将 i 与 n-i+1 两两组合，组成 \lfloor\frac n2\rfloor 个二元环，最终值最大，等差数列求和得到最大值为 (n+n\mod 2)\lfloor\frac n2\rfloor，之后贪心地从大到小交换即可。

只有一种特殊情况是在 n 为奇数时，有可能最后剩下 k=1 而没有距离为 1 的点对，这时暴力找到一个没有改变位置的 i，将其与 i+1 交换即可，此时若 i+1 未被交换则这两个点贡献 1，否则变成三元环，总贡献也会增加 1

D. Elections

可以把 c 直接加给 a_1，显然跟原题意是等价的。之后求出 a 中最靠前的最大值编号 k，显然 k 的答案为 0。

考虑其他 x 的答案。由于 a_x 本身已经不是最大值，并且即使是去掉目前最大的 a_k，这一部分也会加到编号最小的 a_i 上，最大值一定不降。所以至少要将 x 之前的 x-1 个人全部去掉，才能使 x 为编号最小，a_x 增加以变为最大。

所以维护 a 的前缀和 s，若 s_x\ge a_k，只需要把前面全去掉即可，答案为 x-1。否则需要把前面全去掉，并且把 x 后面的最大值 a_k 也去掉，答案为 x。

E. Computing Machine

考虑一个区间的最优操作方案，发现先用 s 中的 0 把 t 中所有能变 1 的变完，再把 s 中所有能变 1 的变完，这样一定是最优的，因为这样保证了第一步之后 t 中的 1 最多，从而最终 s 中的 1 也最多。

接着考虑每一位会怎样被改变。若 s_i 被变为 1，需要 t_{i-1}=1 且 t_{i+1}=1，t 的这两位又会受到 s_{i-2},s_i,s_{i+2} 的影响，所以对于每一位 s_i，都只会受到 [i-2,i+2] 区间内的影响。

因此可以提前对整个区间进行操作，并对最终的 s 求前缀和。询问长度不超过 4 时直接暴力操作求解。超过 4 时由于 [l+2,r-2] 只受区间 [l,r] 内的影响，答案不变，直接记录下原来的答案，再单独对 [l,l+4] 操作并记录前两位的答案，对 [r-4,r] 操作并记录后两位的答案，把三部分相加即可。