2025.10 ~ 2025.11 NOIP 模拟赛

10.5 B

开始往根号想发现没啥性质，后面大概猜出来是要 $/\omega$。

跑 $n$ 次 bfs 跑不了，那就一起跑。每个点以 $d_i$ 为初始长度，边权为 $-1$ 跑最长路，一个点合法当且仅当 $dis=0$ 且每个 $d\not=-1$ 点都能更新到这个点，拿个 bitset 维护点集即可。

10.6 B

随机 $T$ 次，肯定会随到答案里的一个数 $x$，质因数分解之后如果直接做是 $\mathcal O(Tnd(V))$ 的，但是我们只关系整除的数的个数，所以对 $\gcd(a_i,x)$ 做狄利克雷前缀和就对上了，时间复杂度是 $\mathcal O(T(\sqrt V+n\log V))$，如果只筛质数的话 $\sqrt V$ 能除个 $\sim10$ 的常数。

10.6 C

如果 $nm$ 为奇数，可以划分成若干个环。如果是偶数，和上面一样构造最后是 $\dfrac {nm} 2$ 对点和一堆环。问题变成了对 $nm$ 组同色点对定向使得和为 $\pmb 0$。比较精妙的一步是改变原点到 $(n,\dfrac m 2)$，并且抽象成向量加减：等价于把红点划分成大小相同的集合 $A,B$，蓝点划分成大小相同的集合 $C,D$，且有 $A-B+C-D=\pmb 0$。那么整体可以划分成关于原点对称的红红，蓝蓝和红蓝对，最终只要选择若干个对，把对应的点放到 $A,C$ 里面就对了，因为 $A+C=B+D=\pmb 0$。因为题目中保证了至少有一对红蓝对，所以如果 $|A|$ 是奇数也能调整，一定有解。

10.6 D

搬这题的有人类吗。因为有精度限制，所以我们希望做一个递推状物的东西。发现一个差分序列如果把所有数 $-1$ 可以规约到更小的问题，而这个比往末尾加一个元素是好做的，dp 一下。

10.7 A

全场第二难。。。$\mathcal O(n^3)$ 随便做，令 $f_{i,j}$ 表示填完了 $sz \ge i$ 的组，且 $\ge i$ 还有 $j$ 个人没有分配的方案数，每次转移枚举组数，整体就是调和级数的了。

10.7 B

这种浓度题直接变成向量，排序之后操作等价于收缩凸包，那么线段求交一下。

10.7 D

这种维护连通性有个 trick：动态维护最上面 / 最下面的路径，如果修改到公共部分那么肯定没路了，否则就调整，暴力均摊是 $\mathcal O(nm)$ 的，可以通过弱化版，剩下懒得看。

10.8 C

令 $f(i)$ 表示长度为 $i$ 的排列按字典序排构成的序列，那么题目等价于从 $f(n)$ 里选出长度为 $m$ 的下降子序列。而且发现 $f(i)$ 刚好由 $f(i-1)$ 分别整体加 $0,1,\cdots i-1$ 顺序拼接而成的，于是直接 dp：令 $f_{i,\ell,x,y}$ 表示从 $f(i)$ 里面选出长度为 $\ell$ 的子序列，且首尾元素分别为 $x,y$，转移是一个卷积，复杂度为 $\mathcal O(n^8m^2)$。

10.8 D

一直觉得题解有问题，结果一看写着写着没保证 $t$ 是奇数。

学会抽象化问题，挺好一题。把操作看成循环异或卷积，那么我们希望找到矩阵 $C$，使得 $FC=A$，且 $C$ 内非零元素最少。试着找到 $F$ 的逆矩阵，厉害的一点在于联想到费马小定理，想到就容易发现 $F^{2^k}$ 是单位矩阵，因为 $F^2$ 等价于把所有值为 $1$ 的位置 $(x,y)$ 变成 $(2x,2y)$，其他的都会因为对称抵消掉。而又因为 $t$ 是奇数，所以最后 $F^{2^k}$ 只有 $(0,0)$ 为 $1$。所以 $F^{2^k-1}$ 就是其逆矩阵，那么 $C$ 就是唯一的！可以倍增求 $F$，因为对于任意 $k$，$F^{2^k}$ 的非零元素个数都 $\le t$，那么复杂度就是 $\mathcal O(tk4^k)$。

10.10 A

我实在不愿意承认这是题！爆搜考虑优化，如果 $4n<m$ 那么策略是固定的，带个记忆化就过了。

10.10 B

因为操作可逆，所以试着把两个序列排序再合并操作序列。分治，考虑归并两个序列。按照值域分治，可以递归到两个子问题，总大概是 $\mathcal O(n\log^2 n)$ 的，不会证明。

10.10 C

最后的结论还是神了，不是我会的。首先计数转期望有奇效，令 $\mathbb E(A,B)$ 表示 $A$ 个数 $\le x$，$B$ 个数 $>x$ 的期望答案，容易发现 $\mathbb E(A,0)=0$，接下来从 $\mathbb E(A,B)$ 递推到 $\mathbb E(A,B+1)$，每次加入数 $N+1$，其中 $N=A+B$。

长度为 $N$ 的排列中，$>x$ 的数把排列切成 $B+1$ 段。新加进去的 $N+1$ 必须排在第一个 $>x$ 的数前才会有贡献，其中第一个 $>x$ 的数前面期望 $\le x$ 的数个数为 $\dfrac A{B+1}$。而且 $N+1$ 还要放在这段 $\le x$ 的数中的最大值前面，最大值的期望位置为 $\dfrac{\dfrac A{B+1}+1}{2}=\dfrac{A}{2(B+1)}+\dfrac 1 2$。注意如果前面没数那就不存在最大值，减掉对应贡献 $\dfrac B N\cdot \dfrac 1 2$（这个 $\dfrac 1 2$ 是为了把前面式子里多算的减掉，不是本身出现的贡献）。于是 $N+1$ 要放在期望位置为 $\dfrac{A}{2(B+1)}+\dfrac 1 2-\dfrac {B}{2N}$ 位置数的前面，那么概率就是位置期望再乘个 $\dfrac{1}{N+1}$，递推式为 $\mathbb E(A,B+1)=\mathbb E(A,B)+\dfrac{1}{2(B+1)}-\dfrac{B}{2N(N+1)}$。已经可以 $\mathcal O(n)$ 计算了，但是把后面式子裂项开来发现可以直接每一项预处理出来，那就是预处理 $\mathcal O(n)$，查询 $\mathcal O(1)$ 了。

10.10 D

合法充要条件是相邻城市的首都相连链的中点，刚好是两个城市的分界线，dp 要查询和某个点固定距离的 dp 值和，点分树。

10.11 C

容易得到充要条件：每个环对应最大值一样，因为环不会跨过点双，所以对于每个点双问题独立。取出点双内最大的边删掉，如果分裂成了若干个点双，那么处理完子问题之后把每个点双组合数合起来就对了，为了接下来方便可以看成把最大的边和每个子问题最大的边连偏序关系，那就变成了一个森林拓扑序计数，这是典的。按照边权值从小到大加，每次把边的偏序关系处理出来，最后 dfs 一边。

当然上面需要一个结论：对于点双内任意两条边，肯定能找到一个简单环覆盖两条边，这个证明可以看原题解，结论本身是非常直觉的。

10.11 D

考虑判定两个区间 $[l,r],[l',r']$ 是否相同。如果两个区间有交把中间重叠的挖掉就无交了，变成无交怎么做。容易发现条件是 $[l,r]$ 出现的数对应的另一个位置构成连续段，这是非常经典的扫描线问题。模拟赛的时候写完发现不对，实际上一个等价类内的区间数可能 $>2$，但此时所有区间交一定 $>0$。对于一个等价类内的区间，排序之后只要保证一个区间只和下一个区间计算重复就好了，画一下就知道维护区间最小值的同时再维护 $\min$ 的种类数就对上了，又因为 $\min$ 单调所以容易处理。

10.13 A

这也太难了。让雨滴不动人动，那么一个点可以到达的是两条射线围成的区域，写一下式子就可以二维数点了！但是对于每个点，两条射线斜率是相同的，所以可以变换坐标系，应该写起来方便点。

10.13 D

首先如果有 $A+B<B+A$，那么 $A^{\infty}<B^{\infty}$，具体证明可以把其看成 $|\Sigma|$ 位小数看待。把原串划分成若干个段 $S=s_1+s_2+\cdots s_k$，且 $s_i<s_{i+1}$，取断点序列字典序最小的划分，那么插入一定只会在断点插，二分一下。

---

下面是题解区看到的另一种做法。对 $B$ 扫描线，显然排序后答案单调，对答案序列整体二分，每次判定只要在 $\mathcal O(|A|+|B|)$ 的复杂度内完成即可，可以 Z 函数预处理。对于初始询问的排序，可以先随机排列，再 stable_sort，这样期望只要比较 $\mathcal O(\log n)$ 次。

10.16 B,C

B 的话提醒了一下点边容斥，都忘了，NOIP 考了真死翘翘。C $\ge B$ dp 的时候中间可能会 $<0$，直接钦定 $a_1\ge B$，这样就不用考虑这个限制了。

10.16 D

令 $f_S$ 表示集合 $S$ 的答案，那么有转移：

$$f_S=\min\limits_{\{p\},\sum p=1}\max\limits_{i}b_ip_i+a_i(1-p_i)$$

其中 $p_i$ 表示对方选择 $i$ 的概率，$b_i=f_{s\backslash\{i\}}$。考虑二分答案 $C$，令 $d_i=\dfrac{C-a_i}{b_i-a_i}$，则对于所有 $a_i\le b_i$，有 $p_i< d_i$，显然这里 $p_i=0$ 就是最优的，额外判断一下 $a_i\le C$；对于所有 $a_i>b_i$，直接取 $p_i=\max(0,d_i)$，最后判定条件是 $\sum p\le 1$，因为多出来的一部分可以给任意一个 $a_i>b_i$ 的元素，而且这个 $i$ 必定存在，时间复杂度 $\mathcal O(n2^n\log \epsilon)$。重新看一下判定条件：

$$\begin{cases} \sum\limits_{a_i>b_i}\max(0,d_i)\le 1\\ \max\limits_{a_i\le b_i} a_i\le C \end{cases}$$

下面容易求出 $C$ 下界，上面是个 $\mathcal O(n)$ 段的分段函数，开始对 $a$ 排序，暴力扫一遍就是 $\mathcal O(n2^n)$ 的。

• 别怕列长式子，有元就设。

10.17 A

我觉得是困难的，不知道怎么都会。

尝试构造一个图：给定一个序列 $\{a\}$，其中 $a_i$ 表示左部点 $i$ 和右部点 $1\sim a_i$ 的点有边，且有 $a_i$ 不递减，$a_i\le i$。把题目转成 $S\not=\varnothing$ 且 $|S|\le |N(S)|$ 的个数，那么有 $k=\sum\limits_{i=1}^n\sum\limits_{j=1}^{a_i}\dbinom{i-1}{j-1}$。我们生成暴力从大往小枚举 $i$，且每次构造最大的 $a_i$ 就是对的，只要证明两点：

• 考虑完 $n$ 剩下的 $k< 2^{n-1}$

显然，当 $a_n=n$ 的时候总和为 $2^ {n-1}$，归纳即正确。

• $a_i\le a_{i+1}$。

只要证明有 $1\le j\le i$，$\sum\limits_{t=1}^{j+1}\dbinom{i-1}{t-1}\ge \dbinom{i}{j}$，显然。

于是 $\mathcal O(n^2)$ 做完。

• 遇到实在没有思路的构造题直接套有规律的东西，前缀，环，等等。

10.17 *C

10.18 B

彻底验证了我现在很菜的事实。枚举段做贡献是困难的，尝试换个贡献体，如果以段与段之间断点为贡献，枚举断点和左侧颜色数就容易 $\mathcal O(n^2)$ 计算，这个思想类似点边容斥。

• 如果你怎么做都做不出来，可能第一步就有问题。

10.18 C

讲一下强制在线 + $\mathcal O(n\log n+q)$。如果我取出了 $[l,r]$ 区间最小值，位置为 $p$，那么跨过 $p$ 的区间都是好计算的，而分别在 $[l,p),(p,r]$ 的区间可以差分。预处理 $f_i,g_i$ 表示以 $i$ 结尾 / 开头所有区间的权值和，容易用单调栈预处理。那么有 $ans[l,p)=\sum\limits_{i=l}^{p-1}g_i-g_p$，这里有可减性的原因是我们提出了最小值，那么 $[l,p)$ 的取值不会对容斥部分答案造成影响。

10.18 *D

10.20 C

这里提醒一下，还有一种容斥是类似连通图计数的，枚举第一个重复经过的两端点，后面乱填，这样也对。

10.20 *D

超绝 ad-hoc 好题，之前写到一半放弃了。现在还是不想订。

10.23 B

爆搜的时候一般把相同元素合并，否则变成指数级。

10.23 *D

10.24 B

二项式反演掉，然后对关键列直接暴力组合数，发现可以预处理掉。

• 先把最暴力的式子写了。

10.25 C

考虑怎么样避免三元环的干扰。一个普通环的任意相邻两条边 $u\rightarrow v, v\rightarrow w$ 绝对不会在一个三元环上，而且这是充要的。所以对每条边建点，如果存在边 $u\rightarrow v$ 和 $v\rightarrow w$ 且不存在边 $w\rightarrow u$，那么在前两条边之间连一条边，剩下的跑最小环。

10.25 *D

10.28 D

3 log 做法傻逼，观察到点状态数总和是 1log 的，那么双指针砍了一个。

10.29 B

提一下这一题。像这种比较复杂的信息合并可以不从区间合并考虑，试着一个个加元素，写成矩阵形式，有结合律就可以上线段树了，剩下的优化都是一些简单的，例如只记录有用元。

10.29 *D

11.3 C

一种求本质不同子序列的方法：维护 $a,b$ 表示以 $0/1$ 结尾的子序列数，每次加一个数等价操作 $a/b\leftarrow a+b+1$。然后你直接随机 $a,b$，判断方案合不合法，能过，不知道为什么能过，何意味。

11.8 D

假设询问区间 $[1,n]$，令 $h=\lfloor\log\max\limits_i a_i\rfloor$，那么答案为 $n+\min\limits_{i\in[2^h,+\infty)}(i+\sum\limits_{j}[a_j>i])$。方便一点，后半个式子变成 $n-\max\limits_{i\in[2^h,+\infty)}(\sum\limits_{j}[a_j\le i]-i)$。转成 Hall 定理，那么等价于有一个二分图，左部 $n$ 个点，其中第 $i$ 个点向右部 $1\sim a_i-2^h$ 的点连边，式子意义为求左部匹配的点个数。

因为是在线询问，而且我们不好列出一个能快速计算每个点贡献的式子，更偏向于预处理。我们发现，如果我们钦定匹配顺序是从右往左，那么 $[1,r]$ 的匹配方案中，编号在 $[l,r]$ 已经被匹配的点的个数就是 $[l,r]$ 的答案。直接对 $r$ 扫描线，每次加入一个数，如果不能匹配就把已经匹配的下标最小的弹出，这个容易用线段树维护，匹配方案可以用主席树，1log。

11.10 C

chain：从背包优化入手 $\rightarrow$ 二进制分组 $\rightarrow$ 从小值域入手 $\rightarrow$ 每个物品占据的位区间很短（可以记录信息），可以直接从低到高 dp

先二进制分组掉，发现最终总体积的第 $k$ 位只和所有 $\le 2^k$ 个物品的组有关，那么令 $f_{i,j}$ 表示考虑了 $\le 2^i$ 个物品的组，目前在决策第 $i$ 位，从 $i-1$ 进位了 $j$，$\mathcal O(n\sum a_i\log V)$、

11.10 D

chain：只考察连通性，希望有效边在 $\mathcal O(n)$ 级别，枚举众数 $\rightarrow$ 连边两端必定有一个是众数，分类讨论

这个图没有特殊性质，那么只能暴力连边。发现边两端必定有一个是众数，如果都是众数是好做的，单调栈暴力连；否则众数一端连的是一段区间，等价于只连区间点的边，差分掉。

11.12 C

注意一下这里反图 topo 可以平替缩点，而且能边 topo 边构造，好写很多。

11.12 D

算出每个点 $i$ 最远能跳到的点 $r_i$，那么每次可以跳到 $(i,r_i]$ 内任意一个值 $>a_i$ 的点。直接 dp 转移难以维护，找出一个明确的策略。如果 $v=n$，显然每次跳最大的优，因为能跳到的最大的点一定 $r$ 比剩下的点大。易拓展到普适的策略：每次跳区间内最大的 $<a_v$ 的点。这种跳跃类型的要么直接扫描线，或者分块 / 分治，这里两种都可以。

这题借鉴了题解的代码，还是有收获的：如果同时需要 max/min 线段树可以只定义一个，然后另一个修改值取反；而且如果需要部分清空直接遍历线段树，遇到不用清空的就不递归，复杂度也是对的，但这个不能对标记永久化的树处理，标记永久化的标记不能 pushdown（因为主席树节点共享）。

11.15 C

令 $f_{i,j}$ 表示决策到点 $i$，已选的点最多往上延伸到深度 $j$ 的最大值。$f_i$ 的有效 dp 值个数是 $\mathcal O(sz_i)$ 的，启发式合并就是 2log，然后有一个平凡的 1log 点分树做法。

11.15 D

11.17 D

有点太困难了，感觉瓶颈在于第一步。如果暴力维护前 $k$ 个的值差是不好做的，因为顺序会发生变化，我们需要一个不依赖顺序的解法。初始将 $b$ 从大到小排序，前缀和并整体取反。每次加入一个数 $v$，操作 $b_i=\max(b_i,b_{i+1}+v)$，最后 $b_0$ 就是答案。

观察到 $b$ 是凸的，所以可以维护差分数组，线段树分治。如果强制在线，因为这题删除的优先级已经提前给你了，所以当前集合只有最小区间大小个元素可能被删除，其他加进去，分析一下复杂度是 $\mathcal O(n\log^2 n)$。

11.19 A

从低位往高位考虑。看成进制数之后，先把最低位填满，剩下的都可以合并起来变成大一级的那个物品。感觉比第二第三题难。

11.19 C

我的方法应该是第二个题解：把所有两两之间差 $>d$ 的劈开来，小的一共只有 $\sum\limits_{i=0}^{k-1}m^i=\mathcal O(m^{k-1})$，枚举第一个访问的元素，前缀和优化一下就可以做。还有一种是从小到大 dp，插入元素，我们只关心前面 $m$ 个有没有在序列了，状压之后矩阵快速幂。

11.19 D

对串长根号分治（这么经典的东西你怎么能忘？？？），假设阈值为 $B$。如果询问串为 $s_k$，令 $\text{occ}(s,l,r)$ 表示 $s$ 在 $s_l\sim s_r$ 的出现次数，那么有 $ans=\sum\limits_{i=2}^{|s_k|}\text{occ}(s_k[1:i-1],l,r)\text{occ}(s_k[i,|s_k|],l,r)$。

对于 $|s_k|\le B$ 的情况，把出现次数差分掉，那么就是 AC 自动机板子：把所有串插入到 ACAM 里，每次加入一个串，查询是 fail 树上子树和。$\mathcal O(m)$ 个修改，$\mathcal O(qB)$ 个询问，分块平衡一下是 $\mathcal O(qB+m\sqrt m)$ 的。

对于 $|s_k|> B$ 的情况，把 $\min(i,|s_k|-i)\le B$ 的部分用上面方法处理掉，剩下的只有长度 $>B$ 的串互相贡献。注意到本质不同的 $\text{occ}(s_k,1,*)$ 只有 $\mathcal O\left(\dfrac m k\right)$ 个，这部分预处理是 $\mathcal O\left(m\sqrt m +\dfrac{m^2}{B}\right)$。本质不同的询问也只有 $\mathcal O\left(\dfrac {m^3}{B^3}\right)$，预处理复杂度是 $\mathcal O\left(\dfrac{m^3}{B^2}\right)$ 的。总时间复杂度 $\mathcal O\left(m\sqrt m+qB+\dfrac{m^3}{B^2}\right)$，平衡一下 $B=m^{\frac 2 3}$，复杂度 $\mathcal O(m^{\frac 5 3})$。

11.20 D

考虑一个时刻 $i$ 贡献的必要条件：令 $a_i,b_i$ 表示第 $i$ 次操作前 $A,B$ 的个数，则要求：

• $b_i\bmod 2\equiv0$。
• $a_i\bmod 3\equiv0$。
• $2a_i - b\ge 0$。

令 $v_i=2a_i-b$，则有 $v\ge 0$ 且 $v_i\bmod 6\equiv0$。我们猜测这个条件同是也是充分的，这样求最大值只要做一个所有 $v_i\bmod 6\equiv0$ 的 LIS 就好了，接下来构造性证明这个事情。初始所有 $\tt A$ 都先放左侧，$\tt B$ 放右侧。假设要构造段 $[l,r]$，其中 $v_r-v_{l-1}=6k$，我们需要在这一段做出 $k$ 次调整，每次使和 $-6$ 就对了，找到序列中第一个 $\ge 4$ 的 $v_j$（这一步怎么想到的？）：

• 如果 $v_j=4,v_{j-1}=2$，那么把 $j$ 处的 $\tt A$ 放到 2 位置，同时如果原来是 $h_1=h_2$，那么现在变成了 $h_2=h_3$，反着同理，更新完 $v_j=-2$。
• 如果 $v_j=5,v_{j-1}=3$，那么 $s_{j-1}=\texttt A$。把 $j,j-1$ 处的 $\tt A$ 放到相同的一对数上，那么此时 $v_j=-1$。

维护这个过程就好了，$\mathcal O(n\log n)$。

11.24 C

倒着做。令 $f_S$ 表示 $S$ 集合内的数已经确定的最小代价，转移枚举 $T$，要求如果操作 AND，那么 $T$ 内的数都为 $0$，$U\backslash S\backslash T$ 内为 $1$ 的数都为 $1$，暴力预处理需要记录上下界，变成 $\mathcal O(n3^n)$。发现令 $W$ 为 $U\backslash S\backslash T$ 集合中 $y$ 为 $1$ 构成的集合，那么有 $y\ \mathrm{and}\ (W\ \text{or}\ T)=a_i\ \mathrm{and}\ (W\ \text{or}\ T)$，这个可以预处理。其实就是发现两个条件可以并成一个条件：一个集合内和 $y$ 一样，$\mathcal O(3^n)$。

11.24 D

首先所有数 $\times 2n$ 好处理一点。考试的时候状态胡的是 $f_{i,0/1/2/3}$，比较史。实际上只要记录 $f_{i,0/1}$ 就好了，写起来好很多，转移是容易的，不多赘述。

11.25 C

注意一下打 tag 的方法：因为每个点状态不是单调的，所以要维护 set，那么就是多 log 的。这题如果建图比较难，每个点肯定想自己管辖区间内没有被探测到的井两边，本质区间只有 $\mathcal O(m)$ 的，那么可以线段树优化建图之后 topo。

11.25 D

爆搜出来状态，发现能过。

11.26 C

令 $f_{i,j}$ 表示处理完节点 $i$ 子树内所有边和父亲的边，其中到 $fa_i$ 的最长坏链长度为 $j$，最大的颜色数。发现我们合并的时候只要记录最大和次大就好了，暴力做单次合并是 $\mathcal O(k^3)$ 的，不好优化。把状态里的 $j$ 改成至多为 $j$，就可以做到 $\mathcal O(k^2)$ 转移。

11.26 D

$\mathcal O(n\log^3n+q\log^2n)$ 是容易的，然后双指针可以去掉一个 $\log$。

11.27 B

一种方法是考虑动态维护每个 $k$ 的答案，单次加 $1$ 只要找到这个数左右第一个比他大的，这里线段树二分；然后做一个区间加等差数列，可以两个 bit 维护。还有一种方法是先阶梯化，对于每个阶梯的 $v$，把里面所有连续段维护出来，这个式子也是好维护的。

11.27 D

发现列出来 dp 比较难优化，大概率是反悔贪心。假设我们钦定每个商店买 $b_i$ 物品，考虑购买策略。前 $b_i$ 个物品肯定选择放最近的距离的空地，最后一个有两种决策：如果到下一个商店上有一个空地，可以直接顺路放；否则要先绕到下一个空地，再返回到下一个商店。第二个决策不太好处理，因为贪心的之后并不知道下一个要选的商店什么。但是你发现如果你对当前商店做了第二个决策，那么后面一个商店肯定选满了物品，否则把这个物品换到下一个商店选最近的肯定更优。那你在第二个决策的时候就知道了下一个商店是什么，就可以直接做反悔贪心。