2025.7 ~ 2025.9 NOIP 模拟赛

7.20 A

最后只有两种改法：升高把自己的水填起来 或者 降低把旁边的水排出去，前面好做，后面暴力发现是 $\mathcal O(n)$ 的。

7.20 C

建完笛卡尔树，令 $f_u=A_uB_uC_u$，其中 $A_u,B_u,C_u$ 表示 $u$ 子树内在 $A,B,C$ 序列中的个数，那么 $ans=\sum a_u(f_u-f_{ls}-f_{rs})=\sum(a_u-a_{fa})f_u$，树剖维护。

7.21 D

往线段树上放堆想过，但是最后还维护了区间最大值！

线段树每个点维护堆和区间最大值，每次区间加数，查询直接找到对应堆 $\mathcal O(\log n)$ 个区间做。删除的时候，如果堆里有最大值但不包含于查询区间，暴力把最大值下方，$\mathcal O(n\log^2n)$。

7.22 C

简单题，但是有个小注意点：这题能容斥的前提是 $[a_{i-1},a_i,a_{i+1}]$ 不合法那么 $[a_i,a_{i+1},a_{i+2}]$ 一定合法，否则要多记一维。

7.22 D

好像网格分治是非常常见的，很久没做有点忘了！（我的洞真多）还有这题短边可以接受平方枚举。

分治，假如现在在计算 $n\times m$ 的矩阵，其中 $n\le m$。划分成两个 $(n,\dfrac m 2)$ 的问题，考虑跨过 $y=\dfrac{m}{2}$ 的矩阵数。令 $f_{i,j}/g_{i,j}$ 表示拼接点在 $(i,m),(j,m)$，左侧 / 右侧半边矩阵的个数，最终答案是 $\sum f_{i,j}g_{i,j}$。以左侧为例，令 $h_i$ 表示 $(i,m)$ 左侧最长能延伸的距离，对于拼接点对 $(i,j)$，延长距离为 $1\sim \min(h_i,h_j)$，枚举小的一个可以去掉 $\min$，剩下的就是前缀和，时间复杂度 $\mathcal O(nm(\log n + \log m))$。

7.23 C

这个 trick 没碰到过。赛时想过点分治，但是一直在考虑合并子树，合并就死了，必须按顺序决策。而且这个显然是重剖好写很多，但是思想是值得借鉴的。

瓶颈在于我们要做 $\mathcal O(m^2)$ 的卷积，如果是背包就会好很多，所以目标是转化成线性结构的，直接拍成 dfn。发现要记录所有祖先的选择情况，重剖一下，先遍历轻儿子再遍历重儿子，这样每个点只要记录轻边量级的个数。点分治也是可以的，最后都只要记录 $\log n$ 个 01 值，总复杂度是 $\mathcal O(T2^{\log n}nm)=\mathcal O(Tn^2m)$。

7.23 D

不会离线 $\mathcal O(n)$ 建虚树，$\mu=0$ 的贡献都算进去了，复杂度从 $\mathcal O(n2^{\max \omega(V)})$ 退化成 $\mathcal O(n\max d(V)\log n)$，服了。还有处理点对信息可以 dsu on tree。

容易得到容斥，可以 dsu on tree，或者虚树统计，剪枝优化是一个数有效的 $\mu(d)$ 个数应该是 $2^{\max \omega(V)}$ 的。

---

休息中。。。。。

---

8.7 D

相同连续段合并这种东西，尝试构造消除回路。从 $1\sim n$ 扫描序列，初始新建一个点 $r$ 作为起点。如果当前点有颜色为 $a_i$ 的边，那么移动到这条边的另一个端点，否则新建一个点，并和当前点连接一条颜色为 $a_i$ 的边。序列变成了移动序列，每次相当于缩掉序列中的一个环，最后要求变成简单序列。提取出起点和终点之间的链，链外的可以暴力缩掉并加入贡献，链上容易直接 dp。

8.16 D

枚举 $\times 2$ 的次数，转化成将一个数分解成若干个 $2$ 的 $0\sim k$ 次幂的方案数。从 $t=2^k$ 入手。记录个数肯定死，只能记录 $2$ 的次数。观察到如果将和为 $2^k$ 的序列从大往小排列，肯定存在一个断点前的数之和为 $2^{k-1}$，可以类似倍增的处理方案数。同样的如果 $t$ 任意，把他拆成若干个 $2^k$ 之和的段就好了，$\mathcal O(\log ^4 V)$。

8.18 C

想到了二分图性质，但是没有想到把 $x+v_{f(x)}$ 的形式直接换成 $2v_x-x$。

容易转化成差分约束模型，每个数看成一个未知数 + 常数的形式，但这样可能有负权边。如果每个数常数都为 $0$ 就是好做的。题目给出的关系是 $x_r-x_l=\dfrac{r-l}{2}$，移项一下得到 $2x_r-r=2x_l-l$，整体看成新的 $x$ 就没有常数了，而且容易发现最后跑出来的解必定是合法的。

8.19 A

每个数只会最多交换两次。令 $f_{i,x,y}$ 表示决策完前 $i$ 个数最后两个数为 $x,y$ 的方案数。观察到对于固定的 $i$ 有值的 $f_{i,x,y}$ 是不多的，map 暴力转移。

8.20 B

类似三元环计数给无向边定向，每个点的出边量级 $\le \sqrt {2m}$。枚举每个点作为团内入度为 $0$ 的点，再 meet-in-the-middle 一下可以通过。

8.20 C

没写，讲一下思路。

单调栈之后本质有用的区间只有 $\mathcal O(n^2)$ 个。枚举矩阵左上角的点，计算最大的向下延伸区间和向左延伸区间，转化一下条件是二维数点。

8.20 D

8.22 C

对于 $k\le 3$ 可以暴力 $\mathcal O(n^5)$，$k=4$ 可以规约到 $n=2$，$k\ge5$ 把原序列平均切割成 $5$ 段，至少有一段里有一个完整的周期串，暴力枚举 $\mathcal O(2^{\frac n 5}n)$。

8.23 C

直接算不好算。但是合法的 - 不合法是好算的。计算容斥系数 $(-1)^n=\sum\limits_{i=0}^n\dbinom n i c_i$，归纳一下得到 $c_i=(-2)^i$。然后列出式子二项式定理优化就是 1log。

8.23 D

8.25 D

二分答案 $x$，考虑贪心，每次拿出深度最大的节点，删掉其 $x-1$ 级祖先所在的子树，判断 $k$ 次操作之后所有点深度是否 $\le x$，这样已经 $\mathcal O(nk\log^2n)$ 了，观察到相邻点答案之差 $\le 1$ 可以砍掉一个 $\log$。

9.1 D（不用构造版本）

手玩之后可以发现能在任意位置插入 / 删除 $A^4,S^4,A^a,S^s$，最后只和 $A^{\gcd(4,a)},S^{\gcd(4,s)}$ 有关。先经过若干次操作把串转化成 $AA\cdots ASS\cdots S$ 的形式，手玩发现 $A$ 最多 $3$ 个，$S$ 最多 $1$ 个，分类讨论。

9.3 B

2log 做法枚举每一位二分。考虑能否类似倍增一样的求出所有答案。发现我们维护一个变量 $x$ 表示扫描位的时候，当前符合条件的个数。预处理归并的时候可以顺便算出一位前缀和，这足以推出答案。

9.4 D

这个范围给的很紧，如果我们按照正常离线扫描每个询问就要差分成两个，还需要支持区查，大概率逃不掉线段树，所以试图把他浓缩到一维里。扫描 $r$，令 $s_i$ 表示所有 $l\le i$ 的答案，每个询问的答案就是 $s_r-s_{l-1}$。观察到每次拓展修改的单点肯定是一段后缀，而且均摊是 $\mathcal O(n\log V)$ 的，做完了！

9.5 B

写一下我和题解的不同证法。首先把奇数边缩掉，再跑出一棵生成树。容易发现我们只关系边经过次数的奇偶性。而且最终方案一定能拆成一条 $s$ 到 $t$ 的链和若干个环的异或。环的个数是 $m-n+1$（按照线性基基底理解），然后链的个数是 $\dbinom n 2 + 1$（含 $s=t$），乘起来就对了。

9.5 C

想过三分，但是往 Hall 定理 + dp 想了。看完题解感觉这不是 sb 题吗！结果我是 sb。

三分之后，如果按照灰点权值贪心，能放就尽量放，否则可以证明可以更优，2 log。

9.5 D

相邻交换 / +1 / -1 操作很经典的就是前缀和只变化一个元素。以值域为版本建立主席树。容易发现每次操作只会改变一棵树，而且是另一个版本的区间覆盖，$\mathcal O(n\log n)$。

9.16 C

$\mathcal O(3^n)$ 做法是容易的。分别看两问，第一问瓶颈在于枚举子集转移，但是由于这题特殊性，可以只转移 $f_S=\max\limits_{u\in S}f_{S\backslash u}$，如果 $\sum\limits_{u\in S}a_u=0$ 那么给 $f_S$ 加一。第二问也可以同样做，但是会算重。于是多加一维 $i$，令 $g_{S,i}$ 表示 $\not=0$ 的集合大小为 $i$ 的方案数，如果和为 $0$ 要额外带一个 $\dfrac{1}{i-1}$ 的系数，因为除了最后一个钦定，其他顺序不确定，时间复杂度 $\mathcal O(2^nn^2)$。

9.16 D

感觉主要难度在于 implementation 和卡常。作为一个合格的省队选手，你应当在 15min 内想出做法。

看来我不是合格的省队选手！

对于一个固定的 $S$，我们如何做。先把所有数减掉 $L$，然后对 $>R-L$ 的个数容斥，式子应该是 $\sum\limits_{i=0}^k(-1)^k\dbinom k i\dbinom{S-k(L-1)-i(R-L+1)-1}{k-1}$。枚举 $i$ 做后面的组合数。设 $x=k(L-1)+i(R-L+1)+1$，那么 $\dbinom {S-x}{k-1}$ 换成下降幂形式，再把下降幂转普通幂，就可以 dp 了。

9.18 C

这题已经搬过一次了，但是这题有不一样的题解，看起来更加技巧性了！可以积累积累。感觉最有用的就是前缀最值变成格路计数部分，挺厉害的。

根据 Dilworth 定理，序列可以拆成两条下降子序列，为了好描述改成上升子序列。直接对两个归并会算重，所以我们钦定大的一条链的同时，还要求其是前缀最大值，所以前缀最大值序列和原序列构成双射。没有 $p_x=y$ 的限制可以把前缀最大值刻画成直方图，那最后就是一个有限制的格路计数（要保证非前缀最大值可以填的进去）。

如果有 $p_x=y$ 的限制，$y\ge x$ 的时候 $p_x$ 一定是前缀最大值，那么变成了两个格路计数。否则对偶一下，把原来的排列变成逆排列结论还是一样的。

9.18 D

用时间做状态是无法优化的，而且时间点并不都在区间首尾，如果在首尾要划分成若干个来回连续段，这是困难的，所以把他放值域里。令 $f_{i,0/1}$ 表示目前看了 $i$ 个幻灯片，在 $1/2$ 号教室，最小的需要的时间。转移的时候发现可能我来回一次经过了同个幻灯片，那不能算两次，于是再记一维 $0/1$ 表示在这个时间，另一个教室的 ppt 有没有看过，转移写出来容易二分优化。

9.19 B

非常 Ad-hoc 啊，困难的。

如果所有 $a_i\le 2$ 是好做的，有 $3$ 的话，消除方式只有 $3+1,3+3+2,3+5$。结论就是 $\sum\limits_{a_i\le 2} a_i\ge \sum [a_i=3]$，可以构造证明。于是直接令 $f_i$ 表示保留 $i$ 元素剩下最小的 $a$ 和对应最大的 $b$，每次从 $i$ 转移到 $j$ 相当于删去中间一段，容易用树状数组优化。

9.19 C

这种无法入手的构造一般可以证明上下界并直接构造出来。如果有 $k$ 个叶子，两种方案：都选除了叶子的所有点，一种选叶子白点，一种选叶子黑点，那么两者差为 $k$，答案下界为 $\left\lceil\dfrac k 2\right\rceil$。尝试构造到这个下界：将叶子按照 dfn 排序，前一半和后一半匹配成路径，路径上黑白染色。那么一个连通块和一条路径的交集一定是一条连续的路径，最多差 $1$，一共有 $\left\lceil\dfrac k 2\right\rceil$ 个集合那就达到了下界。

9.19 D 加强

9.22 B

9.22 C

被蠢蠢题爆了，最后一步是简单的，咋没想到。

Trie 上 dp 是容易的，发现可以莫队，但是没啥前途。试着对每个数做贡献：计算一个叶子 $u$ 的贡献，跳他的祖先，如果当前祖先深度为 $d$，那么这个数要有 $2^d$ 的贡献的话另一个儿子必须是空的，可以计算出对应 $[l,r]$ 表示如果查询区间在 $[l,r]$ 以内才有贡献，一个叶子有 $m$ 个区间，本质不同有 $m^2$ 个贡献区间。表面上是 4-side chkmax，仔细想想其实不用保证区间包含叶子，一定不优。剩下就是 2-side 了，分块平衡一下是 $\mathcal O(nm^2+q\sqrt n)$，注意我们实际无法存储 $nm^2$ 个区间，所以要边扫描先边找区间。

9.23 C

找出任意一条最大链然后正反各做一遍就好了。常见的用线段树合并，观察到一种求 LIS 方法是记录 $f_i$ 表示长度为 $i$ 的最小结尾，一个点的 $f$ 大小是深度级别的，那么长链剖分就可以做到 $\mathcal O(n)$。

9.25 C

第一问可以分三块累加：$<x$ 在 $x$ 前面的数；$>x$ 在 $x$ 前面且 $k$ 次之后没有被换到 $x$ 后面的数；还有 $<x$ 在 $x$ 后面 $k$ 次之后被换到前面了，扫描线。第二问可以把单点差分出来，把值阶梯化，这样只要对于每个值考虑 $0,1$ 的问题，最后主席树做完，还有卡我 1log 是什么意思。

9.25 D

怎么又被蠢蠢题爆了。为啥能想到对空栈 dp 但是还不会的！

栈里有东西是不好做的，所以试着变成空栈。关键一步在于给 $n-1$ 连颜色 $0\sim k-1$ 的 $k$ 条自环，同时起点建立 $n$ 个虚点 $n\sim 2n-1$，$n\rightarrow 0,n+1\rightarrow n,\cdots 2n-1\rightarrow 2n-2$ 连 $0\sim k-1$ 颜色的边，于是转化成了空栈问题，接下来都是容易的。令 $f_{u,v,c}$ 表示从 $u\rightarrow v$ 是否能以空栈状态开始并结束，同时最终方案中操作到 $u$ 时栈顶强制为 $c$（或空栈），时间复杂度能过。

9.26 C

容易写出朴素 dp，一种转移为 $f_{x,y}=\max(f_{x+1,y},f_{x,y+1})$，换种写法得到 $f_{x,y}=\min(f_{x+1,y+1},\max(f_{x+2,y},f_{x,y+2}))$。也就是如果后面那个 $\max$ 没被取到，每条主对角线的值都是一样的。画一下取到后面的转移只在和有洞的格子距离 $\le 2$ 才会被更新，那么暴力转移就好。

9.27 B

记录 $0/1$ 的个数就至少需要两维，但完全可以先填 $1$ 再填 $0$。令 $f_n$ 表示 $n$ 个 $1$ 可以组成的环方案，最后只要枚举环上的 $0/1$ 个数，但我们很难处理不在环上的点。改成对奇环容斥，这样不在环上的点可以任意钦定后继了。

9.27 C

不是，你扫 $r$ 扫不出来为什么不能扫 $\ell$。。。

发现前面两个元素是 $\mathcal O(n)$ 级别的，对 $\ell$ 扫描线，每次加入 $(x,y,?)$ 的时候就把线段树 $[2y-x,n]$ 对 $a_x+a_y$ chkmax，线段树。

9.28 D

记个结论：无向图邻接矩阵的 $\text{rank}$ 是最大匹配点数。证明大概是如果一个邻接矩阵 $\det\not=0$，那么这个玩意儿就有完美匹配。令 $f_u$ 表示 $u$ 和儿子匹配的概率，直接 dp。