Codeforces Round 1028 (Div. 1) 部分题解

注意

题解写得可能非常抽象。

「如果一个题解你看不懂，那是题解垃圾而不是你垃圾。」

A. Gellyfish and Flaming Peony

题意

有 $n$ 个正整数 $a_i$ ，你一次操作可以选择 $i,j$ 然后 $a_i\gets \gcd(a_i,a_j)$ 。问最少操作次数使得所有数都相等。 $n,a_i \leq 5000$

题解

首先不难发现最后所有数都变成 $\gcd(a_1,a_2,\cdots,a_n)$ 。如果这个数存在，则只需要让不等于这个数的数都变成这个数即可。否则 DP，设 $f[x]$ 表示使得某个数变成 $x$ 需要的最少操作次数。 $f[\gcd(x,a_i)]\gets \min(f[\gcd(x,a_i)],f[x]+1)$ 。最后把所有数与造出来的这个 $\gcd$ 取 $\gcd$ 即可。

B. Gellyfish and Camellia Japonica

题意

有一个长度为 $n$ 的序列 $a$ ，给定多次操作， $a_{x_i} \gets \min(a_{y_i}, a_{z_i})$ 。给定最终序列，求一个可能的原序列，或判断无解。 $n,q\leq 3\times 10^5$ 。

题解

建图。为每次操作得到的新数建点，从 $y_i$ 和 $z_i$ 当时对应的点向这个点连边。有 $n$ 个点的值已知（序列的最终状态），要求每个点的值必须要大于等于其出边，因此拓扑排序复原出一个原序列。再做一遍操作，验证是否能得到最终序列。

C. Gellyfish and Eternal Violet

有 $n$ 个怪物，每个血量为 $a_i$ 。给定 $p$ ，有一把武器，每一回合：有 $p$ 的概率这把武器会被附魔，你得知它是否附魔后可以选择是否跳过这个回合，如果不跳过的话，附魔的武器可以（且必须）对所有怪物造成 $1$ 的伤害，没有附魔的武器可以对一只怪物造成 $1$ 的伤害。有 $m$ 个回合，问最优策略下，能把所有怪物的血量都降到恰好为 $1$ 的概率是多少。 $\sum n\leq 100, a_i\leq 400, m\leq 4000$ 。

题解

附魔的武器一定能用就用。整个流程分为两个阶段：首先使用不附魔的武器，把所有怪物的血量降到相同值；然后维持所有怪物血量极差不超过 $1$ 。第一个阶段，可以计算不附魔攻击的次数，枚举达到这个次数前出现了多少次附魔攻击，相应可以计算概率；第二个阶段，DP，设 $f[i,j,k]$ 表示怪物血量的最小值为 $i$ ，有 $j$ 只怪物血量是 $i+1$ ，还剩 $k$ 个回合，成功的概率。转移分情况：

$i>1, j\neq 0$ ：一定用武器，如果附魔就 $i-1$ ，否则 $j-1$ ；
$i>1, j=0$ $i > 1, j = 0$ ：有两种策略：
- 只用附魔的武器；附魔则 $i-1$ ，否则 $i,j$ 不变；
- 都用；如果附魔就 $i-1$ ，否则 $i-1, j = n-1$ 。
$i=1, j\neq 0$ ：只用非附魔的武器；附魔则 $i,j$ 不变，否则 $j-1$ 。

我有某个线性基，特别地，每个基都带了一个标志，代表它用来最大化还是最小化答案；
给定初值后，从高到低位枚举每个基，按照这个基对应的标志和 $x$ 的当前位决定是否使用这个基。

我们考虑从后往前枚举每个数，初始基为空，记当前数为 $t\gets a_i$ ，从高到底考虑每一位：

如果 $t$ 这一位为 $0$ ，那么这个数对于这一位没有影响，继续看线性基中的更低位；
如果 $t$ 这一位为 $1$ ，而当前的基中没有这个数，把它加入基中，并且根据 $c_i$ 打上标志：这是序列里最后一次让这一位可以自由地异或上 $1$ 的机会了，当前操作的人一定能利用这个机会来控制最后的答案；
如果 $t$ 这一位为 $1$ ，而当前的基中已经有这个数，那么 $t$ 异或上当前的基中这个数 $b_j$ ，继续看线性基中的更低位：尽管是否异或上 $t$ 对当前位没有影响，但如果我多异或一次 $t$ ，那 $b_j$ 也要跟着多异或一次来抵消，相当于我能让更低位异或上 $t \oplus b_j$ 。

上面的过程既是算法流程也是证明。