构造题 题解

· · 题解

出题人闲话

这题本来是 T3，但是由于【数据删除】我们降低了整场比赛的难度，所以这题被放在了 T4。我比较菜，如果你觉得这题太水了或者质量很差请不要喷我，谢谢。

这道题原先有非形式化题意，但是太啰嗦了所以最后只保留了形式化题意。温馨提示部分比较长，主要是怕大家因为没用过 checker 或者不会 linux 命令而无法得分，所以大致讲了一下用法。其实如果要省事，我完全可以不下发 checker，而是让选手自己实现，毕竟 checker 写个拓扑排序就没了，对吧。

本题 p = 75000 的限制可能还是比较松，也许随机化或者其他方法能做得更好。如果你爆标了或者有其他不错的做法，欢迎你与我分享。

Sol 1（期望得分 15）

直接模仿样例的方式暴力构造。这种方法只能构造出 0 \sim 22。我在样例里直接给出了这种构造方法，主要是因为这确实很简单，我也希望更多的人这题能得分。

Sol 2（期望得分 50 \sim 55）

使用二进制方法进行构造。这种方法没有充分利用边数，只能构造出 0 \sim 4000。将下方的点也连接到 24 号点可以通过 0 \sim 6000，可能是极限了。

Sol 3（期望得分 70 \sim 85）

使用三进制方法进行构造。下图虽然可以覆盖所有数字，但是边数过多了，因此不得不舍弃一些点缩减边数，应该可以构造出 0 \sim 15000（较差的实现）或者 0 \sim 45000（较好的实现）。

Sol 4（期望得分 85 \sim 100）

我们将每个点视作一个一维递推数组 f（初值 f_{1} = 1），将每一条有向边视作递推中的一次转移，那么显然从 1 号点到 i 号点的路径数即为 f_{i} 的值。我们可以通过 f 序列前 23 项递推构造若干数字，然后全部向 24 号点建边，每次构造的时候前 23 个点构成的子图完全保留，再将剩下汇入 24 号点的边部分保留得到我们想要的路径数。

由于边数不足 3 倍点数，故猜测主干中每个点的入度不超过 2 是较为合理的。为了充分利用，我们考虑斐波那契数列式构造（下图中需要使用了 66 条边，比题目要求多了一条，我们稍后再进行优化）：

根据斐波那契数列递推公式 f_{1} = f_{2} = 1, f_{i} = f_{i-2} + f_{i-1} (i \geq 3)，我们按照上图方式连接 43 条边即可让编号 1 \sim 23 的点分别提供斐波那契数列前 23 项的值。

有重要结论：斐波那契数列前 n 项的和为第 n + 2 项的值减去 1。考虑使用归纳法证明。显然 n = 1 时成立，于是尝试将结论 n 推广到 n + 1。由 \sum\limits_{i=1}^{n}f_{i} = f_{n+2} - 1 可知 \sum\limits_{i=1}^{n+1}f_{i} = \sum\limits_{i=1}^{n}f_{i} + f_{n+1} = f_{n+2} + f_{n+1} - 1 = f_{n+3} - 1，证毕。

注意到 75000 接近斐波那契数列第 25 项的值（f_{25} = 75025），因此前 23 项选取部分求和可以提供 0 \sim 75000 中的所有数值。（补充：每次贪心地取还能取的最大的项即可）

上述构造方案多了一条边，直接使用的话意味着不得不缩减一个点腾出可用边导致只能构造 0 \sim 45000，但其实我们可以直接移除 1 \rightarrow 24 的边。这样做仅仅会导致我们无法构造 75024，但是显然我们并不需要构造这个值。因此，优化后即可通过此题。