注意
题解写得可能非常抽象。
「如果一个题解你看不懂,那是题解垃圾而不是你垃圾。」
定义一个长为 2n+1 的正整数序列 a 为好的,当且仅当 a1=a2−a3+a4−⋯+a2n−a2n+1,且 1≤ai≤1018,且 ai 两两不同。给定 2n 个两两不同的数 ai,要加入一个数,重新排列,得到一个好的序列。ai≤109,n≤2×105。
注意到允许的数的范围是 1 到 1018,但输入的数范围是 1 到 109,不难想到添加一个比所有数都大的数以保证两两不同。将所有数排序,大的 n+1 个放在奇数位,小的 n−1 个放在偶数位,空出 a2,按照限制构造即可。
交互题,有 0≤n,m<230 两个整数未知,你一次可以给出整数 x,得到 (x\operatororn)+(x\operatororm) 的值。你可以询问最多两次,随后交互库给出 y,你要输出 (y\operatororn)+(y\operatororm) 的值。
需要判断每一个二进制位上 n 和 m 加起来有多少个 1。查询 (⋯0101010101)2 可以得到第 0,2,⋯ 位的情况、查询 (⋯1010101010)2 可以得到第 1,3,⋯ 位的情况。
对于一个 01
串 s,定义其权值为 max0≤i≤nw(s[0:i])w(s[i:n−1]),其中 w(s[i:j]) 为 s[i:j] 中 1
的个数减去 0
的个数。
给定一个长度为 n 的二进制字符串 s,多次修改,每次翻转一位,查询 s 的所有子序列的权值之和。n≤2×105。
w(s[0:i]) 会从 0 开始,连续变化成 w(s);w(s[0:i])+w(s[i:n−1]) 恒定,因此最大值为 ⌊w(s)/2⌋⌈w(s)/2⌉,只与 w(s) 有关。从而最终答案也只与串的 1
的个数有关。
把 w(s)=k 的子序列的个数的组合数求和列出来,推一推,得到一个组合数,答案即为一个【组合数 × 二次项】求和(奇偶要分别讨论)。可以直接头铁推这个式子,也可以推它的差分(因为一次修改只改一个字符)。
给定一个长为 n 的序列,求其字典序最大的子序列,满足把这个子序列的元素作为边长,能构成一个(非退化的)多边形。n≤2×105,ai≤109。
能构成多边形,当且仅当 maxai≤∑i=1nai−maxai。假设我们已经确定最大值是 x,我们从左往右扫所有小于等于 x 的数,维护一个栈,如果当前数比栈顶大且弹出栈顶后剩下的数仍然足以构成多边形,则弹出栈顶。
下面我们证明:字典序最大的答案里面,最大值只可能是整个序列中最大的 logV+O(1) 个数:考虑取出若干个数,要满足其任意子集都无法构成多边形,用的值最小的方案为 1,1,2,4,8,⋯;因此只要取出最大的 logV+O(1) 个数就一定可以找到它的一个子集构成多边形;而如果最大值比这些数还小,字典序肯定不会大于上述的解。
复杂度 O(nlogV)。
有一个长为 n 的纸带,初始每个格子深度是 0;你一次操作可以将其折叠若干次、再在一个地方滴一滴墨水、使得其对应的所有格子的深度加 1。设 f(b) 为达成 b 这个深度序列的最小操作次数。给定 a,求所有 a 的子段的 f 之和。n≤2×105,ai≤109。
先考虑单个序列的求解。一次操作可以选择若干个奇偶性交替的格子,将其颜色加一。我们扫过整个序列,维护 e,o 表示上次最近一次点在偶数/奇数格子上的操作的数量;以当前格子是偶数为例,o←max(0,o−ai),e\gete+k。最后答案是 e+o。注意到整个过程中 e,o 是独立的,因此可以分别做一遍,把答案加起来。于是问题变成了:不断操作 o←max(0,o+a~i),求最后的结果。
考虑如何对所有子段求求和。分治,考虑 [l,r] 内跨过中点 m 的子段;我们在递归左侧时,得到 [i,m] 的所有答案的集合;接着扫右侧,不断会有新的数会被减到零,维护曾被减到零的数的个数、它们现在的值、以及没被减到零的数都加上了多少;从而可以对于每个右端点求和,扫到 r 后得到的集合自然返回到上一层。