Codeforces Round 830

补题

Source

Codeforces Round 830

A - Bestie

注意到 $\gcd(n, n + 1) = 1, \forall n\in\mathbb{N}$，因此我们一定可以通过对第 $n - 1$ 项和第 $n$ 项进行操作从而使 $\gcd(a_{n - 1}, a_n) = 1$

答案至多是 $1 + 2 = 3$，需考虑仅对 $a_{n - 1}$ 或 $a_n$ 进行操作和初始 $\gcd_{i = 1}^na_i = 1$ 的情况

Code

1732 A

B - Ugu

从 B 开始，我的 Solution 和官方的 Tutorial 就有很大差别了（

考虑 DP

注意到被反转偶数次等于未被反转，因而记录反转次数状态只需要记录 $0, 1$ 两种

令 $f(i, j, k)$ 表示前缀 $s_{1\dots i}$ 被改造为合法的，且以 $j = 0, 1$ 为结尾、算上该次（可能没进行的）对后缀 $s_{i\dots n}$ 反转的反转次数为 $k = 0, 1$ 的最小代价

转移显然，就是容易搞错情况，因为有些状态是不可能的（为什么？）

Code

1732 B

C1 - Sheikh (Easy version)

记 $s$ 为异或和

注意到，任何正整数对和的贡献恒大于等于对异或和的贡献。形式化地，$x\geq |s - (s\oplus x)|$。因而我们只会去删掉那些贡献相等的数，否则一定会使 $f$ 变小。而 $f$ 值一定是 $\text{sum}(l, r) - \text{xor}(l, r)$

注意到丢掉的 $a_i$ 会对异或和有影响，因而 two-pointers 扫描

具体而言，先确定左边删去个数最多的情况，然后不断减少左边删去的个数从而使右边删去的个数相应增加。综合所有情况取最值

Code

1732 C1

C2 - Sheikh (Hard version)

记 $s$ 为异或和

回到异或运算的性质上来。我们发现，满足条件的 $x$，即满足 $x = s - s\oplus x$ 的 $x$，其二进制表示中的位和 $s$ 相应的位一定相同

那么缩小 $[l, r]$ 的过程，可以视作将 $s$ 中为 $1$ 的位不断删去，且 $s$ 能删去某些 $1$ 的位当且仅当 $x$ 的二进制表示如此

最坏情况是待删除的 $x_{(2)}$ 为 $1, 10, 100, 1000, \cdots$ 且 $s_{(2)} = 111\cdots$，而 $\log_2 10^9\le 31$，故复杂度实际上还是 $O(n)$ 只是常数 31 比较感人

不过 TLE 了，原因在于 $x = 0$ 的情况。一堆 $0$ 会使复杂度变成 $O(n^2)$，去掉 $0$ 即可。这个过程与离散化微妙地相似

Code

1732 C2

D1 - Balance (Easy version)

大暴力，过的人比 C1 还多就离谱

记 $f(k)$ 为所求，将 $f$ 存下来，以后再求 $k$ 就能从 $f(k)$ 开始找了

Code

1732 D1