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

注意

题解写得可能非常抽象。

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

A. Breach of Faith

题意

定义一个长为 $2n+1$ 的正整数序列 $a$ 为好的，当且仅当 $a_1 = a_2 - a_3 + a_4 - \cdots + a_{2n} - a_{2n+1}$，且 $1\leq a_i\leq 10^{18}$，且 $a_i$ 两两不同。给定 $2n$ 个两两不同的数 $a_i$，要加入一个数，重新排列，得到一个好的序列。$a_i\leq 10^9,n\leq 2 \times 10^5$。

题解

注意到允许的数的范围是 $1$ 到 $10^{18}$，但输入的数范围是 $1$ 到 $10^9$，不难想到添加一个比所有数都大的数以保证两两不同。将所有数排序，大的 $n+1$ 个放在奇数位，小的 $n-1$ 个放在偶数位，空出 $a_2$，按照限制构造即可。

B. Finding OR Sum

题意

交互题，有 $0\leq n,m< 2^{30}$ 两个整数未知，你一次可以给出整数 $x$，得到 $(x \operator{or} n) + (x \operator{or} m)$ 的值。你可以询问最多两次，随后交互库给出 $y$，你要输出 $(y \operator{or} n) + (y \operator{or} m)$ 的值。

题解

需要判断每一个二进制位上 $n$ 和 $m$ 加起来有多少个 $1$。查询 $(\cdots 0101010101)_2$ 可以得到第 $0,2,\cdots$ 位的情况、查询 $(\cdots 1010101010)_2$ 可以得到第 $1,3,\cdots$ 位的情况。

C. Binary Subsequence Value Sum

题意

对于一个 01 串 $s$，定义其权值为 $\max_{0\leq i\leq n} w(s[0:i]) w(s[i:n-1])$，其中 $w(s[i:j])$ 为 $s[i:j]$ 中 1 的个数减去 0 的个数。

给定一个长度为 $n$ 的二进制字符串 $s$，多次修改，每次翻转一位，查询 $s$ 的所有子序列的权值之和。$n\leq 2\times 10^5$。

题解

$w(s[0:i])$ 会从 $0$ 开始，连续变化成 $w(s)$；$w(s[0:i]) + w(s[i:n-1])$ 恒定，因此最大值为 $\lfloor w(s)/2 \rfloor \lceil w(s)/2 \rceil$，只与 $w(s)$ 有关。从而最终答案也只与串的 1 的个数有关。

把 $w(s)=k$ 的子序列的个数的组合数求和列出来，推一推，得到一个组合数，答案即为一个【组合数 × 二次项】求和（奇偶要分别讨论）。可以直接头铁推这个式子，也可以推它的差分（因为一次修改只改一个字符）。

D. Maximum Polygon

题意

给定一个长为 $n$ 的序列，求其字典序最大的子序列，满足把这个子序列的元素作为边长，能构成一个（非退化的）多边形。$n\leq 2\times 10^5, a_i\leq 10^9$。

题解

能构成多边形，当且仅当 $\max a_i\leq \sum_{i=1}^{n} a_i - \max a_i$。假设我们已经确定最大值是 $x$，我们从左往右扫所有小于等于 $x$ 的数，维护一个栈，如果当前数比栈顶大且弹出栈顶后剩下的数仍然足以构成多边形，则弹出栈顶。

下面我们证明：字典序最大的答案里面，最大值只可能是整个序列中最大的 $\log V + O(1)$ 个数：考虑取出若干个数，要满足其任意子集都无法构成多边形，用的值最小的方案为 $1,1,2,4,8,\cdots$；因此只要取出最大的 $\log V + O(1)$ 个数就一定可以找到它的一个子集构成多边形；而如果最大值比这些数还小，字典序肯定不会大于上述的解。

复杂度 $O(n\log V)$。

E. Another Folding Strip

题意

有一个长为 $n$ 的纸带，初始每个格子深度是 $0$；你一次操作可以将其折叠若干次、再在一个地方滴一滴墨水、使得其对应的所有格子的深度加 $1$。设 $f(b)$ 为达成 $b$ 这个深度序列的最小操作次数。给定 $a$，求所有 $a$ 的子段的 $f$ 之和。$n\leq 2\times 10^5$，$a_i\leq 10^9$。

题解

先考虑单个序列的求解。一次操作可以选择若干个奇偶性交替的格子，将其颜色加一。我们扫过整个序列，维护 $e,o$ 表示上次最近一次点在偶数/奇数格子上的操作的数量；以当前格子是偶数为例，$o\gets \max(0, o-a_i), e\get e+k$。最后答案是 $e+o$。注意到整个过程中 $e,o$ 是独立的，因此可以分别做一遍，把答案加起来。于是问题变成了：不断操作 $o\gets \max(0, o+\tilde a_i)$，求最后的结果。

考虑如何对所有子段求求和。分治，考虑 $[l,r]$ 内跨过中点 $m$ 的子段；我们在递归左侧时，得到 $[i,m]$ 的所有答案的集合；接着扫右侧，不断会有新的数会被减到零，维护曾被减到零的数的个数、它们现在的值、以及没被减到零的数都加上了多少；从而可以对于每个右端点求和，扫到 $r$ 后得到的集合自然返回到上一层。