Codeforces Round 838

不！能！再！摆！了！

Source

Codeforces Round 838

A - Divide and Conquer

对于每个数，计算一下如果一直对其进行右移一位的操作，奇偶性变化所需的最小次数。如果 $\sum a_i$ 为奇的话，取最小的即可

Code

1762 A

B - Make Array Good

审题！！！

题目中 $x\leq a_i$ 的条件暗示我们可以这样构造：每个数变为最小的不小于它的 2 的某次幂

Code

1762 B

C - Binary Strings are Fun

首先观察序列中 $\mathtt{01}$ 的转折点 $s_i \neq s_{i - 1}, i>1$。对于前缀 $s[1, i]$ 一定有 $\mathtt 0$ 的个数与 $\mathtt 1$ 的个数仅相差 1

这样一来，最后一个转折点之前的 extension 其实是确定的：

• 非转折部分一定形如 $\mathtt{010101}$，否则不可能在之后产生转折
• 转折点部分一定形如 $\mathtt{101101}$，刚好仍使 $\mathtt 0$ 和 $\mathtt 1$ 个数相差 1

这样，$f(s) = 2^{l-1}$ ，其中 $l$ 指仅含相同元素的后缀长度

注意别直接左移，会爆

Code

1762 C

Warnings

• 别想当然，返回值在函数末尾还是要补一句的。没返回值在 Windows 下可能没问题，Linux 下直接爆炸
• 审题审题审题
• 注意位运算会爆 long long，还是老老实实用快速幂