NOI 2026 题解

· · 生活·游记

Day 0

认真背诵题库。

几个小提示：

Day 1

T1

阅读题面，感受一下，这是一只毛毛虫。--3min

那就不难了，dp_{i,j,k} 表示较长的右端点在 i，较短的右端点在 j，选了 k 个的方案数。转移要么较短的向前移动一个到 dp_{i,j+1,k}，要么拼一个 [j+1,x] 的区间，复杂度 O(nmk)。这题有一些细节，例如你需要在 i=j 的时候结算，因此你需要考虑通过 j+1 转移到 i=j+1 以及 i=x 的情况。另外，还需要注意只选了两个一样的区间的情况。--8min

T2

阅读题面，感受一下，发现距离近的直接去，否则就传送。--5min

因此可以将问题转化对于每个点求这个距离 d。--5min

推推式子，假设领域内有 cnt 个点，距离和为 sum，传送点的答案为 C，则 C=1+\frac{(n-cnt)C+sum}{n}，解得 C=\frac{n+sum}{cnt}，我们希望 C<d+1，并求出最小的 d。--9min

一看就是二分啊，两只 \log，有点难过。--9min

推推式子发现答案不超过 O(\sqrt n)，但是根号也过不去。--13min

由于树上领域相邻的 +1 即可覆盖另一个的全部，因此相邻位不超过 1？好像是合理的。哦有更容易理解的方式，因为如果相差超过 1 那么直接走到那个点，最后再走一步过去就行了。--17min

这个二分变成不必要的了，直接暴力从父亲答案 -1 开始向后枚举即可，时间复杂度 O(n\log n)，需要写一个点分树。--20min

T3

阅读题面，感受一下，这都能做？--7min

有点像百万富翁，考虑一些启发式做法。--8min

部分分有什么提示性？第一个包是简单的，怎么质数看上去就有点困难了？先思考质数。--12min

考虑确定答案属于哪一段值域上的区间，我们希望属于不同区间的给我们的反馈不一样。--15min

构造一下，考虑选择一个质数 p，那么假设询问序列包含 kp 和 (k+1)p，答案在这个范围内，就会导致返回的 \sum \gcd 变小 p-2。--19min

这个结构不够优美啊，你 (k+1)p 怎么接后面的呢？可以考虑找到下一个质数然后乘 2？看上去到了后面会跳的很快呢？--23min

额不过也问题不大，写个搜之类的，找个后面的包含不同 p 的数就行了，感觉肯定能得不少分，不对这个质数的部分分怎么才 20 分，还是得想正解。--25min

不是质数也太不优美了吧。还能和 k 产生一些问题。--27min

等一下，是不是不需要精确确定在哪个部分？只要重叠的够少就行了，反正主要是信息熵要够，那应该类似的结构也能要。--30min

但是限制很紧，稍微多一点分就很少了，我们这里需要 k_ip_i,(k_i+1)p_i,k_{i+1}p_{i+1},(k_{i+1}+1)p_{i+1}，中间那段就被浪费了，而且也无法区分。--32min

对了，我们可以考察这样一个结构：xy,(x+1)y,(x+1)(y+1),(x+2)(y+1),\dots，这样的话每一段初始 \gcd 就不一样，而且利用率也很高。--35min

这咋爆搜来着，额我们可以稍加修改变为 kxy,k(x+a_1)y,k(x+a_1)(y+b_1),k(x+a_2)(y+b_1),\dots。--37min

好的，接下来这个爆搜大概是能写了，我们对于一个集合，枚举 k，让 x,y 相差不大一下（使得每块均衡一点），设定序列长度 C，找到集合的 C 分位数，然后尽可能贴近 C 分位数选择 a,b 序列，让分出来最大集合尽可能小。--40min

（写代码）

朴素实现可以获得五六十分，优化的话包含选择合适的/枚举不同的 C，使用更加优秀的估价，适当改变结构为 kxyz 等，蠕动一会儿就可以 100 了，且肯定可以让做到小于 (4,35)。（我写的最优是 (4,32)）

Day 2

T1

阅读题面，套路化地二分一下，转化为 01 问题。--4min

问题还是有点复杂，先想一个更加暴力的做法：考虑 dp_{i,j} 表示 i 前缀分为 j 段的所有方案中，区段中位数 1 比 0 至多多几个。--10min

暴力转移是 O(n^2k\log n) 的，使用线段树做到 O(nk\log^2n)，当然由于这里相邻查询的位置只会移动 1 所以暴力维护这个线段树就是 O(nk\log n) 的。--11min

当然，这只能解决 k 小的情况。部分分有 k 大的情况，这启发我们去另外想个办法做 k 大的情况。--13min

注意到我们只需要区段中位数为 1 的数量大于 0 的数量就好，而最最朴素的 0101\dots10 的情况 1 都只比 0 少一个，所以这个条件其实很松。这也说明了为什么 k 偶数看起来会更简单，有一档这样的部分分：在朴素状态下 1 就跟 0 一样多了。--18min

可以使用调整法，每次把一段 010 合并为 0，因此在很多情况下我们只需要找最多划分为多少段就可以了！--22min

详细分析一下，对于偶数的情况，0110 没办法再合并了；对于奇数的情况，0110110 没办法再合并了，因此 k=2,3,5 需要特判，这与部分分吻合。--26min

实现上讲，我们只需要对 k=2,8,5 跑朴素 dp，对 k 更大的情况设计 dp_{i,0/1} 表示 i 前缀，分成偶数/奇数段，最大能做到 1 段比 0 段多多少，以及取到这个最大值的时候最多划分了多少段。最后要求 1 段大于等于 0 段且最多划分段数大于等于 k。总复杂度大常数 O(n\log n)。--28min

T2

阅读题面，先思考根据 prufer 序列如何构造树。--5min

可以发现，一个构造方法是：在 prufer 序列最后补上一个 k-1，从小往大枚举 i，找到 i 最后一次出现位置，将其填入下一个还没填数的位置。如此操作之后，将 prufer 序列每个位置的值与我们填的数连边，即可得到原树。--10min

暴力构造是 O(n) 的，O(nq) 可以获得 25 分。--11min

【思考了一会儿特殊性质】--16min

我们可以将问题转化为 x,y 分别被填到了哪里。考虑二分答案这个位置，那么问题被转化为了一个三维偏序，需要 O(n\log^3n)，难以通过。--19min

我们希望去维护一个第 k 小的没有被填的位置在哪里的东西，同时有两维：值域上小于某个 z 以及在序列的位置上小于某个 r。--21min

这样的结构跟三维偏序有一定距离，较为难做（好像实际上也能做）。--23min

考虑对这两维使用莫队，用线段树维护每个数的最后出现位置，然后就可以 O(n\sqrt{q}\log n) 做了。--25min

考虑使用分块，将这个线段树做到修改 O(1) 查询 O(\sqrt n)，即可做到 O(n\sqrt q+q\sqrt n) 的时间复杂度。--27min

T3

阅读题面，这是一道经典的形如对某个符合要求的东西带权计数问题，所以先想判定性问题（也就是某个集合 S 以及某个序列 c 是否合法）。--6min

【场上读错题了一会儿，秒了之后才发现不对劲】--12min

考虑 k_i 表示 i 子树最少有多少种不同颜色需要祖先也有这种颜色。考虑转移，设 sn 为儿子集合，设 x=(\sum_{s\in sn}c_s)+1-c_i，也就是最多重叠 x 种颜色，我们希望尽可能让不同子树的需要祖先也有这种颜色的颜色重合。因此我们得到转移：

--18min

考虑如何维护这个东西，一个暴力的 dp 状态设计师 dp_{i,j,l} 表示 i 子树，c_i=j，k_i=l 的方案数。转移的时候维护 c_s,k_s 分别的 \max 与 \sum。可以做到 O(n^6)。--21min

发现转移的一个难点是 \max_{s\in sn}c_s\leq c_i\leq (\sum_{s\in sn}c_s)+1，将转移容斥为 \max_{s\in sn}c_s\leq c_i 和 (\sum_{s\in sn}c_s)+1<c_i 分开做。--23min（好像是因为我考前看了 UNRD1T2，所以想到这个想的很快，对这步的难度持怀疑态度）

对于前者，发现在枚举完 c_i,k_i 之后，转移过程中只需要记录目前 \sum_{s\in sn}(c_s-k_s) 了。于是这部分时间复杂度降低到了 O(n^4)。--25min

对于后者，发现不需要枚举 c_i 了，优化掉一个 n，时间复杂度 O(n^5)。--27min

【赛场上的我直接开始写了，以下的 +xmin 指的是在通过本题后对本题的思考时间】

注意到内层将俩 n\times n 和 m\times m 的矩阵做二维卷积可以做到 O(n^2m+nm^2)，因此可以做到 O(n^4)。（具体而言，分块然后拉插）-- +6min

注意到 (\sum_{s\in sn}c_s)+1<c_i 时，x<0，也就是 k_i=(\sum_{s\in sn}k_s)-x+[i\in S]。因此也不需要枚举 k_i，这一部分可以直接做到 O(n^4) 了，用上面的优化可以做到 O(n^3)。-- +10min

其实可以讲一下卡常技巧，就是首先你要把除了一看就跑的飞快的二维多项式暴力卷积以外的部分通过前缀和等手段优化到 O(n^4)，然后你的 k_i 想要合法是不会超过 dep_i 的，枚举到 dep_i 即可通过。

A 类 5 分

不会的话转学去青海也可以解决，所以不讲。