跳至主要內容

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

Wallbreaker5th大约 5 分钟OI×ICPCOI×ICPCCodeforcesOI×ICPC - 题解OI×ICPC - 构造OI×ICPC - 贪心OI×ICPC - 交互题OI×ICPC - 位运算OI×ICPC - 组合数OI×ICPC - 贪心OI×ICPC - 栈OI×ICPC - 分治

注意

题解写得可能非常抽象。

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

A. Breach of Faith

题意

定义一个长为 2n+12n+1 的正整数序列 aa 为好的,当且仅当 a1=a2a3+a4+a2na2n+1a_1 = a_2 - a_3 + a_4 - \cdots + a_{2n} - a_{2n+1},且 1ai10181\leq a_i\leq 10^{18},且 aia_i 两两不同。给定 2n2n 个两两不同的数 aia_i,要加入一个数,重新排列,得到一个好的序列。ai109,n2×105a_i\leq 10^9,n\leq 2 \times 10^5

题解

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

B. Finding OR Sum

题意

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

题解

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

C. Binary Subsequence Value Sum

题意

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

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

题解

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

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

D. Maximum Polygon

题意

给定一个长为 nn 的序列,求其字典序最大的子序列,满足把这个子序列的元素作为边长,能构成一个(非退化的)多边形。n2×105,ai109n\leq 2\times 10^5, a_i\leq 10^9

题解

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

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

复杂度 O(nlogV)O(n\log V)

E. Another Folding Strip

题意

有一个长为 nn 的纸带,初始每个格子深度是 00;你一次操作可以将其折叠若干次、再在一个地方滴一滴墨水、使得其对应的所有格子的深度加 11。设 f(b)f(b) 为达成 bb 这个深度序列的最小操作次数。给定 aa,求所有 aa 的子段的 ff 之和。n2×105n\leq 2\times 10^5ai109a_i\leq 10^9

题解

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

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