ACGO 第7次排位赛题解

写在前面

本次排位赛D题 $\tt{火星背包}$ 测试数据已加强。

非常感谢大家参加本场排位赛！

为了大家更好的参赛体验，本场比赛：

1. 所有题目采用全新的排版风格；

新的排版风格本着更方便参赛选手审题的原则，对“时空限制”，“题目内容”，“数据范围”，“输入输出格式”，等做了重新排版。

• 每道题目，均将时间限制与内存限制放置于题目开头。
• 题目内容中不再在变量后标注数据范围。
• 统一将题目中出现的所有变量的数据范围，归置于 $\tt{数据范围}$ 板块，在题目内容下。
• 对于 $\tt{多组测试用例}$ 的题目在 $\tt{数据范围}$ 板块上方作强调说明。
• 输入格式部分，不再使用生硬，不易理解的文字来说明，而是使用更为直接的 $\tt{数据样式示例}$ 说明。

2. 所有题目判题采用 $\tt{checker(Special\ Judge)}$

• 对于存在多组合法方案的题目，不使用 checker 的题目，往往要求按照一定的顺序（例如字典序）输出，这往往会给解题带来一些不必要的麻烦，亦或是限制了参赛者的解题思路。而 checker 判题，则给了解题代码更大的包容性，输出任意顺序或者满足要求的答案即可。

• 对于答案为浮点数的题目，要求保留若干位小数输出，在不使用 checker 判题的情况下，往往可能会导致一些不必要的精度问题，

• 对于输出 $\tt{Yes}$ 或者 $\tt{No}$ 此类型的题目，使用 cheker 可以忽略解题代码输出答案的大小写，即：你可以选择你喜欢的形式，输出 $\tt{Yes}$ 或者 $\tt{No}$。

3. 所有题目给出样例说明，并尽可能给出较好的样例

• 我们希望题目的 $\tt{样例}$ 和 $\tt{样例说明}$ 拥有让参赛者能够更好理解题目意思的作用，而不是仅仅因为需要有一个样例而存在。（比如本场比赛的 $A$ 题。）

• 我们希望题目给出的样例能够在解题程序出现很大错误的时候是无法得到正确答案的，而不是在提交后发现 $\tt{答案错误}$。（比如本场比赛的 $D$ 题的样例2，如果你采用一般的贪心的错误解法，是无法通过这个样例的。）

• 在不透露题目解题思路的情况下，尽可能给出一个数据略大的样例。（比如本场比赛的 $B, D, F$ 题。）

4. 简洁清晰的题面

• 选手应该具备一定的阅读理解能力，但是我们认为竞赛重心仍然是放在解题上，让每位选手能够读清楚，读懂题目，然后思考问题。而不是故意编造一些和题目关联性很低的故事，或者是在题目中玩 $\tt{文字游戏}$ 埋坑，或者使用一些可能会存在歧义的描述。

• 对于题目中提到的特殊概念如 $\tt{好数组}$，$\tt{好数字}$ 等，做特殊标注并做相应解释；对于题目中的重点信息，使用加粗标注。

总而言之，我们希望大家更好地享受算法竞赛，减少一些其他原因影响解题的情况。

大家如果有其他的建议，欢迎在评论区提出哦～

---

简易题解

详细题解的AC代码包括复杂度分析，请点击题目标题查看。

A - 统计线段上格点的数量

令 $X = \vert x_A - x_B \vert, Y = \vert y_A - y_B \vert$，那么我们可以将题目转化为：求最多可以将 $X$ 和 $Y$ 均分为多少段，使得每段的长度均为整数。

令均分的段数为 $k$，那么我们需要求的结果就是找到一个可以整除 $X$ 和 $Y$ 的最大的 $k$。

也就是 $X$ 和 $Y$ 的最大公约数，即 $\gcd(X, Y)$。

答案即为 $\gcd(X, Y) + 1$。

---

B - 大数求和

对于题目中的式子，我们有 $\sum_{k=1}^{N}k \mod M = N \times (N + 1) / 2 \mod M$。

但是由于本题的 $N (1 \le N \le 10^{4 \times 10^6})$ 非常大，直接计算上面的式子时间复杂度为 $\mathrm{\mathrm{O}}(\log^2{N})$，计算量大概为 $1.6 \times 10^{13}$，会超出时间限制。

我们考虑 $1 + 2 + 3 + \cdots + 2 \times M - 1 + 2 \times M = M \times (2 \times M + 1)$。

而 $M \times (2 \times M + 1) \vert M$，即每 $2 \times M$ 个数字的和对 $M$ 取余的值为 $0$。

令 $K = N \mod (M \times 2)$，我们只需要计算最后的 $K$ 个数字的和即可。

而最后的 $K$ 个数字的形式为 $i \times M \times 2 + 1, i \times M \times 2 + 2, i \times M \times 2 + 3, \cdots + i \times M \times 2 + K$。

每个数字对 $M$ 取余得到 $1 + 2 + 3 + \cdots + K = K \times (K + 1) / 2$。

对于本题 $M(1 \le M \le 10^9), K(0 \le K < M \times 2)$，可以直接做整形运算。

对于 $N$，令其长度为 $n$， 我们可以将其写成 $\sum_{i=0}^{n}a[i] \times 10^i$，其中 $a[i]$ 为其从低位到高位上的数字。那么我们便可以从逐位处理求得 $N \mod (M \times 2)$。

---

C - 黑白方格

使用 $\tt{BFS/DFS}$ 或者 $\tt{并查集}$ 所有不同的连通块进行标记。

统计网格中连通块的数量记为 $k$，白色方格的数量为 $w$。

遍历所有 $\tt{白色}$ 方格，统计每个白色方格周围不同的连通块数量，记为 $c_i$，那么如果将当前方格染为 $\tt{黑色}$，网格上的连通块的数量变为为 $k - c_i + 1$。求出所有的 $k - c_i + 1$，最后的答案为 $\frac{{\sum_{i=1}^{w}{k - c_i + 1}}}{w}$。

---

D - 火星背包

本题的背包的容量，以及物品的大小都非常大，无法使用常规的01背包解法。

另外一方面 $N(1 \le N \le 40)$的范围不支持我们使用”搜索+剪枝“来在时限范围内求解。

但是我们可以把所有矿石分为两个部分，分别求解，最后将两个部分的答案合并。

这种方法叫做 $\tt{折半枚举（meet \ in \ middle）}$。

拆分成两个部分后，每个部分的矿石数量为不超过 $20$，可以在 $\mathrm{O}(2^{N/2}N)$ 的复杂度下求得两部分的答案。

我们可以先预处理前半或者后半部分中的选取方法对应的重量和价值总和记为 $w_1, v_1$。这样在另一部分寻找总重 $w_2 \le M - w_1$ 时使 $v_2$ 最大的选取方法即可。

接下来思考如何从枚举得到的 $(w_2, v_2)$ 集合中高效寻找 $\max\{v_2|w2\le M'\}$ 的方法。

首先，可以排除所有 $w_2[i] \le w[j]$ 并且 $v_2[i] \ge v_2[j]$ 的 $j$。这一点可以通过按照 $w_2, v_2$ 的字典序排序后，处理得到。然后剩余的元素都满足 $w_2[i] < w_2[j] \Leftrightarrow v_2[i] < v_2[j]$，要计算 $\max\{v_2|w2\le M'\}$，只需要找到满足 $w_2[i] \le M'$ 的最大的 $i$ 即可。这一点可以通过二分查找高效实现。

令一半矿石的答案个数为 $M(M \le 2^{N/2})$，一次搜索需要
$\mathrm{O}(\log{M})$ 的时间。这个算法总的时间复杂度为 $\mathrm{O}(2^{N/2}N)$.

---

E - 连通三元组

我们使用 $A_i$ 的二进制位来表示 $i$ 和其他点之间是否有边。

为了方便运算，我们可以只存储编号较小的点到编号较大点的边。

当 $i$ 和 $j$ 固定不变时，满足条件的 $k$ 的个数即 $A_{i,k}=A_{j,k}=1$ 的个数，即 $A_i\ \mathrm{AND}\ A_j$ 中 $1$ 的个数。

因此，我们可以使用 std::bitset 来实现
$A_1,A_2,\dots,A_N$ 并枚举 $(i,j)$ 计算 $A_i\ \mathrm{AND}\ A_j$ 中的 $1$ 个数，总共需要 $\mathrm{O}(\frac{N}{w})$ 时间其中 $w = 64$，因此总的时间复杂度为 $\mathrm{\mathrm{O}}(\frac{N^3}{w})$。

由于 $\frac{3000^3}{64}=421875000 \simeq 4 \times 10^8$ ，这个解法已经足够快了。我们只需枚举 $i,j(i < j)$ 就能进一步将执行时间减半。

---

F - 统计含K个非零数字的整数

考虑 $\bf{数位DP}$。

将数字 $n$ 转化为字符串 $s$ 定义 $f(i, cnt, isLim, isNum)$ 表示构造第 $i$ 位及其之后数位的合法方案数，其余参数含义为：

• $cnt$ 表示前面选择的非零数字的数量。
• $isLim$ 表示当前是否受到了 $n$ 的约束（注意要构造的数字不能超过 $n$）。若为真，则第 $i$ 位填入的数字至多为 $s[i]$，否则可以是 $9$。如果在受到约束的情况下填了 $s[i]$，那么后续填入的数字仍会受到 $n$ 的约束。例如 $n=1234$，那么 $i=0$ 填的是 $1$ 的话，$i=2$ 的这一位至多填 $2$。
• $isNum$ 表示 $i$ 前面的数位是否填了数字。若为假，则当前位可以跳过（不填数字），或者要填入的数字至少为 $1$；若为真，则要填入的数字可以从 $0$ 开始。例如
  $n=123$，在 $i=0$ 时跳过的话，相当于后面要构造的是一个 $99$ 以内的数字了，如果 $i=1$ 不跳过，那么相当于构造一个 $10$ 到 $99$ 的两位数，如果 $i=1$ 跳过，相当于构造的是一个 $9$ 以内的数字。

---