比赛链接
- QOJ 链接
题解完成情况
| A | B | C | D | E | F | G | H | I | J | K | L | M |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| \(\Box\) | \(\Box\) | \(\Box\) | 待补 | 待补 | 待补 | \(\Box\) | 待补 | \(\Box\) | \(\Box\) |
H 是个论文题。
L. Z-曲线 (Z-order Curve)
点击查看题意简述
给定二维 Z 形曲线的一个有向片段 \(L \to R\)（构造方法请参见原题），求第一次出现该片段的位置。
数据范围：多测，\(1 \leq L, R \leq 10^{18}\)。
直观上看，只需将所给有向片段不断左移、上移，直至无法移动。此时已经可以直接模拟这个过程。
进一步的，观察题中给出的图，不难发现，能够左移、上移的片段 \(L \to R\)，二者的最高位的所在位置必然相同；否则，该片段必然无法移动。所以，只需从高到低考虑二者的二进制位，如果 \(L, R\) 的这一位不一致，立刻停止。否则，将 \(L, R\) 的这一位都变成 \(0\)，继续考虑低一位即可。代码。
M. 拒绝采样 (Rejection Sampling)
点击查看题意简述
集合 \(N = \{1, 2, \cdots, n\}\)，数字 \(i\) 有一个正整数权值 \(a_i\)。你现在有一个拒绝采样器，其工作方式如下：给定正整数 \(k\) 和 \(n\) 个在 \([0, 1]\) 内的参数 \(p_1, \cdots, p_n\)：
(1). 初始化集合 \(T \gets \varnothing\)。
(2). 对每个 \(i \in N\)：以 \(p_i\) 的概率将 \(i\) 加入 \(T\)。
(3). 如果 \(|T| = k\)，返回 \(T\)。否则回到 (1).。
现在，给定 \(n, k\) 和 \(a_i\)，找到参数 \(p_1, \cdots, p_n\) 使得：
- \(\sum_{i = 1}^{n} p_i = k\)
- 对于 \(N\) 的任意 \(k\) 元子集 \(S\)，该拒绝采样器返回 \(S\) 的概率正比于 \(S\) 中元素权值的乘积。
数据范围：\(2 \leq n \leq 10^5\)，\(1 \leq k \leq n-1\)，\(1 \leq a_i \leq 10^9\)。
自然的，对于某 \(k\) 元集合 \(S\)，拒绝采样器返回它的概率正比于在 (2). 中选中 \(S\) 的概率，也就是：
对于任意 \(i \in N, j \in N, i \neq j\)，取 \(k\) 元集合 \(S\) 使得 \(i \in S, j \not \in S\)，再令 \(S' = S \cup \{j\} - \{i\}\)，那么根据题目要求：
作商得到
该关系对任意 \(i, j\) 都需要成立，因此可以推得：参数 \(p_1, \cdots, p_n\) 满足题述要求当且仅当对诸 \(i \in N\) 皆有 \(\frac{p_i}{1-p_i} \propto a_i\)。
不妨设 \(\frac{p_i}{1-p_i} = c a_i\)，变形可得 \(p_i = \frac{c a_i}{1 + c a_i}\)。显然 \(p_i\) 随 \(c\) 单增，二分出 \(c\) 即可。时间复杂度 \(O(n \log (n \max a_i))\)。
需要注意二分精度需要取到 \(10^{-15}\) 级别，这里我使用了题解的方法，二分 \(\log c\) 来逃课减少二分次数。代码。
B. 滚动石子 (Rolling Stones)
点击查看题意简述
在边长为 \(n\) 的正三角形棋盘（图示请参照原题）上滚动一个边长为 \(1\) 的正四面体骰子，骰子一开始的状态固定，起点固定，要求每个每滚到一个格子，这个格子上的数必须和骰子此时底面的数相同。给定终点，问至少要滚动几次。
数据范围：\(n \leq 100\)。
模拟骰子滚动的过程不难发现，当骰子到达滚到一个固定的格子的时候，此时骰子底面上的数是确定的。而且这个规律很简单，记最上方的格子是 \((0, 0)\)，之后每一行的格子都是 \(0\)-indexed，那么骰子滚到 \((i, j)\) 时的底面数字是：
据此容易判断哪些位置是没法滚到的。现在问题就转化成了：一个棋盘，上面有一些没法走的格子，给定起终点，问最少要走多少次？使用 BFS 解决这个问题即可，时间复杂度 \(O(n^2)\)。
注意不要思维定势，可以往上走的，因为这个挂了一次。代码。
F. 无尽循环 (Infinite Loop)
C. 中点 (Middle Point)
点击查看题意简述
给定矩形的四个顶点 \((0, 0), (0, B), (A, 0), (A, B)\)，每次操作中你可以选择两个点，如果这两个点的中点是整点，则可以作出这个中点，要求通过尽量少的次数作出整点 \((X, Y)\)，给出方案或者报告无解。
先来看我们能构造出什么样的点，尝试后不难发现，\(k\) 次操作内能够做出来的点集为：
但给出构造方法在场上是杀人诛心的，这题构造方法不少，但选错了方法写起来会很烦。
比较高妙的做法是，注意到：我们将 \(P_{k-1}\) 中的所有点分别和初始的四个点作中点，最终构成的点的集合恰是 \(P_k\)，这在直观上看是显然的：将 \(P_{k-1}\) 中的所有点和 \((0, 0)\) 做中点，相当于把 \(P_{k - 1}\) 这一块的点向左下“拉伸”，所得的点的集合恰好是 \(P_k\) 中左下半区的点，剩下部分同理。
现已知 \((X, Y) \in P_k\)，判断 \((X, Y)\) 在整个矩形内的位置，倒序执行上述过程即可：如果 \((X, Y)\) 在整个矩形的左下半区，那么我们认为 \((X, Y)\) 是 \((0, 0)\) 和 \((2X, 2Y)\) 作中点得到的，且 \((2X, 2Y) \in P_{k-1}\)，不断倒推即可，时间复杂度 \(O(\log \max(A, B))\)。
代码。
G. 配对 (Same Sum)
点击查看题意简述
现有 \(n\) 个数，你需要进行若干次区间加操作，并回答形如“是否能将该区间内所有数配成和相等的数对？”的询问。\(n, q \leq 2 \times 10^5\)。
代码。
K. 土豆兄弟 (Brotato)
A. A + B = C 问题 (A + B = C Problem)
点击查看题意简述
构造三个最小正周期分别是 \(pA, pB, pC\) 的 01 串 \(A, B, C\)，使得 \(A \oplus B = C\)，或者报告无解。
数据范围：\(1 \leq pA, pB, pC \leq 10^6\)。
可以通过大量尝试完成此题，但挺烦的。
因为 \(A \oplus B = C\)，所以必须要有 \(pC | \operatorname{lcm}(pA, pB)\)。而 \(A \oplus B = C\) 同时说明 \(C \oplus B = A, C \oplus A = B\)，所以同样需要有 \(pA | \operatorname{lcm}(pB, pC)\)、\(pB | \operatorname{lcm}(pA, pC)\)。暂时找不到其它限制了，考虑在这个限制下先构造。
不妨设 \(pA \leq pB \leq pC\) 且 \(g = \gcd(pA, pB, pC) = 1\)。若 \(g \neq 1\)，我们只需找到 \((pA/g, pB/g, pC/g)\) 的一组解，再将该解中的所有 \(\mathtt{0}\) 替换为 \(\underbrace{\mathtt{0 \cdots 0}}_{g}\)，所有 \(\mathtt{1}\) 替换为 \(\underbrace{\mathtt{1 \cdots 1}}_{g}\) 即可得到 \((pA, pB, pC)\) 的一组解。
但如上想法会在 \(pC = \operatorname{lcm}(pA, pB)\) 时出现问题，我们先处理掉这个边界情况：
- 倘若 \(pA = pB = pC\)，对 \(pA\) 分类讨论：
- \(pA = 1\) 时，有解 \(A = B = \mathtt{1}\)，\(C = \mathtt{0}\)。
- \(pA = 2\) 时，不难发现无解。
- \(pA \geq 3\) 时，有解 \(A = \underbrace{\mathtt{0 \cdots 0}}_{pA - 2} \mathtt{01}\)，\(B = \underbrace{\mathtt{0 \cdots 0}}_{pB - 2} \mathtt{10}\)，\(C = \underbrace{\mathtt{0 \cdots 0}}_{pC - 2} \mathtt{11}\)。
- 否则，必须有 \(pA < pB \leq pC\)。可以考虑选取：\(A = \underbrace{\mathtt{0 \cdots 0}}_{pA - 1} \mathtt{1}\)，\(B = \underbrace{\mathtt{0 \cdots 0}}_{pB - 1} \mathtt{1}\)，\(C\) 是 \(A^{\infty} \oplus B^{\infty}\) 的最短周期串。
接下来我们证明，这个构造符合题目要求。
证明. 待证其实等价于：对集合
\[S = \{x | (x \bmod pA = 0) \oplus (x \bmod pB = 0) = \mathbf{TRUE}\} \]若正整数 \(T\) 满足 \(\forall x, x \in S \iff x + T \in S\)，则 \(T \geq pC\)。
显然 \(0 \not\in S\)，那么对于任意整数 \(n\)，\(n \cdot pA \cdot T \not\in S\)。而 \(n \cdot pA \cdot T \bmod pA = 0\)，于是必须有 \(n \cdot pA \cdot T \bmod pB = 0\)。同理，对任意整数 \(m\)，必有 \(m \cdot pB \cdot T \bmod pA = 0\)。于是：\[\forall n, m \in \mathbb{N}, pC | (n \cdot pA - m \cdot pB) \cdot T \]根据 Bezout 定理，存在 \(n, m\) 使得 \((n \cdot pA - m \cdot pB) = \gcd(pA, pB)\)。于是可以得到 \(pC | \gcd(pA, pB) \cdot T\)。而根据假设 \(\gcd(\gcd(pA, pB), pC) = 1\)，所以须有 \(pC | T\)。
另一方面，容易验证 \(pC\) 是符合要求的。所以 \(A^{\infty} \oplus B^{\infty}\) 的最短周期是 \(pC\)。\(\Box\)
记总周期 \(L = \operatorname{lcm}(pA, pB, pC)\)，串 \(A, B, C\) 的在总周期的重复次数分别是 \(a = L / pA\)，\(b = L / pB\)，\(c = L / pC\)。考虑上面的限制有什么用，可以发现：
同理可得 \(\gcd(a, c) = \gcd(b, c) = 1\)，于是 \(a, b, c\) 两两互质。于是立刻可以得到 \(L\) 是 \(abc\) 的倍数，而因为 \(g = 1\)，不难验证只能有 \(L = abc\)，\((pA, pB, pC) = (bc, ac, ab)\)。
根据中国剩余定理，映射 \(f: \mathbb{Z}_{abc} \to \mathbb{Z}_{a} \times \mathbb{Z}_{b} \times \mathbb{Z}_{c}, f(t) = (t \bmod a, t \bmod b, t \bmod c)\) 是一个双射，而且我们可以只用 \((t \bmod a, t \bmod b)\) 还原出 \(t \bmod ab\)，于是，原题转变成：对诸 \((i, j, k) \in \mathbb{Z}_{a} \times \mathbb{Z}_{b} \times \mathbb{Z}_{c}\)，皆有：
固定 \(j, k\) 变动 \(i\)，此时我们希望 \(B_{(i, k)} \oplus C_{(i, j)}\) 是一个定值。直觉上来看，我们希望 \(i\) 对 \(B, C\) 的影响能够相互“抵消”。通过这个直觉，可以考虑如下形式的构造：记 \(I\)、\(J\)、\(K\) 分别是长度为 \(a, b, c\) 的 01 串，并令：
容易验证，该构造能够使得上述限制恒成立。
接下来，我们选取合适的 \(I, J, K\)，以让 \(A, B, C\) 的最短周期一定是 \(pA, pB, pC\)。而根据上文的证明，我们立刻可以发现，取 \(I = \underbrace{\mathtt{0 \cdots 0}}_{a - 1} \mathtt{1}\)，\(J = \underbrace{\mathtt{0 \cdots 0}}_{b - 1} \mathtt{1}\)，\(K = \underbrace{\mathtt{0 \cdots 0}}_{c - 1} \mathtt{1}\)，即可使得 \(A, B, C\) 的最短周期分别是 \(bc, ac, ab\)。
据此，我们完全解决了本题。代码。
J. 力争和谐 (Balance in All Things)
点击查看题意简述
某锦标赛有 \(k\) 轮，共有 \(2n\) 个人参加。初始时每个人的积分都是 \(0\)。每一轮中，你需要将 \(2n\) 个人配成 \(n\) 对，每一对中分数高的人 -1 分，分数低的人 +1 分，如果分数一样，那么编号小的人 +1 分，编号大的人 +1 分。问：有多少种配对方案，使得每个人分数的绝对值时刻不超过 \(3\)？答案对质数 \(P\) 取模。
数据范围：\(n \leq 400, k \leq 20\)。
本题的算法框架是容易的。可以发现，在偶数轮的时候，每个人的分数只会在 \(\{-2, 0, 2\}\) 内，这一部分的状态数是 \(O(n)\) 的，因为 \(-2\) 分的人数惟一确定了这个状态。在奇数轮的时候，每个人的分数只可能取 \(\{-3, -1, 1, 3\}\)，这一部分的状态数是 \(O(n^2)\) 的。所以，我们对所有状态进行编码，并对于任意两个状态 \(A, B\)，预处理出能把状态 \(A\) 转为状态 \(B\) 的配对方案数 \(g_{A, B}\)，那么我们记 \(f_{i, A}\) 表示在第 \(i\) 轮、目前在状态 \(A\) 的可能方案数，转移为：\(f_{i, A} = \sum_{B 是第 i - 1 轮的合法状态} g_{B, A} f_{i - 1, B}\)，答案即为 \(\sum_{B 是第 k 轮的合法状态} f_{k, B}\)。这个 DP 的复杂度是 \(O(kn^3)\) 的。
现在，我们只需要预处理 \(g_{A, B}\)。分奇数轮 \(\to\) 偶数轮，偶数轮 \(\to\) 奇数轮两种情况进行处理。下文中，我们记 \(A = (a = \#(-2), x = \#(0), a = \#(2))\) 为一个偶数轮的状态，\(B = (y = \#(-3), b = \#(-1), c = \#(1), z = \#(3))\) 为一个奇数轮的状态。
先考虑偶数轮 \(A\) \(\to\) 奇数轮 \(B\) 的情况。此时，我们能确定的匹配是：\(-3\) 分的人只能由两个 \(-2\) 分的人对战得到，\(3\) 分的人只能由两个 \(2\) 分的人对战得到。所以，我们先预先拿出 \(2y\) 个 \(-2\) 分、\(2z\) 个 \(2\) 分配对。此时可以发现，无论如何匹配剩下的人，最终都能得到正确数量的 \(-1\) 分、\(1\) 分的人，只需要求将剩下的人进行匹配的方案数。
问题转化为：现有 \(i\) 个 \(-2\) 分的人，\(j\) 个 \(0\) 分的人，\(k\) 个 \(2\) 分的人，要求：\(-2\) 分、\(2\) 分的人之间不能配对，求合法的配对方案数 \(p(i, j, k)\)。为了防止重复计数，我们强行规定匹配的顺序：先匹配 \(0\) 分和 \(2\) 分的人，再把 \(-2\) 分的人和其余人进行匹配。具体来说：
- 初始化：\(p(0, 0, 0) = 1\)。
- \(2\) 分的人之间无法匹配，\(p(0, 0, k) = 0\)。
- 接下来，考虑 \(0\) 分的人的匹配，若当前正在考虑第 \(j\) 个 \(0\) 分的人：
- 若 \(j \geq 2\)，我们可以从前 \(j - 1\) 个 \(0\) 分的人中选出一个，和当前这个人匹配，转移：\((j - 1) \cdot p(0, j - 2, k) \to p(0, j, k)\)。
- 若 \(k \geq 1\)，我们可以从前 \(k\) 个 \(2\) 分的人中选出一个，和当前这个人匹配，转移：\(k \cdot p(0, j - 1, k - 1) \to p(0, j, k)\)。
- 接下来，考虑 \(-2\) 分的人的匹配，若当前正在考虑第 \(i\) 个 \(-2\) 分的人：
- 若 \(j \geq 1\)，我们可以从前 \(j\) 个 \(0\) 分的人中选出一个，和当前这个人匹配，转移：\(j \cdot p(i - 1, j - 1, k) \to p(i, j, k)\)。
- 若 \(k \geq 1\)，我们可以从前 \(k\) 个 \(2\) 分的人中选出一个，和当前这个人匹配，转移：\(k \cdot p(i - 1, j, k - 1) \to p(i, j, k)\)。
那么，能使偶数轮状态 \(A = (a = \#(-2), x = \#(0), a = \#(2))\) 变为奇数轮状态 \(B = (y = \#(-3), b = \#(-1), c = \#(1), z = \#(3))\) 的配对方案数是：
再考虑奇数轮 \(B\) \(\to\) 偶数轮 \(A\) 的情况。此时效仿上述做法就会发生一些问题，至少，此时 \(p\) 会有自由的四维，计算 \(p\) 的复杂度无法接受。
怎么办呢？还是考虑我们能确定什么。此时，\(-3\) 分的人必须全部变成 \(-2\) 分，而剩下 \(-2\) 分的人必须由 \(-1\) 分的人得到。所以，我们知道，必须恰有 \((a - y)\) 个 \(-1\) 分的人，和其余 \(-1\) 分的人或者 \(-3\) 分的人配对。同理，必须恰有 \((a - z)\) 个 \(1\) 分的人，和其余 \(1\) 分的人或者 \(3\) 分的人配对。
如果我们确定了上述两种情况的配对方案，那么，我们还没考虑到的配对方案必然形如一个负分的人和一个正分的人匹配。而且不难发现，此时剩余的正分的人和负分的人必然相等。所以，对于这一部分人，我们可以随意的将负分的人和正分的人匹配，没有其他限制。于是，如果我们能求出：现有 \(i\) 个 \(-1\) 分的人、\(j\) 个 \(-3\) 分的人，它们内部进行 \(k\) 次匹配的方案数 \(q(i, j, k)\)，那么计算可得（\(1\) 分与 \(3\) 分的情况是对称的）：
接下来考虑求解 \(q(i, j, k)\)：
- 首先考虑 \(-3\) 分的人的匹配，显然，\(-3\) 分的人之间不能匹配，于是 \(q(0, j, 0) = 1\)，否则 \(q(0, j, k) = 0\)。
- 接着，考虑 \(-1\) 分的人的匹配，若当前正在考虑第 \(i\) 个 \(-1\) 分的人：
- 首先，我们可以留着这个人，让他和正分的人匹配，转移：\(q(i - 1, j, k) \to q(i, j, k)\)。
- 如果 \(i \geq 2\) 且 \(k \geq 1\)，我们可以从前 \(i - 1\) 个 \(-1\) 分的人中选出一个，和当前这个人匹配，转移：\((i - 1) \cdot p(i - 2, j, k - 1) \to p(i, j, k)\)。
- 如果 \(j \geq 1\) 且 \(k \geq 1\)，我们可以从前 \(j\) 个 \(-3\) 分的人中选出一个，和当前这个人匹配，转移：\(j \cdot p(i - 1, j - 1, k - 1) \to p(i, j, k)\)。
据此本题解决。实现时，需要对预处理时各维度的范围进行严格限制，否则可能会 TLE/MLE。代码。