Codeforces Round 1011 (Div. 2) A/B/C/D/E

A

题意

对于一个字符串，当他的字典序比他的逆序串的字典序小时，我们说他是好的。现在给定一个长度为$n$的字符串，最多可以进行$k$次操作，每次操作可以选择两个位置的字符进行交换，问能否使得这个串变成好的

解法

当$k$为$0$时，显然只需扫描一遍按规则判断
当字符串内所有字符均相同时，显然这个串不可能变成好的
当$k$大于$0$，且存在不同的字符时，显然答案一定是可行——假如原串头和尾的两个字符不同，则将字典序小的那一个排在头即可；当头和尾两个字符相同时，找到一个与这个字符不同的字符，如果这个新字符字典序更小，则与头交换，否则与尾交换即可
复杂度$O(n)$

B

题意

给定一个长度为$n$的非负整数串，其中$n\ge 4$。你需要进行以下操作：选择一个长度至少为$2$的区间，将这个区间从串中去掉，替换成一个数字，大小为区间内数字的mex。你需要进行一系列操作后，使得这个串的长度为$1$，且串中的唯一一个数字为$0$，输出操作方案，不要求操作次数最少

解法

简单分类讨论
当整个串中不存在$0$时，直接对整个串进行一次操作即可
当串头或串尾中某一个不为$0$时，选择除了这个不为$0$的数以外的区间，这样取到的mex一定大于$0$（因为这部分里面一定存在$0$，否则会进入上面那一条分支），串中就剩下两个不为$0$的数，进行操作即可
当串头和串尾均为$0$时，随意选择一边，取最边缘的两个数，操作后的串变为上面那一条分支，继续操作即可，因为$n\ge 4$，因此这样操作一定可行
复杂度$O(n)$

C

题意

给定两个数字$x$和$y$，要求寻找一个$k$，使得$(x+k)+(y+k)=(x+k)\bigoplus (y+k)$，或者说明这样的$k$不存在

解法

异或的本质是二进制上不进位的加法，因此我们的目的实际上是找到一对$(x+k)$和$(y+k)$，使得在所有二进制位上都不存在两个数这一位都是$1$的情况
因此可以在二进制位上从小到大进行DP，考虑令$f[i][0/1][0/1]$表示当前在$(x+k)$和$(y+k)$从低到高的第$i$个二进制位上，两个数在这一位分别是否有向上进位（指$x+k$的过程产生的进位），满足这个条件时的任意一个合法的$k$；之后直接DP到第$32$位，取$f[32][0][0]$作为答案即可

D

题意

有$n$个时间点，每个时间点会有一盘寿司，第$i$盘寿司整盘寿司一起的美味值为$d_{i}$，每盘寿司内都恰有$k$个寿司。在每个时间点，可以选择拿取当前时间点端上来的这盘寿司，或者吃$1$个之前拿到的寿司，或者什么都不做。要求在$n$个时间点全部结束后，不存在拿取了但是没吃完的寿司，问所有拿取的寿司美味值之和最大是多少

解法

考虑对于一个方案是否合法，其中一个充要的判断条件为：对于所有的时间点，都有在这个时间点及之后拿取的寿司数量乘以$(k+1)$后小于等于从这个时间点开始还有多少时间点
稍微转换一下，我们就可以知道从后到前枚举，不考虑前面时间拿取的寿司的情况下，每个时间点开始可以再拿取多少盘寿司，而这个值只会变大不会变小
因此可以采取一个带反悔的贪心策略：从后向前枚举，当这一盘寿司拿取后不超过数量限制时，就拿，否则考虑已经拿取的寿司中美味值最低的一个，如果美味值比当前的寿司低，就放弃那一盘最低的寿司，拿当前时间点的寿司，这个可以使用一个堆来维护
复杂度$O(nlog_{2}(n))$

E

题意

有一个长度为$n$的原始数组$a$，将$a$里的每个元素对$k$取模，得到一个新的数组$b$，之后将$b$数组随机打乱。现在将原始的$a$数组和打乱后的$b$数组给你，求一个可能的$k$，或者不存在

解法

挺暴力的，不知道是不是正解
考虑对于合法的$k$，一定是大于等于$b_{max}$，小于等于$a_{max}+1$的（大于$a_{max}+1$的$k$和$a_{max}+1$没有本质区别），也就是$k$的范围实际上可以限制在$10^{6}$
那么对于$k\le 10^{4}$的情况，可以直接暴力模拟，看是不是合法解
对于$k\ge 10^{4}$的情况，考虑$a_{max}$对应的某个$b_{i}$，那么有$a_{max}\bmod k=b_{i}$，也就是$(a_{max}-b_{i})\bmod k=0$，此时由于$k\ge 10^{4}$，那么$\frac{(a_{max}-b_{i})}{k}\le 10^{2}$，也就是对于每个可能的$b_{i}$，可能合法的$k$不会超过$10^{2}$个，而且这个上界是非常宽松的（打表可知最大的是$50$个），去重之后再加上要求$k$大于等于$b_{max}$，最终枚举可能的$k$再暴力判断是可以通过的
复杂度$O(max(n\times 10^{4}, 50\times n^{2}))$