Codeforces Round 1004 (Div. 1, Div. 2) A/B/C/D/E/F
(题号以Div. 2计算)

A

题意

给定两个数字$x$和$y$，问是否存在数字$n$，使得$n$的十进制表示下的数位之和等于$x$，$n+1$的十进制表示下的数位之和等于$y$

解法

$y=x+1$时显然有解；$y\gt x+1$时显然无解；当$y\lt x$时，需要利用到$9+1=10$来减少，具体而言，总体上$+1$后，后缀每一个$9$都会使得总的数位之和减少$9$，因此只要判断$y$和$x+1$之间的差值是否为$9$的倍数，以及$x$是否足够拆分出这么多个$9$即可
复杂度$O(1)$

B

题意

给定两个集合$A$和$B$，其中$B$集合一开始是空集。可以无限次进行两种操作之一：将一个数从$A$集合移动到$B$集合，或选择一个$A$集合和$B$集合中都存在的数，将$A$集合中的其中一个该数字$+1$。问能否使得$A$集合和$B$集合完全相同

解法

注意到两件事：当一个数进入$B$集合后，就再也不会变化了；如果某一类数字有超过两个，把其中一个送到$B$集合，剩下的数字留一个在$A$集合，把其他数字都$+1$，这个操作是不会使答案变劣的。因此只需要从最小的数字开始执行这个操作，直到某一个数字只有一个，则无解，否则有解
复杂度$O(n)$

C

题意

给定一个数字$n$，问最少需要加上几个在十进制下每一位都是$9$的数字，才能使得$n$在十进制下至少有一个数位是$7$

解法

注意到每次增加的$9…9$实际上可以写成$10^{x}-1$，因此假设最后答案为$k$，则问题可以转化为：对于数字$n-k$，每次加上形如$10^{x}$的数字，至少几次可以使得$n$在十进制下至少有一个数位是$7$。而增加一个$10^{x}$，实际上就是某一个数位$+1$，这样就可以枚举最后的答案，然后枚举每个数位，检查这一个数位需要加几次才能等于$7$
注意这个方法有个问题，对于$n-k$的假设，需要特殊考虑$n\lt k$的情况
有一个更加暴力的方法。由上面讲的方案，实际上可以得到一个结论，一定存在一个最优解，每次增加的数字都是完全一样的。因此可以直接枚举这个数字（也就是每次增加一个几位数的$9…9$），然后一直加直到出现一个数位为$7$为止。这个算法复杂度是上面的$log_{10}(n)$倍，但好写很多，不需要考虑什么特殊情况
复杂度$O(10log_{10}(n))$或$O(10(log_{10}(n))^{2})$

D

题意

交互题。已知有两个长度为$n$的数列$x$和$y$，每个数都是范围在$1$到$n$之内的整数。你已知$x$，但不知道$y$。题目保证对于所有$i$，$x_{i}\neq y_{i}$，并且对于所有$i\neq j$，$x_{i}\neq x_{j})$或$y_{i}\neq y_{j}$。现在有两个模型：其一是，这两个数列描述了一张$n$个点的有向图，每条边是从$x_{i}$到$y_{i}$；另一个是，这两个数列描述了平面上的$n$个点，第$i$个点的坐标是$(x_{i},y_{i})$。你需要在$2$次询问内判断这次使用的是哪个模型。对于每次询问，输入$i$和$j$，如果使用的是第一个模型（有向图），则返回从点$i$到点$j$的最短路长度，如果从点$i$无法到达点$j$，则返回$0$；如果使用的是第二个模型（平面上的点），则返回从点$(x_{i},y_{i})$到点$(x_{j},y_{j})$的曼哈顿距离，也就是$|x_{i}-x_{j}|+|y_{i}-y_{j}|$

解法

注意到，对于第一个模型，所有边的出发点都是$x$数列中的某个点，也就是没出现在$x$数列中的点，无法到达任何一个其他点；对于第二个模型，两个点的曼哈顿距离至少是$|x_{i}-x_{j}|$，所以返回值不会小于这个值，而又因为没有两个点坐标相同，所以返回值不会是$0$。有了这两个结论，我们就可以构造一个询问了
如果数列$x$中有某个数字没有出现，那么直接询问这个数字和任意一个其他数字，如果返回了$0$，那么是第一个模型，否则是第二个模型
如果数列$x$是一个从$1$到$n$的排列，那么在第二个模型下，$x_{i}=1$的点和$x_{i}=n$的点之间，曼哈顿距离至少会是$n-1$，并且询问顺序对答案没有影响；而对于第一个模型，询问顺序会有影响，相反的询问顺序($i,j$和$j,i$)都能返回结果仅当$i$和$j$在一个环上，而这个环最大是$n$，因此两种询问顺序的回答，加起来不会超过$n$。那么我们找到$i$和$j$使得$x_{i}=1,x_{j}=n$，询问两次，分别询问$i,j$和$j,i$，返回的两次结果相等并且大于等于$n-1$的，就是第二个模型，否则就是第一个模型
复杂度$O(n)$

E

题意

定义一个数列$a$是魔法的，当且仅当对于所有的$1\le i\lt n$，有$min(a_{1}…a_{i})\ge mex(a_{i+1}…a_{n})$，特别的，所有长度为$1$的数列都是魔法的。现在给定一个长度为$n$的数列$a$，问$a$的最长魔法子序列

解法

注意到，我们有一个兜底的子序列：所有非$0$元素组成的子序列，这个子序列一定是魔法的。同时，注意到另一个性质：一个魔法的数列，其中最多只能有一个$0$。因此，我们实际上只有两种可能的结果：所有非$0$元素组成的子序列，以及在这个子序列中加入一个$0$。观察后可以发现，对于两个不同位置的$0$，如果右边的$0$是合法的，那么左边的$0$一定也是合法的。因此我们只需要考虑能否将数列中的第一个$0$加入选取的子序列中，这个只需要模拟即可。
复杂度$O(nlog_{2}(n))$

F

题意

有三个一开始为$0$的数字$P,Q,R$，和一个长度为$n$操作序列$a$，第$i$次操作要求选择$P,Q,R$其中之一，使其异或上$a_{i}$，要求每次操作之后$P,Q,R$中至少有两个数字是相同的，问合法的操作方案数

解法

注意到，$P,Q,R$三个数字只有两种状态：三个数字皆相同，或者其中一个数字与另外两个不一样。当一个新的操作数$a_{i}$进来时，如果其异或上不一样的那个数字后与其他两个数字不相同，那么他一定只能选择这个不一样的数字来异或。同时考虑到操作的特殊性，$a,a,0$实际上和$0,0,a$对后续的操作来说是完全等价的。
那么我们实际上可以将三个数字的状态一直保持为全是$0$或者两个$0$和一个独立数字。而对于每次操作，如果新的数字与当前的独立数字相同，则可能转移到三个$0$的状态，或者独立数字不变，但移动到另外两个数字上。
因此可以考虑维护一个状态$g[i]$，表示独立数字为$i$时的方案数，而每次的转移就是，对于$g[0]$，会三倍转移到$g[a_{i}]$上（可以任选一个数字异或）；对于$g[a_{i}]$，会两倍转移到自己，一倍转移到$g[0]$上；对于其他数字$g[x]$，会转移到$g[x\bigoplus a_{i}]$上。
上述算法是$O(n^{2})$的，但是注意到大部分数字实际上每一轮都是异或一个相同的值，因此可以考虑实际上将下标改为实际下标与前缀操作数的异或，这样就不需要每次都转移每一个数字，而只要进行两个特殊位置的转移即可。
复杂度$O(n)$