CF Round#959 Div.1+Div.2

Codeforces Round#959 Div1+Div2

A. Diverse Game

题意：构造一个排列与给出的排列每一位都不相同。

题解：每位+1输出即可。

B. Fun Game

题意：给定两个01串\(s, t\)，每次操作可以选定一个子区间\(l, r\)，替换\(s_{i} = s_{i} \ xor \ s_{i - l + 1}\)，问是否可以通过操作使\(s\)变成\(t\)。

题解：考虑前缀，异或自己1可以变成0，但是0无法变成1，如果一直到\(t\)串第一个1出现为止\(s, t\)都可以匹配，那么后面任何想要更改的位都可以通过这个1来逐位操作。

C. Hungry Games

题意：给定一个数组\(a\)，代表蘑菇的毒性，如果要吃掉一个区间\(l, r\)的蘑菇，会按照顺序吃，毒性每累积到\(x\)或更高，毒性会刷新清零，问有多少个字区间吃完后毒性累积不为0。

题解：对于每一个点求出到哪里毒性清零，然后从后往前递推一下即可。

D. Funny Games

题意：给定一个数组\(a\)，进行\(n-1\)次操作，每\(i\)次操作可以任选一个\(u, v\)满足\(|a_u - a_v| \equiv 0 \ mod \ i\)，会添加一条\(u, v\)之间的边。尝试给出一种方案使得图连通。

题解：样例猜个结论，一定有可行解，根据抽屉原理，模数总会有两个相同的，因此从\(n-1\)开始倒序构造，每次任选两个模数相同的点连起来即可。

E. Wooden Game

题意：给出\(n\)棵树，每次可以任选一棵砍掉一个子树，记其大小为\(x\)，求可以得到的最大的\(\sum xor(x)\)。

题解：一棵大小为\(x\)的树可以得到\([1, x]\)的任意结果，只需要一个一个的砍掉，直到剩下的大小为需要的结果。那么逐位构造答案，如果只有一棵树的大小这一位为1，那么直接减去这个大小继续构造，如果多于一棵则后续所有位都可以为1。

F. Stardew Valley

题意：给定一张无向图，有一部分边必须要选，一部分边可选，找出一条欧拉回路。

题解：必须选的边会导致一部分点的度数为奇数，但是加边不太好加，换一个思路从所有边往下删边，删非必选的边。

只考虑非必选边，搜索出一棵生成树，自下而上地遍历，若点的度数为奇数，删去与父亲连接的边，这样总能调整到所有的点都为偶数。（因为度数总和一定为2的倍数，所以根节点的度数奇偶性也可以得到保证）又由于图中保证了必选边的连通性，得到的图一定具有欧拉回路。

G. Minecraft

题意：给定\(n\)个数，求一个数\(x\)使得\(\sum a_{i} \ xor \ x = s\)，其中数为大数，以01串形式给出，01串的长度为\(k\)。

题解：先不考虑复杂度，很显然的想法就是按位考虑dp，但是问题是状态数目爆炸，想办法压缩状态。观察发现有效的状态其实非常少，因为\(x\)的这一位会造成\(n-cnt_i\)或者\(cnt_i\)的贡献，所以有效的状态不超过\(n\)个，状态就可以被压缩到\(O(nk)\)，直接dp即可。

H. Fortnite

题意：交互题，最多三次查询找出参数\(p, m\)，可以查询一个小写字母字符串，返回\((\sum ord(s_i)p^i) \% m\)，保证\(27 \le p \leq 50, \ p + 2 \leq m\)

题解：第一次查询\(aa\)得到\(p\)，第二次查询一定是构造一个足够大的串（至少要大于\(m\)），关键是第三次怎么得到\(m\)。

这种构造题，范围又给的很刻意，就会有一些神秘的性质。一个显然的思路是这样：记第二次查询的原始值为\(h_1\)，答案为\(a_1\)，那么显然\(h_1 - a_1 = km\)。那么如果第三次查询的原始值\(h_2\)满足\(h_1 - a_1 - 1 \geq h2 \geq h_1 - a_1 - m\)，那么就一定有\(h_2 - a_2 = (k - 1)m\)，即得到\(m = (h_1 - a_1) - (h_2 - a_2)\)。这个倒是不难想，关键是如何构造这样的\(h_2\)，注意到在这个\(p\)进制下，有些数字可能是表示不了的，因为小写字母只有1到26。

题解给了一种利用性质的构造方法，首先令第一次查询的串为\(zzzzzzz\)，我们不妨先不考虑1到26的限制，将\(a_1 + 1\)写为\(p\)进制数，即\(a_1 + 1 = \sum_{i = 0}^{i < len} d_i \ p^i\)，然后我们用\(h_1\)减去它得到一个可能不合法的\(p\)进制数。记不合法的下标集合为\(S\)，对于每个\(i \in S\)，令\(d_i = 26, \ d_{i+1} = d_{i + 1} - 1\)，得到一个合法的\(p\)进制串作为第三次查询。这样的构造一定能满足\(h_1 - a_1 - 1 \geq h2 \geq h_1 - a_1 - m\)，证明如下。

首先新构造出的值一定会更小，因为借位操作\(p \geq 27\)，因此满足\(h_2 \leq h_1 - a_1 -1\)。考虑发生借位的情况，借位操作会减去一个\(p^{i+1}\)，增加一个\(d_i \ p^i\)，因此借位操作会让构造出的\(h_2\)在\(h_1 -a_1 -1\)的基础上变小\((p - d_i)p^i\)。又因为发生借位的情况一定是\(d_i \geq 26\)，因此变小的差值为\(\delta = \sum_{i \in S} (p - d_{i}) p^{i} \leq \sum_{i \in S} 24p_{i}\)

又由于\(a_1 + 1 = \sum_{i = 0}^{i < len}d_i \ p^i \geq \sum_{i \in S}d_{i} \ p^i \geq \sum_{i \in S} 26p^i\)，所以\(\delta < a_1 + 1 \leq m\)，所以\(h_2 = h_1 - a_1 - 1 - \delta \geq h_1 - a_1 - m\)，得证构造出的\(h_2\)符合要求，通过三次查询即可算出\(p, m\)的值。