目录
- 总结
- 各题题解
- D
- E
- F
- G
- H
总结
-
C
- 知识点：分类讨论；（错读的题意：二分答案）
- 易错点：读题（idea：将题意错读为“使得所有元素互不相同”，似乎也是可以做的?）
-
D
- 知识点：位运算代码基础；位运算的集合意义；字典序的定义；找规律；贪心；
-
E
- 知识点：条件和问题的对称性转换；贪心；
- 易错点：\(\lceil\frac{a}{b}\rceil\) 在
C++的表达是(a + b - 1) / b
-
F
- 知识点：考虑特殊情况（树）；分层图/二分图/最短路树；
- 易错点：实现细节（见下）
-
G
- 知识点：两个曼哈顿距离几乎确定一个点；“找直径”的类似思路
-
H
- 知识点：
lowbit的性质；和式拆分；扫描线思想；
- 知识点：
各题题解
D
题意：给出 \([[0, 2^n - 1 ]]\) 的一个排列，在让 \(\sum_i \operatorname {popcount}(p_0\&p_1\&\cdots \&p_i)\) 最大的前提下，\((p_0, p_1, \cdots )\) 的字典序最小
- 记 \(s_i = p_0 \& p_1 \& \cdots \& p_i\)，记 \(s_{-1} = 2^n - 1\)，则（看作集合的二进制表示）有 \(s_i \subseteq s_{i-1}\)
- 假设已经确定了前 \(i\) 个数，则剩下的数可以分为两类：令它为 \(p_{i+1}\) 后，使得 \(s_{i + 1} = s_i\) 的数，和使得 \(s_{i+1} < s_i\) 的数
- 第一类数是 \(s_i\) 补集的子集，因此在未来（确定 $p_{i+2},p_{i+3},\cdots $ 的时候）永远都是第一类数
- 由此可以证明，策略是：优先填第一类数，在没有第一类数的时候，填使得 \(|s_i|\) 减小 1 的数。这样就能保证最大性。
- 在这个基础上选最小合法的数就可以满足字典序最小
- D code
E
题意：判断是否存在满足 \(a_i + b_i \ge p_i, \sum a_i = x, \sum b_i = y, [a_i < b_i] = s_i\) 的非负整数解 \(a_i, b_i\)
- 考虑问题：\(a_i, b_i\) 的相对大小关系照旧，\(a_i + b_i = p_i, \sum a_i \le x, \sum b_i \le y\)
- 注意到 \(\sum a_i = \sum p_i - \sum b_i\)，问题可以转化为规划 \(b_i\) s.t. \(\sum p_i - x \le \sum b_i \le y\)；而 \(b_i \in \begin{cases} [0, \lfloor \frac{p_i - 1}{2} \rfloor] & s_i = 0 \\ [\lceil \frac{p_i + 1}{2} \rceil , p_i] & s_i = 1 \end{cases}\)
- 这个问题有解的充要条件是：\(\sum p_i \le x + y\)，以及 \(b_i\) 取值上下界的和在 \(\sum b_i\) 的合法区间内
- 容易验证以上条件是原问题的必要条件
- 如果同时存在 \(s_i = 0, 1\) 的元素时，容易证明这些条件也是充分条件
- 而当 \(s_i\) 全部为 0 或者 1 时，以 \(s_i \equiv 1\) 为例，下面说明只需要再加入条件 \(x + n \le y\)（该条件的必要性显然），得到的就是充分条件：
- 首先求一组转化后的问题的解 \(a_i', b_i'\)。显然 \(\sum a_i' + n \le \sum b_i'\)。下面从这组解出发构造一组原问题的解。
- 下面让 \(\sum b_i' - \sum a_i' = y - x\)：
- 当\(\sum b_i' - \sum a_i' < y - x\)
- 策略：任取一个 \(b_i'\) 把它增大为 \(b_i + y - x\)
- 在策略中，\(a_i'\) 不变，\(b_i'\) 不变或者增大，不会破坏 \(a_i' < b_i', a_i' + b_i' \ge p_i\) 的性质。
- \(a_i'\) 没有变化故 \(\sum a_i' \le x\) 成立；这意味着 \(\sum a_i' - x \le 0\)，由 \(\sum b_i' = y + (\sum a_i'- x)\) 知 \(\sum b_i' \le y\) 也成立
- 当 \(\sum b_i' - \sum a_i' > y - x \ge n\)
- 策略：此时 \(\sum b_i' - \sum a_i' \ge n + 1\)，必然存在 \(i\) s.t. \(a_i' + 1 < b_i'\)，我们修改 \(a_i'\) 为 \(a_i' + 1\)。重复这一过程直到 \(\sum b_i' - \sum a_i' = y - x\)。
- 在策略中，\(b_i'\) 不变，\(a_i'\) 不变或者增大，不会破坏 \(a_i' + b_i' \ge p_i\) 的性质。
- \(a_i' < b_i'\) 由修改的 \(i\) 满足 \(a_i' + 1 < b_i'\) 来保证。
- \(b_i'\) 没有被修改，与上一种情况同理可证 \(\sum a_i' \le x, \sum b_i' \le y\) 都成立。
- 当\(\sum b_i' - \sum a_i' < y - x\)
- 最后，任意选取一个 \(j\)，记 \(t = x - \sum a_i' = y - \sum b_i'\)（\(\sum b_i' - \sum a_i' = y - x\) 保证了后一个等号成立），然后修改 \(a_j', b_j'\) 为 \(a_j' + t, b_j' + t\)，即可让 \(\sum a_i' = x, \sum b_i' = y\)
- E code
F
题意：给二分图的顶点染色，然后在只知道顶点邻居的数量和颜色的情况下，选择一个“到 \(1\) 的距离更小”的邻居
- 如果图是树：以 1 为根，按照某个顺序循环给每一层染色，根据邻居中没有出现的颜色推断自己的颜色，根据自己的颜色确定距离根更近的是什么颜色。
- 考虑将这个想法推广到图：
- 取从 1 出发的最短路树（到儿子的最短路经过父亲），复刻上述的染色方法
- 边不带权，由最短路的性质知，有边相连的顶点要么在相邻层，要么在同一层
- 可以归纳证明同一层的点在二分图的同一侧，故而所有有边相连的顶点都在相邻的层、不在同一层
- 据此可以套用树的方法判断距离根更近的是什么颜色
- 实现细节
- 最短路图中的点可能没有后继节点，体现为点的所有邻居都是同一个颜色。在程序中不要把这种情况漏掉了。
- F code
G
题意：点 \(1\sim n^2\) 编号，\(n \times n\) 的棋盘上每个格子恰好有一个点，询问至多 \(3n^2 + 150\) 次“编号为 \(i,j\) 的顶点之间的曼哈顿距离”，还原棋盘（使得曼哈顿距离和询问答案一致即可）。\(n \le 100\)。
- 找对角线两端点：随意取一个点，找它的最远点 \(A\)，再找 \(A\) 的最远点 \(B\)。则 \(A,B\) 是某个对角线的两端点，开销为 \(2n^2\)，并且已知所有顶点到 \(B\) 的距离
- 找另一个对角线的端点：与 \(B\) 距离为 \(n - 1\) 的顶点就是另一个对角线上的点（共 \(n\) 个），任取其中一点，则这个对角线上离它最远的点一定是对角线的端点，记为 \(C\)。开销为 \(n\)
- 再花费 \(n^2\) 的开销给出每个点到 \(C\) 的距离。在已知点到 \(A,C\) 的距离的情况下可以确定顶点的位置
- G code
H
题意：lowbit(i) 表示 \(i\) 的二进制最低位的值（是 2 的整数幂次），操作为“给出 \(l,r\)，对于所有 \(i \in [[l, r]]\)，执行 w[i] += (i-l+1) * lowbit(i-l+1)”。初始w[i]=0，共 \(q\) 次操作，问操作完之后的 w[i]。\(n, q \le 2 \cdot 10^5\)
- lowbit 的性质：\(\operatorname{lowbit}(x) = 2^j \Leftrightarrow x \equiv 0 \pmod {2^{j}} \wedge x \not\equiv 0 \pmod {2^{j + 1}}\)
- 和式拆分：
（i+1-l)*lowbit(i-l+1) => (i+1)*lowbit(i-l+1) - l*lowbit(i-l+1)。枚举 \(\operatorname{lowbit}(i - l + 1)\) 的取值 \(2^j\)（只有 \(\log n\) 种），我们需要对所有 \(i, j\) 求出 \(\operatorname{lowbit}(i-l+1) = 2^j\) 的所有 \(l\) 的个数与和。 - 扫描线的方法可以对每个 \(i\) 给出“满足 \(i \in [l, r]\) 的所有询问的 \(l\) 构成的集合”
- 进一步考察：\(i - l + 1 \equiv 0 \pmod {2^j} \Leftrightarrow (i+1) \equiv l \pmod{2^j}\)，所以对于 \(l \bmod 2^j\) 的每种取值维护 \(l\) 的个数与和，就可以对每个 \(i\) 给出满足 \((i-l+1) \equiv 0 \pmod{2^j}\) 的所有 \(l\) 的个数与和。对 \(j, j+1\) 的结果做差，即可得到满足 \(\operatorname{lowbit}(i-l+1) = 2^j\) 的所有 \(l\) 的个数与和。
- H code