退役后复健趣题

· · 休闲·娱乐

配套题单

写在前面

AClove 不喜欢也不擅长做传统题，AClove 喜欢且擅长做趣题。

AClove 在 NOI2024 中凭借趣题拿下 D 类银牌。

AClove 在 NOI2025 中被传统题撞飞了，拿下铜牌，遗憾离场。

AClove 退役不再打 OI 了，但 AClove 还是很喜欢趣题。

这是 AClove 退役后的趣题复健题单，AClove 希望能给那些一直埋没在传统题的题海中却还是想要体验趣题乐趣的选手一些快乐。

功利地说，希望每一个喜欢且擅长趣题的选手都能在自己最重要的比赛里遇见能够改变自己 OI 生涯的趣题；不功利地说，希望每一个选手都能从趣题中汲取到一些自己初学 OI 时感受到的那种最原始的快乐。

以上。

P13320 Equal Sums

题目链接

测试点 1：直接枚举所有子集判断有没有两个不同子集的和相同即可，复杂度 O(n2^n)。

测试点 2：

考虑 n = 500，如果我们要从中选出 k 个数，那么有 {500 \choose k} 种选择。

我们每次随机取 $6$ 个数求和，直到出现重复的和为止即可。 这样做为什么不会 TLE？ $k = 6$ 的子集有 $2 \times 10 ^ {13}$ 个，我们从中选择 $x$ 个，选择的方案数有 ${2 \times 10^{13} \choose x}$ 种。 我们先假设所有 $k = 6$ 的子集和在 $[6, 6 \times 10 ^{12}]$ 范围内是均匀随机分布的，此时每个数的期望出现次数大概是 $\dfrac{10}{3}$。 那么不重复的选择方案就有 ${6 \times 10^{12} \choose x} \times (\dfrac{10}{3})^x$ 这么多种。 当 $x$ 足够大时，下面的方案数与上面的方案数的比值会几乎等于 $0$，也就是说不重复的选择方案几乎占所有选择方案的 $0\%$，那么这个时候选到的方案里就基本确定会有重复的了。 这个结论是建立在假设子集和均匀随机分布的基础上的。但实际上子集和并不一定均匀随机分布，那么这个结论还正确吗？ 我们发现：均匀随机分布时不重复的选择方案数一定大于非均匀随机分布时不重复的选择方案数。为什么？ 不会严谨证明，来一个不太严谨的证明： 设所有会出现的数构成了集合 $T$，其中每个数的出现次数为 $y_i$，不重复的选择方案数为： $${|T| \choose x} \times \prod_{i \in T}y_i$$ 我们知道 $\sum_{i \in T}y_i$ 是个固定值，根据基础不等式，显然所有 $y_i$ 相等时 $\prod_{i \in T}y_i$ 最大。也就是说：对于所有出现次数不为 $0$ 的数，当它们的出现次数全部相等时，方案数最多。 另外感性理解，如果所有出现次数不为 $0$ 的数出现次数都相等的话，显然 $|T|$ 越大选择时越不容易重复，也就是不重复的方案数越多。 根据这两条结论：所有出现次数不为 $0$ 的数出现次数相等时方案数最多；当所有出现次数不为 $0$ 的数出现次数都相等时，$|T|$ 最大时方案数最多。我们发现：这不就是均匀随机分布时的情况嘛。所以均匀随机分布时不重复的方案数最多，非均匀随机分布只会使不重复的方案数减少。 分母不变分子减少，那么概率只减不增，换言之就是选到重复的概率只会增大，所以不需要考虑这种情况了。 最终的 $x$ 的应该不会大于 $2 \times 10^7$。 ## P12797 Hot and Cold [题目链接](https://www.luogu.com.cn/problem/P12797) 首先考虑如果我们知道每个单词是什么含义，这时该怎么做。 先从一维的情况开始考虑，不难发现可以二分。 在当前区域内，每次取中点和中点右面的点，如果得到的回复是“Closer”说明在中点右面，反之则在中点左面。 一个维度的二分次数为 $2 \times \log_210^6$，是 $40$ 次。对两个维度分别做二分，需要的次数是 $80$。 这样做是对的，但超过了 $64$。原因是我们对两个维度分别做二分，对一个维度二分时会浪费另一个维度的信息。我们考虑对两个维度同时做二分。 取平面中点，再取中点上方的点，如果回复“Closer”说明宝藏在中点上方，反之在中点下方。然后取中点右上方的点，如果回复“Closer”说明在中点右侧，反之则在中点左侧。 这样做只需要取 $3$ 个点就对两个维度同时进行了二分。最后需要的次数是 $60$，小于 $64$ 次，非常成功。 现在我们并不知道每个单词是什么含义，我们考虑如何知道。 带感叹号的一定是“Found!”，第一个出现的一定是“Not Found”。我们只需要区分“Closer”“Further”和“At the same distance”即可。 取 $(0, 0)$ 作为第一个点，取 $(1, 1)$ 作为第二个点，这时得到的回复要么是“Closer”要么是“At the same distance”。 然后我们再取回 $(0, 0)$，如果得到的回复和刚才不同，那么刚才的回复是“Closer”，现在的回复是“Further”，那个没出现的回复就是“At the same distance”。这时用了 $3$ 次询问，加上刚才的 $60$ 次，总共 $63$ 次，没有超过 $64$。 如果相同的话，说明这个回复是“At the same distance”，那么宝藏一定在 $(0, 1)$ 或 $(1, 0)$ 的位置，分别询问即可。 ## P12541 Hack! [题目链接](https://www.luogu.com.cn/problem/P12541) APIO 场上写了一个 77 分做法，离正解一步之遥。因为 APIO 没打好，这道题一直都没补，现在来补题了。 考虑二分，判断区间 $[l, r]$ 内是否存在 $n$ 的倍数。 取 $0$ 和 $[l, r]$ 的所有数，如果返回值不为 $0$ 说明有，反之则没有。 （注意：题目要求 $x_i \ge 1$ 我们是取不到 $0$ 的，但我们只要对所有数全局加一，这时候取 $1$ 就相当于取到 $0$ 了） 这样做需要的次数为 $O(V)$，太大了，考虑优化。 不难想到我们不需要取 $[l, r]$ 区间内所有的数。我们可以先确定一个数 $v$，接下来取 $[0, v - 1]$ 的所有数，然后在 $[l, r]$ 区间内每 $v$ 个数取一个数即可。这样我们取的数个数就是 $O(v + \dfrac{r - l + 1}{v})$ 级别的。 显然当 $v = \sqrt{r - l + 1}$ 时最优，$V = 10^9$ 时次数约为 $1.5 \times 10^5$，也是我的赛时做法，拿到了 77 分（实现好一些能拿到 78 分）。 想要拿到 100 分需要更进一步的优化。 考虑刚才的做法，发现当 $V = 5 \times 10^8$ 时次数约为 $10^5$，比题目要求的 $1.1 \times 10^5$ 要小。因此我们考虑将 $V$ 的范围折半。 这里有很多种做法，举两种： 第一种是按照大小折半。显然对于 $[1, 5 \times 10^8]$ 区间内的所有数，它一定至少有一个倍数在 $[5 \times 10^8 + 1, 10^9]$ 区间内。因此我们直接对 $[5 \times 10^8 + 1, 10^9]$ 区间二分，最后得到 $n$ 之后枚举 $n$ 的所有因数即可。 第二种是按照奇偶折半。考虑将所有奇数乘上 $2^{30}$ 次方，然后直接对所有奇数进行二分。最后将得到的这个奇数乘上若干个 $2$ 得到真正的 $n$。 应该是我在正式比赛中距离场切黑题最近的一次，如果这道题放在 NOI2025 或许我就真的创造奇迹了。 ## P10539 魔术表演 [题目链接](https://www.luogu.com.cn/problem/P10539) APIO2024，忆昔当年泪不干。 这个题的解决思路有两种，一种是保存完整的信息不要让信息被删干净，另一种是保存一些有效信息通过删除后剩余的有效信息还原原数。 第一个思路的一种可行做法为 $k$ 进制拆分，先对 $X$ 拆位，每一位连向代表 $0 \sim k - 1$ 的点，多连几遍。随机删点的情况下正确率非常高。 但交互库可能会采取某种特殊策略删点，比如删除某个点连出去的所有边之类的。这样就有很大的可能会丢失信息。 多做几次随机置换能降低丢失信息的概率，最后能不能过比较吃运气。 由这个做法可以延伸到第二个思路的类似做法：我们对 $X$ 做多次 $k$ 进制拆分，每次取不同的 $k$。最后就算删除了相当一部分信息，我们仍然能从剩余的信息里还原出原来的 $X$。 这个做法可行但很麻烦，考虑一个更简单的做法。 把 $k + 1$ 连向 $X \bmod k + 1$，最后 exCRT 还原一下即可（实际上直接暴力还原复杂度也是对的）。 设保留下来的边里的更大的数为 $x_i$，那么最后一定能还原出一个小于所有 $x - 1$ 的最小公倍数的解。 我们只要保证这个最小公倍数大于 $10^{18}$ 即可，为了保证正确性，要把 $n$ 取大一点。