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

A

题意

给定一个长度为$n$的数列$a$，要求执行若干次操作直到$a$的长度变为$1$，每次操作可以选择当前$a$长度的一个不等于$1$的因数$k$，将$a$分成若干个长度为$k$的子序列（而非子串），之后将这些子序列分别求平均数，组成新的数列$a$。问是否有可能使得最后$a$中唯一的数字为$x$

解法

容易看出和证明，这个操作实际上并不会改变整个$a$的平均数，因此最后剩下的数字就是$a$中所有数字的平均数，判断一下即可
复杂度$O(n)$

B

题意

有$n$个房间，每个房间内有一个人，其中第$i$个房间和出口之间的距离为$n-i$，房间之间不互通。现在要在每个房间内安装一个传送器，指定其中的人传送到另一个房间（不能传送到当前房间），之后对所有房间进行$k$轮传送（相当于每人传送$k$次），问如何布置传送器可以使得最终所有人离出口的距离之和最短

解法

很明显最好的情况就是所有人都走到第$n$个房间，但是因为必须走$k$次而且不能传送回自己，因此实际上显然无法做到。实际上最好的办法就是由$n$和$n-1$两个房间构成一个小循环，其他房间的人通过计算$k$的奇偶性来判断传送到哪个房间可以在最后落在$n$号房间，这样所有的人中有且仅有一个人不在$n$号房间，且距离出口仅为$1$，这就是最优解了
复杂度$O(n)$

C

题意

有一个长度为$2n+1$的原数组$a$，所有数字都在$[1,10^{18}]$以内，两两不同，并且满足条件：$a_{1}=a_{2}-a_{3}+a_{4}-a_{5}+…+a_{2n}-a_{2n+1}$。将数组$a$打乱，之后删去其中一个数字，得到一个长度为$2n$的数组$b$。现在给定一个数组$b$，求一个可能的原数组$a$

解法

注意到$b$的数据范围是$[1,10^{9}]$，与$a$不同
实际上原数组$a$的条件中，如果进行一些移项，将奇数项移到等式左边，偶数项移到等式右边，可以发现，这个条件等价于所有奇数项的和等于所有偶数项的和
考虑到经过随机打乱，因此还可以理解成分成大小为$n+1$和$n$的两组数字，他们的和相等
在这个理解下，考虑$b$中被删掉的数字，要么是从$n+1$组里删的，要么是从$n$组里删的，因此可以发现，要构造一个满足条件的$a$很容易，核心问题是数组$a$的另一个要求：两两不同，因此必须构造一个数组$b$中没出现过的数字
其中一个构造方案是，考虑被删掉的数字是$n$组中的，于是将数组$b$中最大的$n+1$个数字分到$n+1$组，剩下最小的$n-1$个数字分到$n$组，由于$n+1$组中最小的$n-1$个数字也比$n-1$组中的每个数字大，因此被删掉的这个数字，也就是两组数的差，大小就至少是$b_{最大}+b_{次大}+n-1$，这个数字显然不可能在$b$中出现过，并且最大情况下也就是$(n+1)\times10^{9}=2\times 10^{5}\times 10^{9}\lt 10^{18}$，因此满足条件
复杂度$O(nlog_{2}(n))$

D

题意

有一条路，分为两行，路上排列有$n$个关卡，每个关卡在每一行上有一个门。可能有两种门，一种是$+x$，一种是$\times 2$或$\times 3$。一开始两行上各有一个人，他们将经过这$n$个关卡。当经过一个门时，将按照门的规则增加一些新的人，例如，如果是$+x$就会增加$x$个人，如果是$\times 3$就会增加这行上已有的人数的$2$倍。新增加的这些人你可以任意分配到两行之中，不一定要放在导致他们产生的门所在的行上，但是已经在某一行上的人不能转移到另一行。问最终最多可以有多少人

解法

显然，当你站在某一个关卡面前，目前具体有多少人是不重要的，无论有多少人，最优解都是确定的。因此我们可以用DP来推算这个最优解。
考虑从后往前，$f[i][0/1]$表示假如有$1$个人在这一关走进了第$0/1$行，最终会变成多少人。那么DP的转移就很好考虑了：首先这个人一定会继续往后走，因此$f[i][j]=f[i+1][j]$，之后考虑新增加的人，可能是$+$，可能是$\times$，假设走过这个门后新增加的人为$x$，那么这$x$个人可以自由分配，显然应该分配往下一关中$f$更高的那一行，因此最终的转移式为
$$f[i][j]=f[i+1][j]+x\times max(f[i+1][0],f[i+1][1])$$
复杂度$O(n)$

E

题意

交互题，有两个隐藏的数字$x$和$y$，你可以询问最多两次，每次询问一个数字$n$，将会得到$(n|x)+(n|y)$的值。之后，评测系统给出一个数字$m$，要求计算$(m|x)+(m|y)$的值。满足$0\le x,y,n,m\lt 2^{30}$

解法

挺恶心的一个题
显然这个题要考虑二进制表示
由于我们完全没有$x$和$y$的信息，又只能问两次，这两次显然大概率是某些”Magic Number”。考虑作为按位或相加的结果，第一次询问$0$是一个比较容易想到的选择，这样我们就得到了$x+y$的值
在二进制下，每一位之间求和其实是相对独立的，你对低位唯一关心的是它是否对你产生进位，因此我们比较关心在$x+y$这个结果中，每一位是否对上一位产生了进位，知道了这个我们就能构造一组$x$和$y$，这样构造出的任意一组$x$和$y$，对某个数按位或之后相加的结果都是相同的
那么我们如何知道某一位是否产生进位呢？我们可以通过询问来观测。考虑如果我单独对某一位询问$1$，其他位询问$0$。那么，如果这一位的更高一位的结果与$x+y$中不同，就说明在$x+y$中这一位是没有产生进位的，反之就是有进位的
但是我们在经过了询问$0$之后，就只有一次询问了，而我们不可能对所有位置询问$1$，因为这样答案是固定的$2^{30}$，没有意义
这时注意到，当我们对这一位询问$1$时，这一位单独求和的结果显然是$0$，那么，如果返回的结果中，这一位不是$0$而是$1$，就说明这一位的低一位产生了进位
因此我们就有了一个方案，询问一个特定的数，这个数中从低往高，奇数位都是$0$，偶数位都是$1$，这样通过返回的结果与$x+y$中的结果比对，就可以得知每一位在$x+y$中是否产生了进位，也因此可以构造出一组$x$和$y$了
要注意这里细节比较多，例如，新询问的$1$带来的进位可能会导致原本不产生进位的高一位产生了进位，在后续的计算中需要考虑到这一点
复杂度$O(30)$