跳至主要內容

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

Wallbreaker5th大约 4 分钟OI×ICPCOI×ICPCCodeforcesOI×ICPC - 题解OI×ICPC - DPOI×ICPC - 拓扑排序OI×ICPC - 概率OI×ICPC - 组合数OI×ICPC - 线性基OI×ICPC - 位运算

注意

题解写得可能非常抽象。

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

A. Gellyfish and Flaming Peony

题意

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

题解

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

B. Gellyfish and Camellia Japonica

题意

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

题解

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

C. Gellyfish and Eternal Violet

题意

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

题解

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

  • i>1,j0i>1, j\neq 0:一定用武器,如果附魔就 i1i-1,否则 j1j-1
  • i>1,j=0i>1, j=0:有两种策略:
    • 只用附魔的武器;附魔则 i1i-1,否则 i,ji,j 不变;
    • 都用;如果附魔就 i1i-1,否则 i1,j=n1i-1, j = n-1
  • i=1,j0i=1, j\neq 0:只用非附魔的武器;附魔则 i,ji,j 不变,否则 j1j-1

D. Gellyfish and Forget-Me-Not

题意

有两个序列 ai,bia_i, b_i 和 01 串 cc,甲乙两人操作。初始 x=0x=0,第 ii 次操作时,如果 ci=0c_i=0,由甲操作,否则由乙操作。每次操作时,玩家可以选择将 xx 异或上 aia_ibib_i。甲希望最小化 xx,乙希望最大化 xx。问最终的 xx 的值。n105,ai,bi<260n\leq 10^5, a_i,b_i< 2^{60}

题解

先将初始值异或上所有 bib_i,然后 aia_i 也异或上 bib_i,这样游戏变成了每个人决定一个 aia_i 是选还是不选。

我们可以归纳证明,“初值到最终值的映射”一定有这样一个形式:

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

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

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

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