XJOI 省选训练 6

xza

OI

Water Distribution

https://www.cnblogs.com/yuanquming/p/11508861.html

E 题

Modern Painting

https://www.cnblogs.com/penth/p/10263903.html

注: 以上两题均选自 AtCoder CODE FESTIVAL, 该系列比赛的题目质量较高,有兴趣的同学可以尝试去多做做.

Xor Sum

建议参考官方题解.

问题需要求的是 “最大值最小”，可以想到二分答案 $V$，变成判定性问题。

XOR 运算的每一位是独立的，由此我们先独立地考虑每一位。假设第 $i$ 位有 $c_i \ (c_i\le n)$ 个数为 $1$，那么 $X$ 变成限制所有 $c_i$ 的奇偶性。

设 $b_i$ 为 $(S-X)/2$ 的第 $i$ 位（如果 $S<X$ 或 $S-X$ 是奇数先特判），可以发现 $c_i = 2 b_i + x_i$ 是一组合法的初始解。同时，所有的解可以通过不断操作 「$c_i$ 减二，$c_{i-1}$ 加四」来得到。

加下来的方向可能也只有按数位从高到低 DP 了。有了 $V$ 的限制之后，我们让状态的第二维为「当前有多少个 $a_i$ 未卡到 $V$ 的上界」，称其为 “自由位”。设 $f(i,j)$ 为：当前考虑第 $i$ 位，有 $j$ 个 $a_i$ 卡到上界，最少需要多少进位（也即当前位操作数量）。可以做到关于 $n$ 和 $\log V$ 的多项式复杂度。

考虑缩小 $j$ 的状态数量。一个重要的性质是，如果「当前 $V_i$ 是 $1$，自由位的数量至少为 $3$，同时不需要进位」，那么 $V$ 一定可行。这是因为 $c_i$ 的初始解 $\le 3$，一旦有 $3$ 个数成为自由位，可以令后面的其他位都是 $0$，由这 $3$ 个数字自由调整。

设之前退下来的位加上当前的初始解为 $w$，也即当前位需要的 $1$ 的个数（可以继续往后退）。如果当前 $V_i$ 为 $0$，那么只能继续往后退。接下来，如果 $w \le n$ 并且 $\min(n-w+j,n) \ge 3$，直接返回 true（由前一段所述）。否则继续枚举 $k$，表示新的自由位个数。继续观察可以发现一个更重要的性质：当 $k\ge 5$ 的时候，如果 $k-j \ge 2$ 显然是更不优的（由于奇偶性的限制，$2$ 到 $4$ 的转移是必要的），当 $j$ 足够大的时候，我们最优化的目标只有 需要的进位最少。

所以需要考虑的 $j$ 的上界只有 $5 + \log S$... 由此我们得到了一个 $O(\log^3S)$ 的做法。