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

A

题意

给定一个$01$串$s$和一个空串$t$，可以无限次执行两种操作：把$s$的一个后缀移除，接到$t$的后面；把$t$的一个后缀移除，接到$s$的后面，现在要使得串$s$内都是字符$0$，串$t$内都是字符$1$，问最少操作次数

解法

显然最优做法是把串$s$分成只有$0$和只有$1$的连续子串，之后轮流放到$s$和$t$的后缀
答案就是子串的数量，如果第一个子串是$1$开头则还要$+1$
复杂度$O(n)$

B

题意

定义一个数列的分数为数列长度减去数列中出现的整数的种类数。给定序列$a$，可以选择删掉$a$的一个连续子串，使得删除后$a$的分数最高，在分数相同时，输出删掉子串最长的方案，再相同时输出任意方案

解法

这题的核心问题其实不是分数相同，而是删掉子串最长。考虑到数列分数的定义和可以不删除的情况，那么可以被删掉的数字只有在数列中只出现一次的数字，所以问题变成求只出现一次的数字组成的最长连续子串，先扫一遍判断每个数字是否只出现一次，再扫一遍求最长的连续出现次数即可
复杂度$O(n)$

C

题意

给定一个数列$a$，包含非$0$的整数，一开始你有$0$分，你可以执行以下操作任意次：假设当前数列$a$的长度为$m$，选择一个下标$i$，满足$1\le i\le m$，获得$|a_{i}|$分，之后，如果$a_{i}\lt0$，则移除$a_{i},a_{i+1},…,a_{m}$，否则移除$a_{1},a_{2},…,a_{i}$，问最后最多可以得到多少分

解法

考虑到选择一个正数会使得下标小于这个正数的数字都被移除，而负数则相反，因此最终被选中的下标中不可能出现一个下标小的负数和一个下标大的正数，因为他们会互相移除。
于是最后的方案一定是连续的正数之后连续的负数，那么我们只需要找到一个分界点，分界点左侧选择所有正数，分界点右侧选择所有负数即可
为了保证复杂度，先反向预处理一遍所有后缀的负数的绝对值之和，然后从头扫一遍枚举分界点即可
复杂度$O(n)$

D

题意

给定一个史莱姆序列$w$，每只史莱姆有一个重量$w_{i}$，定义一只史莱姆可以吃掉另一只史莱姆，当且仅当他的重量大于等于被吃的史莱姆，吃掉后这只史莱姆的重量变成二者重量的异或。现在有$q$次询问，每次询问给出一个整数$x$，问假设有一只史莱姆重量为$x$，放在序列的最后一位($n+1$处)，然后一路向左吃，直到无法继续吃为止，最多可以吃几次。注意每次询问不会实际改变史莱姆序列，也就是每次询问的序列都是初始的史莱姆序列

解法

手动模拟过程后可以发现，一路向左吃时，新史莱姆的重量的二进制最高位只会变小不会变大。因此当比新史莱姆的二进制最高位更高的位上有$1$的史莱姆出现时，无论如何它都无法吃掉。
那么可以想到的一个朴素做法就是，考虑当前史莱姆的最高位，从后往前找到第一只最高位大于等于当前史莱姆最高位的史莱姆，中间的史莱姆由于最高位都更小，而一定可以被吃，判断一下能否吃掉这一只史莱姆，不行就结束了，可以的话更新当前史莱姆的重量，之后继续这个过程直到碰到吃不掉的
优化这个做法需要一些预处理，预处理每个后缀史莱姆的异或和用来判断能否吃掉这一只史莱姆；预处理到每个位置为止，最高位大于等于第$j$位的史莱姆最后一次出现在哪个位置
这样，预处理后每次转移都是$O(1)$的，而因为每次吃掉最高位与自己相同的史莱姆后，最高位一定会下降，因此这样的判断最多进行$log_{2}(n)$次，因此复杂度可以通过
复杂度$O((n+q)log_{2}(n))$

E

题意

定义一种重力排序法为：给定一个排列，从上往下每一行分别放置对应数量的沙块，之后让沙块坠落，得到排序结果，具体参考下图

现在考虑给每个方块染色，并且每一行的方块的颜色都相同，那么我们对于一个排列$p$，可以得到一个颜色数列$c$，例如对于上图，排列$p=[4,2,3,1,5]$，颜色数列$c=[1,3,1,2,4]$
现在给定一个排列$p$和一个颜色数列$c$，问有多少种可能的$p’$和$c’$的组合，按照重力排序法排序后沙块的最终图案和给定的$p$和$c$相同。注意给定的$p$和$c$也要计入答案

解法

考虑按列从左往右考虑这个问题，会发现从第二列开始，每一列都是上一列去掉某一个块，假设当前是第$i$列，那么被去掉的那个块实际上就是数值为$i-1$的那一行的最后一个方块，因此我们可以把重力排序法的问题转换成这个模型，也就是按顺序移除方块的模型。
而如果要保证当前这一列不会被影响的话，可以发现合法方案实际上就是某一个连续的相同颜色的段中任意选取一个删掉，因此问题变成在每一步的时候，考虑当前被删掉的方块，所在的连续的颜色相同的段中，方块的数量，并乘到答案中
那么我们可以用一个双向链表来维护当前的每个方块前后是哪个方块，用并查集来维护连续的颜色相同的段的大小，之后挨个删除的过程中把每一步删除的块所在的并查集的大小乘到最终答案里即可
复杂度$O(nlog_{2}(n))$(假设并查集的复杂度为$O(log_{2}(n))$的情况下。如果使用路径压缩+按秩合并则复杂度可以压缩到$O(n\alpha(n))$，其中$\alpha(n)$为反阿克曼函数)