你牛大了 | Gavin's Blog

2026/7/27 NOI D1

考虑树的性质：连通、无环。推一下就会发现合法的情况当且仅当只有相交。在值域上从左到右考虑区间，记录当前左端点的最大值 $l_{\max}$ 以及右端点的次大和最大值 $r1$ 和 $r2$ ，则一个新区间 $[l,r]$ 合法当且仅当 $r1 < l \leq r2$ 。

再加上目前选的区间数量，我们就有了一个四维的状态。优化 dp 可以从状态或转移入手，这里显然着手优化状态。容易发现， $l_{\max}$ 一定对应着 $r1$ 和 $r2$ 中的一个，所以只需要维护 $l_{\max}$ 对应的下标以及另一个 $r$ 就可以了，状态降到三维。

转移是简单的，复杂度 $O(nmk)$ 。

感性理解一下，如果距离近的直接过去就行，否则需要靠传送。理性分析一下，传送门的效果是一定的，所以如果在一个点选择了往前走，后面的点也一定只会往前走了。再理性分析一下，这个选择的情况一定有一个阈值，在终点的一个邻域内都靠走，外面的都靠传送门。

比较暴力的想法是，列出一个不等式并二分到最小可能的值。这个好像是双 log 的，不可以过。更进一步地，我们发现这个答案不超过根号，好像也过不了。哦你邻域向外拓展一格的变化量最多为 $1$ ，那你就不用二分了，挂个点分树不是做完了？

D1 唯一一道本质交互题，感觉考验乱搞能力。

如果钦定答案在集合 $S$ 里，直接查询集合就可以知道答案了。核心思想是先尽量缩小答案候选集合 $S$ ，最后直接问 $S$ 。

你先考虑随几个序列，每次找到其中区分度最好的（等价类），有 $72$ 分。记忆化一下，有 $88$ 分。

我们的目的是找到区分度最好的序列，于是你可以构造几种方案：

随机
放一些因数多的
保持相邻两个数差为 $B + r$ ，其中 $B = \frac{m}{len}$ ， $r$ 是 $O(1)$ 级别，对于每个数随机取一个，使得相邻两个数不互质的概率大大提升
直接从 $S$ 里取一些数
取一个连续的素数区间

把这五种按比例随机，区分度很好，然后就做完了。