Codeforces Round 1028 (Div. 1) 部分题解
注意
题解写得可能非常抽象。
「如果一个题解你看不懂,那是题解垃圾而不是你垃圾。」
A. Gellyfish and Flaming Peony
题意
有 个正整数 ,你一次操作可以选择 然后 。问最少操作次数使得所有数都相等。
题解
首先不难发现最后所有数都变成 。如果这个数存在,则只需要让不等于这个数的数都变成这个数即可。否则 DP,设 表示使得某个数变成 需要的最少操作次数。。最后把所有数与造出来的这个 取 即可。
B. Gellyfish and Camellia Japonica
题意
有一个长度为 的序列 ,给定多次操作,。给定最终序列,求一个可能的原序列,或判断无解。。
题解
建图。为每次操作得到的新数建点,从 和 当时对应的点向这个点连边。有 个点的值已知(序列的最终状态),要求每个点的值必须要大于等于其出边,因此拓扑排序复原出一个原序列。再做一遍操作,验证是否能得到最终序列。
C. Gellyfish and Eternal Violet
题意
有 个怪物,每个血量为 。给定 ,有一把武器,每一回合:有 的概率这把武器会被附魔,你得知它是否附魔后可以选择是否跳过这个回合,如果不跳过的话,附魔的武器可以(且必须)对所有怪物造成 的伤害,没有附魔的武器可以对一只怪物造成 的伤害。有 个回合,问最优策略下,能把所有怪物的血量都降到恰好为 的概率是多少。。
题解
附魔的武器一定能用就用。整个流程分为两个阶段:首先使用不附魔的武器,把所有怪物的血量降到相同值;然后维持所有怪物血量极差不超过 。第一个阶段,可以计算不附魔攻击的次数,枚举达到这个次数前出现了多少次附魔攻击,相应可以计算概率;第二个阶段,DP,设 表示怪物血量的最小值为 ,有 只怪物血量是 ,还剩 个回合,成功的概率。转移分情况:
- :一定用武器,如果附魔就 ,否则 ;
- :有两种策略:
- 只用附魔的武器;附魔则 ,否则 不变;
- 都用;如果附魔就 ,否则 。
- :只用非附魔的武器;附魔则 不变,否则 。
D. Gellyfish and Forget-Me-Not
题意
有两个序列 和 01 串 ,甲乙两人操作。初始 ,第 次操作时,如果 ,由甲操作,否则由乙操作。每次操作时,玩家可以选择将 异或上 或 。甲希望最小化 ,乙希望最大化 。问最终的 的值。。
题解
先将初始值异或上所有 ,然后 也异或上 ,这样游戏变成了每个人决定一个 是选还是不选。
我们可以归纳证明,“初值到最终值的映射”一定有这样一个形式:
- 我有某个线性基,特别地,每个基都带了一个标志,代表它用来最大化还是最小化答案;
- 给定初值后,从高到低位枚举每个基,按照这个基对应的标志和 的当前位决定是否使用这个基。
我们考虑从后往前枚举每个数,初始基为空,记当前数为 ,从高到底考虑每一位:
- 如果 这一位为 ,那么这个数对于这一位没有影响,继续看线性基中的更低位;
- 如果 这一位为 ,而当前的基中没有这个数,把它加入基中,并且根据 打上标志:这是序列里最后一次让这一位可以自由地异或上 的机会了,当前操作的人一定能利用这个机会来控制最后的答案;
- 如果 这一位为 ,而当前的基中已经有这个数,那么 异或上当前的基中这个数 ,继续看线性基中的更低位:尽管是否异或上 对当前位没有影响,但如果我多异或一次 ,那 也要跟着多异或一次来抵消,相当于我能让更低位异或上 。
上面的过程既是算法流程也是证明。