2023.7 好题记录

Aleph_Drawer · 2023-07-04 16:47:36 · 题解

0 前言

设立这个记录的初衷是为了整理一些非常有趣的题目思路。

这非常有助于提高思维能力。

同时，也分享给其他人，这样也可以给别人提供一个借鉴和参考。同时给自己额外的一点动力去写题。

出于某些原因，这里并不会收录校内模拟赛的题目，除非有可以在公开 OJ 上获取的渠道。

前缀 P 表示洛谷的题目。

1 题目

CF1817D Toy Machine

非常奇怪的一道题。没有太多思维含量，全部都是乱搞。

题目提供了模拟器，可以手玩一下。根据往魔方公式上的奇怪联想，或者是足够多次的手玩之后可以发现，LDRU 可以让最左边的方块从第一个变成第二个。以此类推，我们可以将前 \dfrac {n -1}2 个玩具通过类似于置换的方式调到最前面，然后最后 L 一下即可。

很自然的想到对后 \dfrac {n - 1}2 个玩具进行对称操作 RDLU，然后更自然的想到正确的方法应该是把我们需要的玩具调到最末尾的位置，然后再把这个玩具操作到前 \dfrac {n - 1} 2 个玩具中，然后再用 LDRU 操作到想要的位置。

最开始想到的是 RDRULU，发现不太行，最后实在想不下去了忍不住看了题解，正解是先用 RDRU 全部收纳到右半边，然后再 LU 一下，目标方块就到了中间的位置。然后接着做就可以了。

ARC163D Sum of GCC

很有趣的题目。

直接做是比较困难的，考虑转化问题然后再计数。

先考虑一个满足条件的图，我们假设原图中的 GCC 集合为 S = \{s_1, s_2, ..., s_k\}，我们发现，|S| + 1 等于对原图做如下操作的方案数：

将图中的点分成 A,B 两个集合，使得 A, B 集合之间的每一条边都是从 A 集合出发到 B 集合。

注：集合可以为空。

为什么？我们发现，对于任意的 0 \leq i \leq k，我们可以把 \{s_1, s_2, ..., s_i\} 划入 A 集合，而剩下的可以划入 B 集合。请特别注意，s_i 并没有特定的指明是哪一个强连通分量。出现在这里的意义仅仅是代表数量。

很容易证明这样是可以满足构造方法的。不然，要么就是你 SCC 找错了，要不然就是有别的方法去划分。

而且这样的划分方法仅有一种。

所以我们就把问题转化成了划分集合的方案数。

不妨设 f_{i,j,k} := 当前考虑了 i 个点，其中有 j 个加入了 A 集合，共有 k 条从小到大的边。

转移只需要枚举第 i + 1 个点是加入哪个集合，算一下组合数，就可以解决了。

最后的答案就是动态规划出来的答案，减去符合题目要求的图的总数，即 \large C_{\frac{n \times (n - 1)}2}^m。

CF442C Artem and Array

刚开始肯定是手玩一下。发现一个数很难做到计数多次，除非是类似于山谷的方式排列，比如 \{2,3,1,3,2\}。这样中间的 1 就可以被计数到两次。

然而这种情况我们发现，这种情况肯定不是最优的，以上面为例，我完全可以把中间的 1 先删掉，得到 \{2,3,3,2\} 的计数方法，然后再拿两个 2 的贡献，但是另一种只能拿到一个 2 的贡献，而只能拿到两个 1 的贡献。

这个数字也可以表示相对大小关系，我们发现价值 \{1,1,2\} 是绝对小于 \{2,2,3\} 的。

这让我们同时得到了两个非常有用的结论：

形如 a_{i - 1} \geq a_i \leq a_{i+ 1} 把中间的 a_i 拿掉肯定不会更劣；

在满足上面条件的情况下，每个数最多被计入一次。

然后我们发现，处理掉所有的多余的 a_i 我们发现剩下的序列就形如一个山峰了。

然后接下来就是乱搞了。

我们随便举一个例子 \{1,3,4,6,7,9,8,5,3,1\}。

显然的 9 是不可能取得到的，8 也是。

然而 7 是可以取到的，7 肯定与 8,9 挨在一起，无论是哪一个，取中间的就好了。

然后我们发现按照这样的方法我们可以直接把剩下的全部恰好取一遍，结合上面的结论这就是最好的方案了。

那么这道题目就做完了。实现可以直接使用双向链表，由于不是珂朵莉，写起来还是很方便的。

P8883 幻想中成为原神

~~（为什么我会找到这道题目）~~

妙妙 MO 题。难度低了，似乎题目作者高估了这个公式的熟知程度。

~~毕竟 小吴同学wtc 没有秒掉的题目都是紫色及以上的。~~

题目给你了一个很大的误差，那么我们或许可以通过计算密度来得到答案。

那么先计算概率。正难则反，考虑不含平方因子的概率。

这里有一个误区，可能很多人认为概率是 \prod_{n \geq 2} 1 - n^{-2}，然而这并不是正确的。因为可能会存在重复计算的情况。

事实上，对于任何的合数，都会被其质数重复计算，所以概率应当是 \prod_{p} 1 - p^{-2}。

接下来考虑欧拉乘积公式的一个版本（这里同时出现了黎曼 \zeta 函数，可以概括调和级数，巴塞尔问题，黎曼猜想和（错误的）自然数之和等于 -\dfrac 1{12} 的函数，感兴趣可以去了解一下）：

\zeta(s) = \sum_n \dfrac 1{n^s} = \prod_p (1 - p^{-s})^{-1}

注：通用版本如下，对于 f(nm) = f(n)f(m) 且 f(1) = 1 的函数，有

\sum_n f(n) = \prod_p(1 - f(p))^{-1}

当 f(n) = n^{-s} 即取得上式。

接下来我们考虑如何证明这个公式。

我们学习过素数筛法，这里我们借用一下思想，考虑用这种方法来证明。

x = \sum_{n} f(n) = f(1) + f(2) + \cdots

f(2) x = f(2) + f(4) + f(6) + \cdots

相减得到

(1 - f(2))x = f(1) + f(3) + \cdots

这样就完成了一次操作。再演示一次：

y = (1 - f(2))x

f(3)y = f(3) + f(9) + f(15) + \cdots

相减得到

(1 - f(2))(1 - f(3))x = f(1) +f(5) + f(7) + \cdots

将所有素数都做一遍，右边就剩下了 f(1) = 1，稍微转化一下就可以得到上述式子。

回到原问题，我们可以将概率转化为 \dfrac{1}{\sum_n \dfrac 1{n^2}}。

下面那个我们很熟悉了，是 \dfrac {\pi^2}{6}。这就是巴塞尔问题，仍然很推荐看 3Blue1Brown 的视频。

所以最后这道题的答案就是 n \cdot (1 - \dfrac 6{\pi^2})。误差在控制范围内。

P9405 Komunikacja międzyplanetarn

非常有趣的题目！~~（又是 MO）~~

小吴同学wtc 与 2020wjn 稳定发挥，1A 秒了这题。

这题的难度在于神秘却十分优美的转化上面。首先，根据部分分的提示，我们可以想到将二维的平面距离求和转移到一维上面。我们在平面上画一条 y = \tan \theta \cdot x 的直线，然后在选定一个点 (x,y)。我们尝试将这个点映射到直线上，然后我们在这条直线上面计算完所有距离，最后我们除以 \cos 值，然后就可以得到结果了。

具体的计算过程，我们可以先上图，然后再解释：

令 A 的坐标为 (x,y)，那么 |OC| = x, |DC| = \tan \gamma \cdot x, |AD| = y - \tan \gamma \cdot x。

接下来是一个初中数学小 trick，八字模型，\angle DAB = \angle DOC = \gamma，所以进一步的，|BD| = \sin \gamma (y - \tan \gamma \cdot x)。

而 |AD| = \dfrac x{\cos \gamma}。

所以我们想要的 |OB| = \dfrac x{\cos \gamma} + y \cdot \sin \gamma - \sin \gamma \tan \gamma \cdot x。

由于 \tan \gamma = \dfrac{\sin \gamma}{\cos \gamma}，所以上式化简为 y \cdot \sin \gamma - x \cdot \dfrac {\sin^2 \gamma - 1}{\cos \gamma}。又因为 \sin^2 \gamma + \cos^2 \gamma = 1，所以最后化简为 y \cdot \sin \gamma + x \cdot \cos \gamma。这就是我们想要的东西了。

现在，我们可以随手画出一条经过原点的直线，然后就可以立刻得到 |OB| 的长度了。

然而，对于不同的线段，由于其夹角不同，所以要乘上的系数也不同，如果我们想要画一条线段就解决问题，这是不可能的。

这种情况下，有一个非常有趣的降维打击方法，这来源于一个想法：

如果我把 \gamma 值全部取一遍，最后再除以一个数，是不是可以得到值？

这的确是一个非常妙的想法，夹角与 \gamma 是一个一次函数关系，而且当 0 \leq \gamma \leq \pi 的时候，夹角的值是与 \gamma 一一对应的。然而，这就意味着，我们不得不引入更高级的积分概念。

我们想象一个线段，它的长度是 l。然后现在已经画好了一条直线，l 与直线的顺时针夹角为 \alpha(0 \leq \alpha \leq \pi)。

那么我们要求的就是

\int_0^{\pi} l \cdot |\cos \alpha| \text{ d}\alpha

把 l 提取出来，就是

l \cdot \int_0^\pi |\cos \alpha| \text{ d}\alpha

绝对值看上去太别扭，按照性质拆成

2l \cdot \int_{0}^{\pi / 2} \cos \alpha \text { d}\alpha

此时答案就已经很明了了，但是我还是想多拆几步，令 f(x) = \cos \alpha，显然 F(x) = \sin \alpha + C。

然后就是 2l (F(\dfrac \pi 2) - F(0)) = 2l。

所以那个我们要除去的数就是 2。

接下来，正解就很明了了。我们把这个积分划成多段，然后分部求数值积分。对于每一段的积分，我们枚举 \alpha，按照要求算出所有映射的点，简单排序一下，然后用前缀和优化一下计算即可。

时间复杂度是 O(n \log n \cdot k)。其中 k 是你将积分分成的部分数量。

P4003 无限之环

思维没有达到黑题的水平，很大程度上是靠其复杂的建图堆积出来的。

看到网格图，首先不难想到黑白染色，然后白点连接源点，黑点连接汇点。

我们不妨将一个点拆成 5 个点，分别代表四个方向和中心点，我们管边缘的叫做 ”方向点“（”上点“，”下点“，诸如此类）

我们先把相邻格子的相邻方向点连接起来。判断是否有答案就很简单了，如果最大流的数量是所有管子接口数量的 \dfrac 12 就是全部连通的，否则就不是了。接下来，问题就只剩下每个格子的方向点怎么连接了，连接好之后跑一边最小费用最大流即可。

显然，首先初始状态肯定是中心点与方向点间连接一条费用为 0 的边。然后，如果我们旋转改变了接口，肯定是从一个方向点连接到另一个方向点，费用为消耗的旋转次数。

以上右拐角形为例，肯定是中间与上点，右点先连接费用为 0 的边，然后再将左右与上下连接费用为 1 的边。

为什么这样是对的？可以自行模拟一下，不同的方向需要消耗的代价是否跟题意是符合的。

剩下的情况就类似，直接推即可。

CF406E Hamming Triples

首先我们不难想到将这个 01 序列进行排序以及编号。观察到如果进行特定顺序的排序，那么我们可以做到相邻的序列的 H 只相差 1。

具体的，假设 n = 3，那么我将其排序如下：

000, 001, 011, 111, 110, 100

接下来，我们按照输入对它进行编号，以 001, 011, 110 为例，就编号为 2,3,5。

此时 H(a,b) 就可以很方便的表示了。这样，我们便可以挖掘更多的性质。

我们不妨用偏几何的方法来表示。我们可以在一个正 2n 边形上面研究性质。

不难发现应该有两种情况。

首先是第一种：所有的点都集中在一个长度不超过 n 的区间当中。

那么此时可以找到这些点的两个 “端点”。如果我们设这两个端点的值为 a,b，那么 2H(a,b) 就是能够达到的最大值。方案数是比较好求的，我们假设有 x 个 a，y 个 b，那么方案数就是

(m-x-y)xy + \dfrac {x(x-1)y + y(y - 1)x}2

其中，前半部分是选择 a,b 然后再选择中间的一个其他值的方案数，而另外部分则是选择两个 a 一个 b 和两个 b 一个 a 的方案数。

然后是第二种：就是其他的情况。

这种情况下，最大值是 2n。你可以在正多边形上画出一个类似于三角形的东西，这个东西是横跨所有节点的，所以最大值是 2n。

这种情况下的求值也好办：我们对这三个点没有太大的要求，只要他们不同时在一个长度小于 n 的区间里面即可。

所以我们再次运用组合数知识。我们将所有可能的选取方法，减去选取三个同时在一个长度小于 n 的区间的方法。

可以使用双指针扫描一遍 O(m) 的解决。

C_m^3 - \sum_i C_{[l,r]}^3

由于两种讨论方法都只需要 O(m) 的扫描时间，而排序需要的时间是 O(m \log m)。

所以时间复杂度是 O(m \log m)。

不过还请特别注意一个细节，在某些实现方式下，当所有序列的值全部一样时，会进入死循环，这时需要特殊判断。