做题记录

· · 个人记录

2025.7.1

http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=3330&tid=D

A

注意到环是独立的，考虑枚举环长，列出式子

\frac{1}{n!}\sum_{i=1}^{n}i^k\binom{n}{i}(i-1)!(n-i)!=\sum_{i=1}^{n}i^{k-1}

然后直接拉插，i^k 可以欧拉筛预处理。

B

考虑根号分治，>\sqrt{n} 直接暴力，否则最多 n\sqrt n 个询问，设 f_{x,r} 表示询问的答案。

注意到

\binom{ik+r}{x}=\binom{ik+r-1}{x-1}+\binom{ik+r-1}{x}

即 f_{x,r}=f_{x-1,r}+f_{x,r-1}（r=1 时要特殊处理），然后又发现

\sum_{i=0}^{k-1}f_{x,i}=\binom{n+1}{x+1}

递推+主元法解方程即可。

C

首先考虑 $l=r$，容易发现要插入 $x$，$x$ 只可能是插入的元素中 $x$ 的前驱和后继中较晚插入的元素的儿子，然后用 set 维护即可。 考虑加上限制，$1\sim l-1$ 可以直接确定，将 $1\sim l-1$ 设为白点，$l\sim r$ 设为黑点，对于 $r+1\sim n$ 先将确定连边的连了，那么黑点与黑点（或白点）之间就可能会存在一棵 $r+1\sim n$ 部分元素形成的子树，考虑对于一段连续的黑点怎么处理。 注意到可以区间 dp，设 $f_{l,r}$ 表示 $l\sim r$ 黑点的答案，然后就有转移 $f_{l,r}=\min(f_{l,k-1}+f_{k+1,r}+siz_{l,r})$。相当于枚举 $k$ 作为根，然后将 $k$ 的 siz 加进去，$siz_{l,r}$ 可以预处理。然后发现有决策单调性就做完了。 ### D 考虑枚举 $\max$ 和 $\min$，满足条件的树只可能是 $0$ 或 $1$。要求 $siz$，考虑枚举 $x$，如果 $x$ 满足 $x-\max$ 和 $x-\min$ 路径上不存在 $>\max$ 和 $< \min$ 的点，则在树内。 然后点分治，令 $mx$ 和 $mn$ 分别表示 $u$ 到分治中心路径上的最大值和最小值，则条件变为 - $mx[\max]=\max,mn[\max] \ge \min

考虑枚举 \min，如果从大到小枚举则 \max 和 x 的限制在变松，然后直接用双指针+线段树维护即可。

2025.7.3

https://vjudge.net/contest/726555

A

问题转换为在若干个环内选出总和为 k 的点，环内的点两两不相邻的方案数。求长度为 n 的环选出 k 个不相邻的点的方案数考虑断环成链和预分配，得到 \binom{n-k}{k}+\binom{n-k-1}{k-1}。然后把所有环卷积起来，用分治 NTT 做即可。

证明：断环成链，考虑 1 不选，则问题变成从 2\sim n 中选 k 个数两两不相邻，考虑预分配 k-1 个数，选出 k 个数后插入在相邻数之间，所有答案为 \binom{n-1-(k-1))}{k}=\binom{n-k}{k}；考虑 1 选，则 2 和 n 不选，问题便为从 3\sim n-1 中选 k-1 个数两两不相邻，同样处理得到 \binom{n-3-(k-2)}{k-1}=\binom{n-k-1}{k-1}。

B

容斥，考虑用总方案数 n^{m} 减去不合法的。求不合法方案可以考虑第一次不合法。设 f_i 表示 [i-n+1,i] 区间不合法，且是第一次出现，于是答案可以表示为

n^m-\sum_{i=n}^{m}f_in^{m-i}

这是显然的，不会算重也不会算漏，相当于枚举第一次不合法，后面随便填。考虑求 f。

如果不考虑第一次出现，则 f_i=n!n^{i-n}，然后枚举第一次出现（假如说 [j-n+1,j]）情况减去，分类讨论：

容易发现很像卷积形式，令 a_i 为

a_i=\left\{\begin{matrix} i!(i<n)\\ n^{i-n}n!(i\ge n) \end{matrix}\right.

于是可以通过分治 NTT 做到 O(n\log^2 n)。但是进一步的，设 F 为 f 的生成函数，A 为 a 的生成函数，S 为 n!n^{i-n} 的生成函数，则有

F=S-F*A\\ F=\frac{S}{1+A}

所以通过多项式求逆可以做到 O(n\log n)。

C

考虑单次修改，链上每条边到最后仍不变的概率。对于链上一条边 x\to y 来说，影响它的只可能是后续操作且在 x 子树内，而不变的概率就是 (1-p) 的乘积。所以容易得到做法，倒序处理操作，每次查询链上（注意这里不包含 x_i）权值之和，然后将链上权值乘上 (1-p_i)。用树链剖分加线段树即可。

D

先考虑概率。设 f_i 表示 i 个点的完全无向图连通的概率，g_i 表示 i 个点的完全无向图不一定连通的概率，则显然有

g_n=1=\sum_{[n]=\{S_1,S_2,\cdots,S_k\}}(1-p)^{\binom{n}{2}-\sum\binom{|S_i|}{2}}\prod_{i=1}^{k}f_{|S_i|}

乘的系数表示除了这些连通块内部的边外都要不存在的概率。解释的话就是若干连通块的概率之和。

系数不好看，考虑变形为

\frac{g_n}{(1-p)^{\binom{n}{2}}}=\sum_{[n]=\{S_1,S_2,\cdots,S_k\}}\prod_{i=1}^{k}\frac{f_{|S_i|}}{(1-p)^{\binom{S_i}{2}}}

套生成函数，设 \hat{G} 为左边的指数生成函数，\hat{F} 为乘积右边的指数生成函数，所以有 \hat{F}=\ln \hat{G}，可以求出。

现在求期望，考虑 \exp \hat{F} 的组合意义

\exp \hat{F}=\sum_{i=0}^{\infty}\frac{\hat F^i}{i!}x^i

考虑 [x^k]，假设乘了 (1-p)^{\binom{k}{2}}，则分子表示 k 个点形成 i 个有序连通块的概率，除以 i! 为形成 i 个无序连通块的概率，那要求期望即再乘上 i，变为

\sum_{i=1}^{\infty}\frac{\hat F^i}{(i-1)!}x^i=\hat F\sum_{i=0}^{\infty}\frac{\hat F^{i}}{i!}x^i=\hat G\ln \hat G

2025.7.5

http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=3330&tid=H

A

看成二进制数，Alice 有策略使得每一次轮转后数单调递增。

B

有二选一，考虑建图。连边 (a_i,b_i)，于是如果一个连通块有环，显然是有解的；否则是树，区间不能完全包含这棵树，否则必然存在一个选不了，于是记录一下树里 id 最小值和最大值作为区间，随便维护一下即可。

C

无向图四元环计数板题。

https://oi-wiki.org/graph/rings-count/

D

维护点对信息，不太好用线段树维护，考虑分块。

首先预处理块内两两之间的答案，这部分时间复杂度为 O(n\sqrt n)。然后考虑处理跨块的答案，只需要维护每个元素在块内的第一次和最后一次出现，询问时扫一遍即可。于是便能解决没有操作 1 的情况。

考虑加上修改，对于整块的打 Tag 即可，在询问时特判一下；对于散块，首先如果有 Tag 先修改，然后相当于将 [l,rt]（或 [lt,r]）赋值为 x，影响的只会是 [l,rt] 区间内颜色和 x 的答案。所以只需要将 [l,rt] 内的颜色拿出来（如果没有完全被覆盖），然后更新它与块内其他颜色的答案。假如说该区间内有 k 个互不相同的颜色，那么经过这次操作会减少 k-1 种颜色，所以这部分时间复杂度为 O(k\frac{n}{k-1}\sqrt n)=O(n\sqrt n)，或者说均摊 k 为 O(1)。

一些细节：由于块内两两之间的答案是在离散化后，所以当 x 是新增颜色时，需要复用不存在（cnt=0）的颜色编号，所以拿一个 vector 存一下，然后复用即可。

2025.7.8

http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=3342&tid=J

A

考虑枚举 a 的一个前缀，并找到 b 最大的一个前缀满足前缀和 \le a 的前缀和，这时如果相等直接输出即可；否则因为值域为 [1,n]，所以前缀和之差 \in [0,n-1]，又因为 0 判掉了，所以是 [1,n-1]，由于有 n 个前缀，所以根据抽屉原理必有两个差相等，然后答案就是两段区间。

B

考虑转成最大流模型，一个完全二分图（容量为 1），原点向第一排点连容量为 k_i 的点，第二排点向汇点连容量为 b_i 的点。相当于每一次选 1 对点 -1。考虑转成最小割模型，由于其性质，枚举断掉几个容量为 k_i 的边（显然选最小的几个），那么要么断掉容量为 b_i 的边，要么断中间的边。然后答案可以写成

\min_{i=0}^{m}\left(\sum_{j=1}^{i}k_j+\sum_{j=1}^{n}a_j\min(b_j,m-i)\right)

注意到随着 n 变大最优决策点 i 是单调不降的，然后用整体二分即可。

C

考虑按值域倍增分块，第 i 块值域为 [B^i,B^{i+1})。然后对于每一块维护一个序列上的线段树，对于一次修改 x，对于每一个块（设值域区间为 [kl,kr]）的线段树，假如说当前区间最大值已经 \le x，那就直接返回；如果最小值 -x\le kl，直接打标记即可；否则往下递归。当递归到叶子节点时，可能需要跨块操作，然后修改一下即可。

最多执行 O(n\log_B n) 次跨块操作，一次跨块的代价最多为 O(\log n)，这一部分时间复杂度是 O(n\log_B n\log n)，

2025.7.10

http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=3342&tid=M

A

环长为 3、、、

B

注意到，当元素种类为 3 时，必定会形成若干个块，后一个块的开头对前一个块形成克制关系。

容易发现，当块的个数模 3 为 0 时，性质很好。因为在经过 n 轮挑战后块与块之间的顺序不会发生变化，这是显然的，变化的只有块内元素的相对顺序。并且模拟发现实则在做冒泡排序，所以这一部分很好处理。

当块的个数模 3 不为 0 时，容易证明通过不超过 n 轮挑战一定能变成模 3 为 0 的情况。

C

把答案拆成每条边的贡献，然后通过一些变换便能形成一次函数形式，然后李超树合并。

D

对出现次数模 k 哈希，变成选两个哈希值相同的前缀，然后莫队。

2025.9.8

https://vjudge.net/contest/746156

A

考虑暴力怎么做，f_i 表示二进制数 i 的答案，枚举超集更新即可。考虑优化，有二进制，所以直接折半，即 f_{i,j} 表示左半边为 i 右半边为 j 的答案，更新枚举超集，求值枚举子集即可。时间复杂度 O(n2^{10})。

B

考虑以直径中点 u 为根。则深度越深的点 f_i 越大。有了这个性质便可以做了，对于点 x 找到其祖先深度最浅的点 y 满足 f_x-f_y\le l，则以 x 到 y 链上任意一点为根，y 都可以在其连通块里，于是直接二分加树上差分即可。

D

不仿让 x 递增，设 y_i 表示 x=i 时的 y。则 [l,r] 合法当且仅当 \max y_i-\min y_i=r-l，移向得到 \max y_i-\min y_i-r+l=0。结合性质 \max y_i-\min y_i-r+l\ge 0，考虑扫描线，点 i 维护 [i,r] 的值，注意到只需维护区间最小值和最小值个数即可，更新 \max 和 \min 用单调栈区间改即可。

2025.9.9

http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=3359&tid=Z

B

最后统计答案要考虑先后顺序，即 $\sum f_{1,i}A(m,i)$。 考虑直接做 $O(nm^2)$ 的dp，容易发现 $f_{i,j}$ 是一个关于 $j$ 的 $siz_i-\text{leaf}_i$ 次多项式，所以直接维护 $siz_i-\text{leaf}_i$ 个点值，卷积合并只需要乘起来，时间复杂度 $O(n^2)$ 。 ### C 注意到关键结论： $$ f(S)=\gcd_{u,v\in S}\{f(\{u,v\})\} $$ 其中 $f(S)$ 表示只取 $S$ 集合内的元素最小周期的**周期数**。 所以便可以 $O(nk)$ 算出 $f(\{u,v\})$，$O(qk^2)$ 回答询问。考虑分块，假设块长为 $B$，则共有 $C=\frac{k}{B}$ 块，块内可以通过 $2^BB^2$ 时间复杂度预处理 $f(S)$，总时间复杂度 $O(C2^BB^2)$。考虑块与块之间，先通过 $O(C2^Bk)$ 的时间复杂度预处理 $i$ 到某块内集合为 $S$ 的 $f$ 值，然后便可以通过 $O(C^24^B)$ 从 $\text{lowbit}$ $O(1)$ 转移过来，得到 $g(S1,S2)$。询问时间复杂度 $O(C^2q)$。$B$ 取 $8$ 跑得最快，时间复杂度 $O(nk+C2^BB^2+C2^Bk+C^24^B+C^2q)$。 ## 2025.9.12 https://vjudge.net/contest/746885 ### A 显然最小生成树是唯一的，让最小生成树上的边为树边，则对于一条横叉边 $u\to v$，只有当根在这两个点的子树中时才不会 dfs 到这条边；同理对于一条返祖边 $u\to v$，只有当根在 $u$ 子树，或整棵树去掉 $v$ 位于链上的儿子那个子树时合法。 ## 2025.9.28 https://vjudge.net/contest/750619 ### D 观察发现，为了让和最大肯定考虑让每个 $hw$ 的矩阵和都为 $-1$，且填的负数尽量少。于是考虑构造全 $1$ 矩阵，在每个 $(i,j)(i=hx,j=wy)$ 的地方填 $-hw$，假设有 $t$ 个，则和为 $HW-t(hw+1)$。但是仍然会被 hack。 问题出在值域，考虑如果是全 $k$ 矩阵，则填的数变为 $-k(hw-1)-1$ 则和就变为 $HWk-t(khw+1)=k(HW-thw)-t$。如果 $HW-thw<=0$ 那没办法，否则的话要让该式 $>0$，$k$ 就要尽量大，所以只要能大过 $t$ 就行。 ## 2025.9.29 http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=3359&tid=u ### B 求所有包含绝对众数的区间的长度乘众数的和。 考虑分治。注意到前缀和后缀不同绝对众数只有 $O(\log n)$ 个，所以直接枚举众数然后扫猫线即可。 ## 2025.10.7 http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=3359&tid=%E2%92%B7 ### B 由于走路的存在，所以对于两个机关之间的区域是一个等价类，里面的点可以互相到达。 这个题明示图论，考虑最短路。这样的等价类是 $O(n)$ 个，并且对应区间 $[l,r]$ 两两不交，考虑通过冲刺能到达的区间 $[l+k,r+k]$ 也是两两不交，所以只需要双指针求出每个区域能到哪些区域，然后跑 dij 即可。容易证明边数也是 $O(n)$ 的。 ### C 先考虑朴素 dp，设 $f_{u,i}$ 表示 $u$ 祖先 $c$ 之和为 $i$ 子树内的答案，容易写出转移： - $f_{u,i}=\sum f_{v,i}$。 - $f_{u,i}=f_{u,i+1}+w_u$。 同时对于 $i<v_u$，需要强制将 $f_{u,i}$ 变为 $f_{u,v_u}+(v_u-i)w_u$。于是便可做到 $O(nV)$。 观察性质，发现 $f$ 是凸函数，要执行加法、按斜率 $w_u$ 推平和强制推平。所以直接维护斜率变化量，用线段树合并或可并堆便可做到 $O(Tn\log n)$。 再换一种方式刻画图像，考虑在 $x$ 处每增加一个拐点，就将前面每一段的斜率 $-1$，于是手推不难发现转移变为合并完所有拐点后，在 $v_u$ 处增加 $w_u$ 个拐点，并在所有拐点中，取最大的 $w_u$ 个。 最终是要求 $f_{u,0}$，不难发现即为所有拐点的横坐标之和。于是考虑一个点删去了哪些拐点，首先我们知道一个点合并后有 $w_u+\sum w_v$ 个拐点，所以要删去 $\sum w_v$ 个拐点。因为要保留最大，所以按 $v$ 从小到大排序，考虑 $u$ 的 $w_u$ 个拐点在哪些祖先（包括自己）中被删除，直接依次删即可，假设在 $f$ 删了 $d$ 个，则对 $f$ 贡献为 $-dv_u$，最后合并起来即可。 ### D 显然如果一个 $x$ 区间被选，但端点并不为最大 $y$ 或最小 $y$，则可以将区间变短而不劣。 于是问题变为在二维平面上选若干对点 $(i,j)$，假设 $y_i<y_j$，则要求对于 $\forall k,\min(x_i,x_j)\le x_k\le \max(x_i,x_j)$，要满足 $y_i\le y_k\le y_j$。考虑如何去刻画这个合法条件，先按 $x$ 从小到大排序，然后分别按 $y$ 建出大小根笛卡尔树，则要求大根笛卡尔树中 $j$ 在 $i$ 的子树里，并且小根笛卡尔树中 $j$ 是 $i$ 的祖先。 然后考虑 dp，按 $y$ 从小到大排序，设 $f_i$ 表示考虑前 $i$ 个的答案，则 $f_i=\max\{f_{j-1}+w(j,i)\}$，并且要满足上文的限制。$j$ 是 $i$ 的祖先且 $j$ 在 $i$ 的子树里。第二个可以变为 $j$ 要满足 $x_j$ 在一段区间中，所以考虑可持久化线段树。下标为 $x$，值为 $dp$ 值，每次在父亲所在的线段树中查询，继承并加入 $i$ 到 $i$ 这棵线段树中，由于按 $y$ 从小到大的顺序枚举，所以祖先肯定已经处理过了。由于要讨论 $x_j$ 和 $x_i$ 的大小，所以要存 $2$ 个值。 ## 2025.10.8 http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=3359&tid=%E2%92%BB ### D 最优性问题改为判定性问题，考虑二分直径 $x$。 设 $f_{i,j}$ 表示考虑了前 $i$ 个点，连了 $j$ 条边且目前直径 $\le x$，前面的点到 $i$ 距离的最大值。转移从 $f_{k,j-1}$，随便预处理一点东西判断合法即可。 时间复杂度 $O(n^3\log V)$。 ## 2025.10.9 http://oj.daimayuan.top/contest/402 ### A 求子树内 siz 为某个值的子树个数可以放在 dfs 序上转为求区间里某个值的个数可以离线下来直接做。 ### B >因为我并不会这个比较经典的问题，但既然答案这么问那就只能区间 DP 模拟题意然后四边形不等式优化到平方。——wxr 考虑设 $f_{i,j}$ 表示答案，然后按题意直接模拟枚举断点，容易发现当与这段区间有交的询问都包含这段区间的话，深度就是 $0$，这也是初始化。 然后需要特判 $f_{i,k}$ 和 $f_{k+1,j}$ 深度都为 $0$ 的情况，这时所有包含 $[i,j]$ 的询问在左右两边都会算到，但事实根本不会往下下放，所以合并时就会算错。 ### C 考虑转化成枚举 $k$ 个点的划分方式，然后将方案数乘系数。 首先考虑如果是 $m$ 个连通块，大小分别是 $a_1,a_2,\cdots,a_m$，则将连通块之间连边使其构成树的方案数由 $\text{Prüfer}$ 序推论可得 $\prod a_i\left(\sum a_i\right)^{m-2}$，而在此题中要求划分出这 $m$ 个连通块不能互相连边，然后还有 $n-k$ 个点，则使其构成树的方案数观察计算~~找规律~~即能得到 $(\prod a_i)n^{n-k-1}(n-k)^{m-1}$。 于是考虑 dp，设 $f_{i,j}$ 表示 $i$ 个连通块有 $j$ 个点的权值，转移枚举当前连通块的大小，即 $$ f_{i,j}=\sum f_{i-1,j-l}\binom{j-1}{l-1}l^{l-1} $$ 由于需要钦定当前连通块的某个点，所以组合数要 $-1$，而生成树方案 $l^{l-2}$ 还需要乘上连通块大小 $l$。那么最终答案即为 $\sum if_{i,k}(n-k)^{i-1}n^{n-k-1}$，考虑如果不乘 $i$ 的话 $i$ 这一维是不需要记的，所以在设 $g_j=\sum if_{i,j}$，然后用 $f_j$ 转移即可。 ### D 考虑一条非树边加入时对于一条路径上的树边都已经加入了才行，正着做不好处理权值，考虑倒着加边。 将非树边看为白点，树边看为黑点，则白点加入的条件是对应路径上的所有黑点都没有加入过。并且黑点只能加入到开头，白点可以任意插入。假设当前有 $n$ 个点，$m$ 个黑点，方案数为 $c$，权值和为 $s$，容易得到 - 加入一个白点，转移到 $(n+1,m,c(n+1),s(n+2))$。 - 加入一个黑点，转移到 $(n+1,m+1,c,s+(m+1)c)$。 加入多个白点相当于是一个上升幂。然后考虑优化，直接将黑点状压即可，需要求从一个状态到另一个状态要加多少个白点，这个可以高维前缀和预处理。时间复杂度 $O(2^nn)$。 ## 2025.10.10 https://vjudge.net/contest/754928 重要式子： $$ \gcd(a,\text{lcm}\{S\})=\text{lcm}\{\gcd(a,b),b\in S\} $$ ### A 正着做限制太多，考虑倒着做。 假设现在还有 $a_1,a_2,\cdots,a_k$ 没加入，则 $a_i$ 合法的条件为 $a_i\nmid \text{lcm}\{a_j|j\ne i\}$，也即 $\gcd(a_i,\text{lcm}\{a_i|j\ne i\})<a_i$，也即 $\text{lcm}\{\gcd(a_i,a_j),j\ne i\}<a_i$。 所以每次选一个数出来时间复杂度是 $O(n^2\log V)$ 的，总时间复杂度为 $O(n^3\log V)$。 ### B 考虑统计 $f_i$ 表示选出来的数，下标两两 $\gcd=i$ 且 $\gcd(p_i,p_j)=1$ 的方案数。 考虑先直接将下标为 $i$ 的倍数的数拿出来，然后容斥减去 $f_{ki}$，统计 $\gcd(p_i,p_j)=1$ 的对数直接莫比乌斯反演便可直接做了。时间复杂度是 $O(n\log n \max d_i)$。 ### D 一个数 $x$ 要在集合 $S$ 中，则由裴蜀定理易得需要 $\gcd(S\setminus x)\nmid x$，考虑转换成，对于每个 $x\in S$，需要满足 $\exist p$，设 $c_i$ 表示 $p$ 在 $i$ 中分解后的指数，则要求 $c_x>c_y,\forall y\in S \land y\ne x$。 考虑枚举 $d=p_1^{r_1}p_2^{r_2}\cdots p_k^{r_k}$，表示选出了 $k$ 个数，第 $i$ 个数 $s_i$ 满足对于 $j\ne i$，$p_j^{r_j}\mid s_i$ 且 $p_{i}^{r_i}\nmid s_i$，这样的一组数显然是合法的。然后容易发现对于 $\forall i$，$\frac{d}{p_i^{r_i}}\le m$，其中 $m$ 为 $\max a_i$，否则就找不到合法解。 令 $p_1^{r_1}<p_2^{r_2}<\cdots<p_k^{r_k}$，容易发现当 $k>2$ 时 $p_1^{r_1}\le \sqrt m$ 是可以直接枚举的，然后 $p_2^{r_2}p_3^{r_3}\cdots p_k^{r_k}$ 又是 $\le m$ 的，所以直接枚举时间复杂度是 $O(m\sqrt m)$ 的，然后对于一组 $p_i,r_i$，其合法条件是 $f_{d}<f_{d/p_i^{r_i}}$，其中 $f_i$ 表示 $i$ 的倍数的个数，所以判断时间复杂度是 $\omega(m)$ 的，卡卡常可以通过。而对于 $k=2$，容易发现是找到一组 $(i,j)$ 满足 $a_i\nmid a_j$ 且 $a_j\nmid a_i$，在值域范围下最长不合法序列长度是 $O(\log m)$ 的，所以直接枚举即可。 ### F 考虑 $S_1,S_2$ 的合法条件，即对于 $\forall a\in S_1,a\mid \text{lcm}(S_2)$ 且 $\forall b\in S_2,b\mid \text{lcm}(S_1)$。然后一如既往地、不失一般性地、套路地将整除变为 $\gcd(a,\text{lcm}(S_2))=\text{lcm}\{\gcd(a,b),b\in S_2\}=a$。 然后考虑先都选全集，然后考虑不断删数，每次暴力判时间复杂度太高，考虑在一个集合中删去了一个数后会对另一个集合的哪些数产生影响。 假设删去 $S_1$ 中的 $a$，则对于 $b\in S_2$，合法的条件为 $$ \gcd(a,b)\mid \text{lcm}\{\gcd(a',b),a'\in (S\setminus a)\}\\ \gcd(\gcd(a,b),\text{lcm}\{\gcd(a',b)\})=\gcd(a,b)\\ \text{lcm}\{\gcd(a,b,a')\}=\gcd(a,b)\\ \gcd(b,\text{lcm}\{\gcd(a,a')\})=\gcd(b,a) $$ 每次 $O(n\log V)$ 求一下 $\text{lcm}\{\gcd(a,a')\}$ 即可，时间复杂度 $O(n^2\log V)$。 ## 2025.10.11 http://oj.daimayuan.top/contest/403 ### C 先考虑没有 $l,r$ 限制时的第 $k$ 大，做一个树形 dp，$f_{i,j}$ 表示 $i$ 子树无限制第 $j$ 大，转移看这一位 $0$ 还是 $1$ 即可。 现在加上 $l,r$，本质上能拆分出 $\log$ 个区间，每个区间都无限制，这个边走边算即可。 ### D 考虑轮廓线 dp，先做 $k=1$。 ## 2025.10.14 http://oj.daimayuan.top/contest/405 ### A 首先要观察到原序列是能分成若干段，段与段直接是独立的。容易发现将 $A,C$ 分成一组，$B,D$ 分成一组，当相邻的两个数是一组时一个一定不能跨过另一个，所以现在问题变为对于一段计算答案。 然后再发现无论怎么交换，$A$ 和 $D$ 的相对顺序是不会变的，且 $A,D$ 下标奇偶性不变且不同。不妨将 $A$ 的下标看做奇数，于是问题变为在奇数位置选 $a$ 个 $A$，偶数位置选 $b$ 个 $D$ 使得 $A,D$ 相对顺序不变。考虑将 $A,D$ 看作 $1$，$B,C$ 看作 $0$，先将原序列化为最简，形如 $10111010000\cdots$，然后相当于每次在末尾选相邻的两个 $0$ 插到两个 $1$ 之间，组合数容易算出方案。 ### C 首先有惊人结论，这种构思是代码偏短的思维题，嘴角一歪，小手一抖简单计算即可，若常数不算大就可以通过。不过过于炸裂，虽然也能拿到一定分。发现直接线段树是可接受的，比较难写。 ### D 考虑它到底要求什么，拿三维举例，对于 $(i,j,k)$，必须要有一个 $(j,*,*)$、$(k,*,*)$、$(*,i,*)$、$(*,k,*)$、$(*,*,i)$、$(*,*,j)$ 跟它颜色相同，那显然最少就是用 $(j,k,i)$ 和 $(k,i,j)$ 两个格子。但是注意到对于 $(i,j,j)$ 这个就不优了，可以直接 $(j,i,i)$，然后再凭一点直觉就发现就是 $\{i,j,k\}$ 去重后值域的轮换。 然后通过~~打表~~斯特林数+组合数就得出来这个算出来的答案为 $\sum_{i=1}^{n}i^{k-1}$，又由于保证每个格子跟它颜色相同的格子数最小，所以总颜色数就最大了。 ## 2025.10.17 https://vjudge.net/contest/757202 ### A 直接跑费用流，由于其 $1\le dis\le 5$，所以在用 dinic 多路增广的情况下时间复杂度变为 $O(5n\sqrt m)$。 ### J 考虑直接用 https://www.cnblogs.com/chara-/p/18722684 中“最小割-建模-更一般的情况”的建图方法，本题 $g$ 满足四边形不等式，所以可以用。 ### F >**重要式子！！！**： >$$ >\sum_{i=1}^{n}\min(a_i,w)=\sum_{i=1}^{w}\sum_{i=1}^{n}[a_i\ge i] >$$ 跟本文 “2025.7.8 B” 有异曲同工之处。 考虑最小割，如果选择割左侧点的集合为 $S$，则代价为 $$ \sum_{i\in S}a_i+\sum_{i=1}^{m}\min(b_i,n-|S|) $$ 容易发现后面只跟 $|S|$ 大小有关不妨将 $a$ 排序，于是枚举 $|S|=k$，变为 $$ \sum_{i=1}^{k}a_i+\sum_{i=1}^{m}\min(b_i,n-k)=\sum_{i=1}^{k}a_i+\sum_{i=1}^{n-k}c_i $$ 其中 $c_i$ 为 $b$ 中 $\ge i$ 的个数。 于是便能用线段树直接维护出 $k\in [1,n]$ 的答案了。 ## 2025.10.21 http://oj.daimayuan.top/contest/409 ### A ![](https://cdn.luogu.com.cn/upload/image_hosting/352mpn2p.png) 因为限制是 $O(L\sqrt{n^2})$，考虑莫队。因为欧几里得距离 $\le$ 曼哈顿距离，所以放缩成曼哈顿距离。分析莫队的复杂度，将 $x$ 划分成 $n$ 段，每段纵坐标的长度不超过 $L$，所以纵坐标变化总和为 $nL$，对于横坐标，每段内的点最多变化块长 $\frac{L}{n}$，所以是 $n^2\frac{L}{n}=nL$，但是跨段的时候最多会变化 $2\frac{L}{n}$，所以有 $\frac{L}{n}n=L$ 的常数。总共就是 $(2n+1)L$。但是曼哈顿距离取满时欧几里得距离取不满，所以能过。 普通莫队，长度（对应 $L$）为 $n$，询问（对于点数）为 $q$，所以取块长 $\frac{n}{\sqrt q}$ 有时间复杂度 $O\left(n(2\sqrt q+1)\right)$。 ### B 自然数异或，周期为 $4$。分讨题。 ### C 何意味。 ### D 将全局限制改为局部限制，由于最短路跟起点集合一一对应，考虑统计合法 $b$ 的个数，要求 - $b_i\ge 1$。 - $|b_i-b_j|\le 1$。 - 当 $b_i>1$ 时存在相邻的点 $b_j=b_i-1$；$b_i=1$ 时存在相邻点跟它异色。 直接 dp 即可。时间复杂度 $O(n^2k^2)$。 ## 2025.10.22 http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=3396&tid=E ### A 若干数的乘积考虑先取对数然后变成加法再 exp 回去。 ### B 期望变为选出数的 $\gcd\ne 1$ 的概率之和，包括空集。因为 $$ E=\sum_{i=1}^{n}P(\text{exact }i\text{ round})i=\sum_{i=1}^{n}P(\ge i\text{ round}) $$ 先考虑 $o=2$， 然后考虑枚举选出数的 $\gcd=d$，记为 $f(d)$，设 $cnt_i$ 表示 $i$ 倍数的个数，容易发现 $$ f(d)=\sum_{i=1}^{\infty}\left(\frac{cnt_d}{n}\right)^i-\sum_{k>1}f(kd) $$ 设 $F(d)=\displaystyle\sum_{i=1}^{\infty}\left(\frac{cnt_d}{n}\right)^i$，则 $F(d)=\displaystyle\sum_{d|n}f(n)$，根据莫比乌斯反演容易得到 $f(d)=\displaystyle\sum_{d|n}\mu\left(\frac{n}{d}\right)F(n)$，而我们要求 $$ \begin{aligned} \displaystyle\sum_{i=2}^{V}f(i)&=\sum_{i=2}^{V}\sum_{i|j}\mu\left(\frac{j}{i}\right)F(j)\\ &=\sum_{i=2}^{V}F(i)\sum_{j|i,j\ne i}\mu(j)\\ &=\sum_{i=2}^{V}-\mu(i)F(i) \end{aligned} $$ 这样本来 $O(V\log \log V)$ 的高维差分就变为 $O(V)$ 了。 --- 而 $o=1$ 只需更改 $F(d)$，因为取出就不放回，容易得到 $$ \begin{aligned} F(d)&=\sum_{i=1}^{cnt_d}\frac{(n-i)!}{n!}\frac{cnt_d!}{(cnt_d-i)!}\\ &=\sum_{i=1}^{cnt_d}\frac{\binom{cnt_d}{i}}{\binom{n}{i}}\\ &=\frac{cnt_d}{n-cnt_d+1} \end{aligned} $$ 用了组合恒等式，但事实上已经可以 $O(nd(V))$ 求了。 ### C 何意味。 ### D 何意味。 ## 2025.10.23 http://oj.daimayuan.top/contest/410 ### B 考虑二分答案，然后根据下标奇偶贪心选。 ### C 不妨设 $f(u,x)$ 是二次函数，则 $f(u,x)=\min\{(x-x_1)^2+(x-x_2)^2+f(l,x_1)+f(r,x_2)\}$，容易得到 $x_1$ 和 $x_2$ 的取值，并能归纳证明其为二次函数。 ### D 考虑倒着 dp。然后就能单侧递归线段树了。 ## 2025.10.24 https://vjudge.net/contest/759551 ### H 考虑判定 $k$ 是否可行。容易想到从大到小枚举 $i$，维护一个 $p$ 表示需要 $p$ 个 $[0,i]$，如果 $cnt_i<p$，则还额外需要 $p-cnt_i$ 个 $[0,i-1]$ 拼成 $i$；否则能多出 $cnt_i-p$ 个数，考虑将它们变为 $0$ 并加到 $cnt_0$ 中。则最终合法当且仅当 $cnt_0\ge p$。 答案具有单调性，所以只需要 check $O(n)$ 次，考虑加速这个过程。用线段树维护一下 $cnt$，如果区间最小值已经 $\ge p$ 了，那么一定可行；否则如果区间右端点 $r$ 乘 $p$ 大于当前数的个数，那么也一定不可能。分析一下时间复杂度是 $O(\sqrt n)$ 的。 ## 2025.10.25 http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=3396&tid=I ### B 贪心假了，考虑 dp。设 $f_i$ 表示权值为 $i$ 的字符串个数，容易发现有 $f_i=f_{i-1}+f_{i-2}$，考虑对着这个 dp。设 $f_{i,j,p,q}$ 表示现在考虑到第 $i$ 个数，当前和为 $j$，和为 $j$ 的有 $p$ 个未用，$j-1$ 的有 $q$ 个未用。则 $f_{i-1,j,p,q+1}+(j-1)a_i\to f_{i,j,p,q}$，$f_{i,j,p,q}\to f_{i,j+1,q,p+q}$。 然后可以费用提前计算，将 $j$ 一维去掉，时间复杂度 $O(n^3)$。 ### C 考虑找到一段最小前缀 $1\sim i$，满足恰好 $i$ 个数各出现了 $3$ 次，则此时答案一定是 $i$ 个数中的任何一个，并且后面的数由于到不了前面所以不可能是答案。 或者考虑建图，当一个点和链头在一个强联通分量里时合法，然后进一步发现强联通分量对应若干区间。 反正就是可以做了。 ### D 考虑分治，然后是二维偏序。 考虑修改，注意到一个 $\max$ 只会对应修改一个 $x$ 的答案，然后又是二维偏序，差分一下就做完了。时间复杂度 $O(n\log^2 n)$。 ## 2025.10.28 http://oj.daimayuan.top/contest/414 ### A 首先可以任意交换行列，所以可以变成下图若干 L 形。 ![](https://s2.loli.net/2024/08/17/dzxSRmhFBsAv7Gf.png) 每个 L 是独立的。对于单个数考虑**容斥**，钦定第 $i$ 行第 $j$ 列是不合法的，方案容易计算，这样时间复杂度是 $O(n^2\log n)$ 的。 一种方法是直接将上面做法其中一维二项式定理化简一下，另一种是只对行或列容斥，则需要求另一维保证合法，方案易算。 ### B 10.21 D。 等价于最近异色点距离 $-1$。经典地， - $|c_i-c_j|\le 1$。 - 存在相邻的点 $c_j=c_i-1$。 因为 $b$ 是递增的，所以可以去掉第二个限制，然后直接 dp 即可。 ### C 垃圾卡常题，傻逼出题人。 ## 2025.10.29 http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=3396&tid=T ### NOIP A 好题啊。考虑将序列变成 $01$，向右记为 $1$，向上记为 $0$，容易发现答案写成了 $$ \begin{aligned} \sum_{i=1}^{n}a_i\left(i-\sum_{j=1}^{i}a_j\right)&=\sum_{i=1}^{n}a_ii-\frac{\sum_{i=1}^{n}a_i\sum_{j=1}^{n}a_j+\sum_{i=1}^{n}a_i^2}{2}\\ \end{aligned} $$ 枚举状态，简单的维护 $1$ 的下标和、$1$ 的个数便可做到 $O(1)$ 转移，时间复杂度 $O(2^m)$。 ### CSP-J A ![](https://cdn.luogu.com.cn/upload/image_hosting/scs3tzdz.png) 好题啊。记 $n'=n/\gcd(n,m)$，$m'=m/\gcd(n,m)$，容易发现答案写成了 $$ \left\{\begin{matrix} \frac{1}{2} & n'\text{ or }m'\text{ is even}\\ \frac{n'm'+1}{2n'm'} & \text{otherwise} \end{matrix}\right. $$ 由于是 J 组模拟赛，所以不需要证明。 ## 2025.10.30 http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=3396&tid=X ### B 考虑贪心。对于点 $u$，往儿子走肯定是最优决策，因为不会对祖先结构产生影响。如果不行，再考虑往父亲走，并把 $a_u$ 贡献到 $a_{fa}$ 上。否则只能自己作为出口。 判断能否往子树走只需开个数组简单处理即可。 ### C 首先处理出 $f_{i},g_i$ 分别~~哦啊哈斯~~表示前后缀的答案，现在要求包含 $i$ 的答案。先考虑不包含 $i$，由经典结论可得前缀和后缀不同 $\gcd$ 种类数只有 $O(\log V)$ 个，可以二分+st表处理得到若干个区间。 现在问题变为给 $a_i$ 赋值，使得包含 $i$ 的区间最多，这个问题可以规约到矩形并，没有很好的做法，考虑直接枚举 $a_i$ 的值。直接枚举相当于枚举 $\text{lcm}(a_{i-1},a_{i+1})$ 的因数，但是事实上发现注意到有用的只有 Square-free，于是枚举量变成 $O(2^{\omega (\text{lcm}(a_{i-1},a_{i+1}))})=O(2^{11})$。再注意到对于 $a_{i-1}$ 独有的质因数，要么不选要么只选一个，$a_{i+1}$ 同理。所以枚举量再变为 $\max\{O(2^{x}(7-x)^2)\}(0\le x\le \omega(\gcd(a_{i-1},a_{i+1}))=6)=144$。显然跑不满。 枚举之后，只需要再枚举左端点所在区间，用双指针扫最右边合法区间，理论时间复杂度为 $O(\log^2 V)$，跑不满。所以总时间复杂度为 $O(144n\log^2 V)$。 ### D 好题。首先发现关键性质，一个数只会先除若干次，再乘若干次，所以考虑设 $f_{i,j,k}$ 表示 $a_i$ 除了 $j$ 次，乘了 $k$ 次且前 $i$ 个数合法的最小代价，其中 $j$ 是 $O(\log m)$ 级别，$k$ 不好分析，但是据说是 $O(\log n\log m)$ 级别的，转移双指针 $O(1)$。所以朴素 dp 时间复杂度是 $O(Tn\log n\log^2 m)$ 的。 问题出在每个数的上界，考虑答案序列一定是一段 $\le m$ 的前缀 + $>m$ 的后缀。于是先将 $f_{i,j,k}$ 限制到 $m$ 以内，再设 $g_{i,j}$ 表示 $a_i$ 除了 $j$ 次，且后缀合法的最小代价。其中不需要知道乘了多少次，因为一定是乘到第一次 $>m$ 停止。转移只需枚举 $g_{i+1,k}$，要注意当 $i+1$ 除 $k$ 次第一次 $>m$ 的数小于 $i$ 除 $k$ 次第一次 $>m$ 的数的时候，意味着 $i+1\sim n$ 每个数都要 $\times 2$ 来保证合法。 合并显然，时间复杂度 $O(n\log^2 m)$。 ## 2025.11.1 CSP-S ### C 除开 $s_1=s_2$ 和 $|t_1|\ne |t_2|$，考虑将所有字符串变成 $(a_i+b_i+c_i,a_i+b_i'+c_i)$ 的形式。 对于询问 $(A+B+C,A+B'+C)$，则合法的方案需要满足 - $b_i=B$，$b_i'=B'

对于第一个，可以通过哈希确定类别。对于第二个，由于其前缀后缀关系，考虑对于每一个类别分别建出前后缀字典树。令 a_i 在后缀字典树上的节点为 p_i，b_i 在前缀字典树上节点为 q_i，那么条件变为

容易通过离线+树状数组做到 O((n+q)\log n)。

D

经典地，设 f_{i,j,k} 表示考虑了 1\sim i 天，有 j 个人离开，有 k 个人 c\le j，并经典地考虑系数提后计算，即只考虑了 c\le j 的系数。转移显然。

具体地，当 s_{i+1}=1 时，分这个人 c\le j 还是 >j 考虑，如果选的 >j，直接转移到 f_{i+1,j,k} 即可。否则由于 j\to j+1，需要枚举前面有多少个 c=j+1 的，即 f_{i,j,k}(pre_{j}-k)\binom{cnt_{j+1}}{l}\binom{i-j}{l}l!\to f_{i+1,j+1,k+l+1}。

## 2025.11.4 http://oj.daimayuan.top/contest/417 ### B 首先知道答案是 $0$ 的列数和 $1$ 的行数的最大值，然后再发现两个至少一个会取到极值，即 $m$ 和 $n$。不妨设 $n\ge m$。 考虑设 $f_{i,j}$ 表示考虑前 $i$ 行，有 $j$ 行有 $1$ 的方案数，那么答案容易表示为 $\displaystyle \sum_{i=0}^{n}f_{n,i}\max(i,m)$，直接做时间复杂度是 $O(n^2)$ 的，考虑到我们只需要求出 $\displaystyle \sum_{i=0}^{m}f_{n,i}$ 和 $\displaystyle \sum_{i>m}f_{n,i}i$，前半部分可以直接 $O(nm)$ 求，考虑容斥求后半部分。 注意到 $\displaystyle \sum_{i=0}^{n}f_{n,i}i$ 是好求的，只需对于每一行算贡献，那么再减掉 $\le m$ 部分就算出答案了。 ### C 好题啊。观察可得，问题不弱于一般图 $k$ 染色方案数，虽然是 NP 的，但是有确定的 $O(n^3)$ 多项式时间复杂度。 但是我们发现这张图竟然是一个弦图！！！然后就做完了。 ### D 思考可得是回滚莫队。 ## 2025.11.5 https://vjudge.net/contest/763875 ### D 注意到对于一个子序列，如果最后一个元素不是最大值，那么将它删除一定不劣。所以枚举最后一个元素就做完了。 ### C 考虑不进行任何操作的根的序列，假设 $u$ 是第 $i$ 个数。然后考虑如何刻画将一个数 $v$ 权值变为 $0$，事实上就是将前 $i$ 个数在 $v$ 子树里的点都删掉，因为只会在最后加入 $v$，自然包括它的子树。显然 $v$ 不能是 $u$ 的祖先。 那么问题就变为从前往后扫，链修改，查询非链权值最大值，用树剖容易解决。 ### F 考虑每个人最终会停留在一个位置，考虑枚举这个位置。 又因为只关心最大值，所以每个位置最优的肯定是左边和右边第一个人。 ## 2025.11.6 http://oj.daimayuan.top/contest/418 ### B 双指针写假了、、、 每次移动左端点，check 能否移动右端点 vs 每次移动右端点，移动左端点直到合法 谁能赢？？？ 注意到第一种写法一个点会被 check 多次，而第二种写法保证了每个点被加入和删除一次。 事实上能用第二种方法的前提是能动态维护全局合法性。 ### C 注意到是 ``管乐部的练习时间快到了，你也尽快离开较为妥当哦。`` 记 $a$ 最大的点编号为 $i$，那么对于 $b_j>a_i$ 的点一定不会被删除，记数量为 $x$。那么答案要么为 $x$，要么为 $x+1$。先判掉 $b_i>a_i$ 的情况，那么考虑找到一个 $b_j$ 尽量小的使得能打败 $i$。 注意到等价于将覆盖 $(b_j,a_j]$，找到 $a_i$ 往前第一个是 $0$ 的位置即为 $b_j$ 最小值。比较显然。 ## 2025.11.7 https://vjudge.net/contest/763877 ### J 容易发现当图中有长度为 $3$ 的链就不合法。考虑如何去刻画，对于点 $u$，记 $(i,j)$ 表示链上它前面有 $i$ 个点，且它为第 $j$ 个点，$j=i$ 表示不选这个点，否则 $j=i+1$。那么对于每个点，其状态只能为 $(0,0),(0,1),(1,1),(1,2),(2,2)$ 之一。 于是这就是一个切糕模型，对于点 $u$，当它选择 $j=i$ 的状态时有 $1$ 的代价，且对于 $v$ 如果满足 $a_u\mid a_v$，那么还要求 $v$ 选的状态 $(i',j')$ 需要满足 $i'\ge j$，即当 $i'<j$ 时有 inf 的代价。 ### I ### H 直接做是一个最大树形图，并且边数很多，考虑转换一下。将边权设为 $a_u+a_v$，并且视为无向图，容易发现在原来的树形图上当每个点作为儿子时会被多算一次权值，于是对于每个连通块，需要钦定一个根将它权值加回来。 但是注意到有可能会出现不选一条边使其连通块数量 +1 从而权值和变大的情况，考虑**增加一个 $a=0$ 的虚点**，于是发现钦定根和这个问题直接就解决了，于是现在问题就在于求出最大生成树。 Boruvka 可以直接做，但是有基于边权性质的 $O(3^{18}\alpha(n))$ 做法。因为有边当且仅当 $a_i\text{ AND }a_j=0$，那么此时 $a_i+a_j=a_i\text{ XOR }a_j$，于是考虑直接从大到小枚举边权，那么再枚举子集就是对的。由于一种边权可能有多的，再维护连通块的数量就行了。 ### F ### C ## 2025.11.8 http://oj.daimayuan.top/contest/420 ### D 好题啊。 不妨设 $\overline{b_1\cdots b_ka_k\cdots a_1}x=\overline{a_1\cdots a_kb_k\cdots b_1}$。比较显然的是 $1\le x<k$。 考虑从两边往中间填，先枚举倍数。如果填了 $a_1\sim a_i$ 是容易算出 $b_1\sim b_i$ 并知道 $a_i$ 会向 $a_{i+1}$ 进多少位，以及 $b_{i+1}$ 需要向 $b_i$ 进多少位。于是设 $f_{i,j,k}$ 表示从低往高考虑到第 $i$ 位，第 $i$ 位向 $i+1$ 位进了 $j$ 位，第 $n-i$ 位需要向第 $n-i+1$ 位进 $k$ 位。 如果直接枚举状态和第 $i+1$ 位填什么时间复杂度是 $O(k^3\log_k n)$ 的，再加上枚举倍数就是 $k^4$ 了。事实上发现只需要枚举第 $i+1$ 位填 $a$ 和第 $i$ 位向第 $i+1$ 位进了 $j_1$ 位，然后就能求出 $b$ 和第 $i+1$ 位会向第 $i+2$ 位进 $k_1$ 位，进而知道第 $n-i$ 向第 $n-i+1$ 位的进位 $j_2$ 和第 $n-i$ 位需要第 $n-i-1$ 进 $k_2$ 位。所以便由 $f_{i,j_1,j_2}\to f_{i+1,k_1,k_2}$。 然后需要分讨长度为奇偶的情况，以及当长度恰好为 $\log_k n$ 时还需记录 $0,1,2$ 表示高位 $<$、高位 $=$ 低位 $\le$、高位 $=$ 低位 $>$，类似数位 dp 的 limit。合并差不多。 一个卡常小技巧是对于一个进制，有一些倍数一定不存在，可以打表出来不枚举即可。 ## 2025.11.10 https://vjudge.net/contest/765335 ### D 容易通过两次询问 $[1,n]$ 和 $[n,1]$ 得到每个点的度数 $d_i$。还原一棵树，考虑剥叶子，并且为了得到父亲的编号，考虑求出每个点的邻居编号异或和或者和之类的。 考虑按二进制位考虑，记 $s_0,s_1$ 分别表示这一位为 $0$、$1$ 的集合，那么通过查询 $s_0s_1$ 和 $s_1s_0$ 便容易得到一个点邻居这一位的和，这样查询次数是 $2\log_2 n+2=34$ 的，但是查询最高位一定可以得到 $[1,n]$，所以可以减一次。 但是还是过不了，考虑换成 $3$ 进制，那么次数就变为 $3\log_3 n+1=31$ 了。 --- $k\log_k n$ 都可以考虑一下 $k=2,3$ 甚至是 $4$。 ### F 比较 tricky。考虑将每个数减去 $B=\lfloor\frac{m}{n}\rfloor$，$m$ 变为 $m\bmod n$，这跟原问题显然是等价的，并且每个数 $\in [-B,n-B]$ 且 $m\in [0,n)$。 然后就有结论：假设存在一种顺序 $\sum_{i=1}^{n}a_i=m$，那么一定可以通过对 $a$ 重新排列使得对于 $\forall 1\le p\le n$，使得 $\sum_{i=1}^{p}a_i\in[-n,n]$。 可以通过构造式证明，更一般的，如果 $\sum_{i=1}^{n}a_i=x\in[l,r]$，且 $a_i\in[l,r]$，也一定存在重排使得任意前缀和 $\in[l,r]$。设当前前缀和为 $s$，如果 $s\ge 0$，那么如果有 $<0$ 的数则加上，否则任意排列一定合法；如果 $s<0$，有 $>0$ 的数则加上，否则任意排列一定合法。 注意到加的数最大为 $r$，最小为 $l$，所以加上后和依然合法。 那么这道题只需要保留 $x^{-n}\sim x^{n}$ 的点值求出 $[x^m]f^n$，ntt 即可。并且此题只需要保留 $0/1$ 值。 ## 2025.11.11 http://oj.daimayuan.top/contest/423 ### B 考虑这个答案 $f(n,k)$ 可以递归算，假设其左子树大小为 $sl$，右子树大小位 $sr$，那么 $f(n,k)=f(sl,k)+f(sr,k)+n$，比较显然。 再注意到 $sl$ 一定为 $k^p$，并且可以得到 $sr\in[k^{p-1},k^{p+1})$。并且可以通过分析得到对于固定的 $n$，$sr$ 只会对应一个 $sl$。大概是考虑如果对应 $k^{p-1}$ 或 $k^{p+1}$ 会引起矛盾。 所以现在问题就变为求 $f(k^p,k)$，这个是容易计算的（也是采取递归），然后如果每次只往右子树走一步时间复杂度是不对的，考虑直接走完左儿子相同的右链，然后加上一个等差数列。这条链的大小也是容易计算的。 ### C 考虑 $k$ 进制按位考虑。 ![](https://cdn.luogu.com.cn/upload/image_hosting/07clvzud.png) 这是一个 $3$ 进制构造，$n=2\times 3^0+1\times 3^1+2\times 3^3$，相当于对每个长度为 $3$ 的子结构在其对应位上的值后插入一个点。注意到最后一个子结构不需要完整。所以构造次数大概是 $O((k+1)\log_k n)$ 的。$k$ 取 $4$ 时卡常可以得到 $291$ 次。 考虑混进制，因为 $5\times 4^{57}\ge 10^{17}$，最高位只需要保留对应位上的值的个数。所以次数是 $5+4\times 56+57+3=289$ 的。 ### D 考虑按 dfn 序 dp，并继承重儿子，时间复杂度 $O(nm\log n)$。 ## 2025.11.12 http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=3396&tid=e ### B 星战。 ### C 还不会。 ### D 看官方题解吧。https://atcoder.jp/contests/agc061/editorial/5697 好像比较依托。考虑已经匹配了 $0\sim k-1$。如果 $k-1$ 并没有向 $k$ 进位，那么第 $k$ 位的值是只跟异或集合的奇偶型有关的。 而对于进位，一定会变为 $0\sim k-1$ 全 $1$ 然后通过 $+1$ 操作进位的，然后 $0\sim k-1$ 全 $0$，之后再考虑匹配 $0\sim k-1$。事实上这就变成了一个子问题。 考虑设 $f_{k,s,t,u}$，表示匹配了 $0\sim k-1$，初始状态为 $s$，异或集合为 $u$，到结束状态为 $t$ 的最小花费。这个东西之所以是从低往高 dp 是因为调用进位操作时需要知道更低位子问题的答案。再观察到，初始状态根据前文所说是只需记录 $S$ 和全 $0$，结束状态只需记录 $T$ 和全 $1$。 考虑怎么转移，先考虑不向第 $k$ 位进位直接匹配，即通过状态算出第 $k$ 位的值已经和结束状态匹配了。 否则从 $s$ 到 $t$ 会进位，考虑整个过程，它是有可能会进位多次（因为可能会被异或掉）的，而进位体现在变为状态为全 $1$ 后 $+1$，所以本质上是从 $s$ 变到（变的过程会异或，也可能会 $+1$，但是为了后续能进位，要求第 $k$ 位能被异或掉）全 $1$，然后 $+1$，变成全 $0$，然后变到全 $1$（变的过程同理）然后 $+1$……变到全 $1$，然后 $+1$，变成全 $0$，然后变到 $t$。 其中变的过程是可能进行若干异或和 $+1$ 的，但是只要没有向第 $k$ 位进位，那么第 $k$ 位的值是只跟异或集合有关的。 考虑以每次向第 $k$ 位进位操作为界将它分割为若干子问题，最开始形如 $s\to 1$（$s$ 变到全 $1$），中间形如 $1\to 1$（全 $0$ 变到全 $1$），结尾形如 $1\to t$（全 $0$ 变到 $t$），以 $+1$ 操作连接子问题并要求 $+1$ 操作前第 $k$ 位能被异或掉。 形式化的，$f_{k,1,1,s}+A\to f_{k,1,1,s'}$ 合法条件为 $s'$ 的第 $k$ 位为 $1$（将这位异或掉），然后开头和末尾判一下即可。发现转移有环，所以需要类似 dijkstra。 ## 2025.11.13 ### B 考虑朴素 dp。如果 $f_{i-w_j}+v_j>f_i$，则 $f_i\to f_{i-w_j}+v_j,g_i=g_{i-w_j}$；否则如果 $f_{i-w_j}+v_j=f_i$，则 $g_i\to g_i+g_{i-w_j}$。 然后发现这个本质是就是对于二元组 $(a,b)$ 重载运算符，抉择等价于 $\bigoplus$ 操作，$+v_j$ 等价于 $(f_{i-w_j},g_j)$ 与 $(v_j,1)$ 进行拼接于是等价于 $\bigotimes$ 操作。 赛上只想了 $v=w$ 的矩阵（单元），感觉二元还是比较神秘。其实成熟的选手看到转移后应该就想到矩阵了。 ### D ## 2025.11.14 https://vjudge.net/contest/765906 ### A 考虑从部分分思考。对于链的性质，$1$ 只会有两条支链，那么一个集合最优肯定是一左一右，每次贪心取出左右 max 合并即可。 这启发我们对于多儿子的情况，只需将每个儿子存的堆合并，这一部分用启发式合并即可。感觉上时间复杂度加上堆是 $O(\log^2 n)$ 的，但是因为这里的合并并不是大小相加而是大小取 $\max$，小的直接舍弃掉了。所以每个元素只会被 pop 一次，时间复杂度就是 $O(\log n)$ 的。 ### B 有一个想法，对于左端点 $l$ 找到最远的一个 $r$ 使得 $[l,r]$ 没有一个数出现两次。然后钦定这段区间不动，让没有出现的数移至两端。发现这是不好做的，因为无法确定左右两边移动数的个数，导致贪心可能有后效性。 所以直接钦定一个元素 $p$ 不动且恰好为第 $\frac{k}{2}$ 个元素，容易发现这样钦定显然是存在一种最优解的。这样后，我们就知道了左右两边移动数的个数，记 $l_i$，$r_i$ 分别表示 $i$ 在 $p$ 左侧第一个和右侧第一个到 $p$ 的距离，那么相当于要在两边分别选 $\frac{k}{2}$ 个不同的数，使得 $\sum l_i+\sum r_i -C$ 最小，其中 $C$ 由于确定了左右两边数的个数所以是确定的。 注意到可以直接去掉个数限制，因为当左右数量不均时，算出来的答案是一定比正确答案更劣的，而正确答案又会在中点处被考虑到。所以问题直接变为 $\sum \min(l_i,r_i)$。这个东西可以直接二阶差分算贡献，所以时间复杂度是 $O(n)$ 的。 ### C 操作的本质是交换相邻逆序对。所以容易发现对于每个数 $a$，如果另一个数 $b$ 在 $A$ 中在其前面且 $b<a$，那么在 $B$ 中也要求 $b$ 在 $a$ 前面，因为无法跨过。 记 $a_0$ 为 $a$ 在 $A$ 中的位置，$a_1$ 为 $a$ 在 $B$ 中的位置，则要求对于每个 $a$ 需要满足 $\displaystyle a_1>\max_{b_0<a_0\land b<a}b_1$。 先判掉已经填好位置的 $a$ 是否满足，于是我们就可以对于每个没填的 $a$ 求出一个合法区间 $[l_a,r_a]$，问题变为给每个位置分配 $a$ 使得满足所有条件。 这个问题可以贪心去做，考虑 $i$ 从小到大，即对于一个 $c_i=0$ 的位置 $i$，找到 $l_a\le i$ 里最小的 $r_a$，$r_a<i$ 显然无解，否则就直接匹配。 相当于去匹配最劣的，那么留给后面的就更优了。或者说 $r$ 越小剩余可用的就越小，那么就越紧迫，就越需要匹配。 这样匹配显然满足本身 $c_i\ne 0$ 和 $c_i=0$ 之间的限制，考虑 $c_i=0$ 之间的限制。注意到如果 $b<a\land b_0<a_0$，那么 $l_b\le l_a\land r_b\le r_a$，只需当 $r$ 相同时取 $id$ 最小的。所以这样贪仍然是对的。 ### D 贪心放，一定是最大、最小、次大、次小……证明考虑如果最大不在第一位，那么翻转 $[1,pos]$ 一定合法且更优。其他同理翻转可证。 因为对于 $x>\sqrt k$，只能跟 $\le \lfloor\frac{k}{x}\rfloor$ 放在一起。考虑变成对于 $\forall i\le \sqrt k$ 都需要有 $cnt_{\ge \lfloor k/x\rfloor}\le cnt_{\le x}$。这个是充要条件。但是有一个 conner case，当 $n$ 是奇数时，$cnt_{\le x}$ 可以为 $\frac{n-1}{2}$，所以只需让 $\frac{cnt_{\ge \lfloor k/x\rfloor}-cnt_{\le x}+1}{2}$ 跟 $\lfloor\frac{n}{2}\rfloor-cnt_{k\le x}$ 取 $\min$。因为卡空间所以可以分块或者莫队。 ### F 容易发现 $|A|=\lceil \frac{s-1}{2}\rceil=T$，因为如果 $i\in A$，则要求 $s-i\notin A$。所以上界是 $T$，并且构造 $A=\{T+1,\cdots,s-1\}$ 是合法的。 令 $A$ 中 $\le T$ 的元素构成集合 $B$，那么已知 $B$ 是可以推出 $A$ 的，可以证明若 $B$ 合法则 $A$ 一定合法，然后考虑让 $B$ 字典序最小。 不太会。 ### G 将 $0$ 看作 $-1$。考虑将前缀和变成折线。那么不平衡度就是前缀和的极差即这个折线的宽度。考虑固定折线的上端点值为 $m$ 求出其下端点的最大值 $f(m)$。不妨先将所有 ? 都填上 $-1$，然后考虑调整。肯定是贪心的从前往后能将 $-1$ 变 $1$ 就变，判一下后缀 max 即可。 如果直接枚举最大值时间复杂度是 $O(n^2)$ 的。注意到 $f(m+2)\le f(m)+2$，所以更大不优，只需考虑最小的两个值即可。 证明你去问一下 wxir。wxir 说最多将一个 $-1$ 改为 $1$。 ### I 数结果<->数操作序列。让其一一对应，贪心找到方案。 如果没有 $3$，那么操作只能让一段长度 $-1$，方案即为长度乘积。考虑有 $3$，找到其位置，两个 $3$ 之间的段可以任意保留子段（因为两边可以合并）。开头和结尾分别是前后缀。 ## 2025.11.15 http://oj.daimayuan.top/contest/426 ### D 考虑每个数从高到低会经过和 $l,r$ 都相同、和 $l,r$ 其中一个相同、无限制三个阶段。 考虑对于第 $k$ 位，如果已知区间 $[i,j]$ 第 $i$ 和 $j$ 个数这位的值 $u,v$，并且 $[i+1,j-1]$ 无限制，是容易预处理出这一段的答案 $val_{k,i,j,u,v}$。 然后考虑从高位到低位填，每一位是能拆成若干个上述区间的，即若干数这一位固定，之间的数无限制。并且注意到填第 $k$ 位时，要么继承第 $k+1$ 位的区间（即仍然抵着 $l$ 或 $r$），要么将多个区间合并（即中间端点到了第三阶段）。于是考虑设 $f_{k,i,j,0/1,0/1}$ 表示考虑了 $k\sim m-1$ 位，第 $i$ 个数跟 $l/r$ 抵着，第 $j$ 个数跟 $l/r$ 抵着，区间 $[i+1,j-1]$ 无限制的答案。 于是一种转移是直接继承，$f_{k,i,j,s,t}\to f_{k+1,i,j,s,t}+val_{k,i,j,p_{i,s,k},p_{j,t,k}}$。其中 $p_{i,0/1,k}$ 表示 $l_i/r_i$ 第 $k$ 位的值。否则就是合并若干区间，为了实现多次合并，记 $g_{k,i,j,s,t}$，和 $f$ 类似，但是 $j$ 的 $k+1\sim m-1$ 位抵着，而第 $k$ 位变成无限制的答案（记 $pos_i$ 表示 $l_i$ 和 $r_i$ 最高的位，使得到 $m-1$ 位都相同。容易发现其合法条件是 $k<pos_j-1$（$<pos_j$ 才能进入第二阶段，所以 $<pos_j-1$ 才能进入第三阶段）且如果 $t=0$，那么要 $p_{j,t,k}=0$ 且这一位填 $1$；$t=1$ 要 $p_{j,t,k}=1$ 且这一位填 $0$。因为要变得无限制。）。 那么有 $f_{k,i,j,s,t}=\min g_{k,i,mid,s,w}+f_{k+1,mid,j,w,t}+val_{k,mid,j,1-p_{mid,w,k},p_{j,t,k}}$。 然后当满足上述条件时，$g_{k,i,j,s,t}=f_{k+1,i,j,s,t}+val_{k,i,j,p_{i,s,k},1-p_{j,t,k}}$，并类似 $f$ 合并一下即可。 ## 2025.11.17 https://vjudge.net/contest/767392 ### G 考虑到如果一开始合并到 $k$ 个数 $(a_i,b_i)$，如果存在某个 $i$ 满足 $a_i-tb_i\le 0$ 是没啥用的，不如跟其他数进行合并。所以不妨假定对于所有 $i$ 都满足 $a_i-tb_i>0$。 于是变成最大化 $\displaystyle \sum_{i=1}^{k}a_i-t\sum_{i=1}^{k}b_i$，观察其合并形式，所以 $a$ 肯定会取前 $k$ 大，$b$ 取前 $k$ 小。所以新增的 $a$ 越来越小，新增的 $b$ 越来越大，只需二分到第一个 $a\le tb$ 的位置，然后前缀和计算答案即可。 当然可以排序后离线做到线性。 ### H 考虑枚举 $i_2$ 和 $j_3$，相当于分成两部分，一部分是统计 $([i_1,j_1],[i_4,j_4])$ 个数，这个可以用二维前缀和；另一部分是统计 $i'>i_2$ 的 $([i',j_2],[i_3,j_3])$ 个数，也可以类似前缀和。 于是现在要求 $f_{i,j}$ 表示 $i$ 开头 $j$ 结尾的 $([i,i'],[j',j])$ 个数且区间不交。直接求不好，考虑枚举 $i$ 和 $j'$，那么求一下 $[i,n]$ 和 $[j',n]$ 的 lcp，变成了区间加，差分一下即可。 或者利用**border**的等差性质，或者倍增跳 fail 之类。 ### I 结论：割点且相邻点双非“一条边”。但是我不会 tarjan，也不会 trajan。 ### A & D 袋鼠题。比较 $ab$ 和 $ba$ 考虑比较 $a^{\infin}b^{\infin}$ 和 $b^{\infin}a^{\infin}$。 ## 2025.11.18 http://oj.daimayuan.top/contest/427 ### C 考虑三种构造方式。记 $A$ 为 $a$ 中非 $0$ 个数，$B$ 为 $b$ 中非 $0$ 个数。 - 将所有水倒到 $n$，然后从后往前倒，变成全 $1$ 局面，然后将 $b_i=0$ 的倒向 $a<b$ 的位置。次数为 $A+n+n-B$。$A$ 多了就炸了。 - 如果 $a_i=0$，从 $1$ 倒水，如果 $1$ 没水找一个 $a>1$ 倒向 $1$。变成全 $1$ 局面，后续同一。次数为 $2(n-A)+n-B$。$B$ 多了就炸了。通过前两种方式可以通过 $b_i=1$。 - 将所有水倒到 $n$，然后从后往前，如果 $b_i>0$ 那么 $n$ 倒向 $b_i$ 再倒向 $i$，次数为 $A+2B$。 三种方式和为 $5n$，所以不可能同时大于 $\lfloor\frac{5n}{3}\rfloor$。 第四种构造 - 将 $a_i$ 分成 $\le 2$ 和 $>2$，记 $\le 2$ 的和为 $A$，将 $>2$ 的全部倒向位置 $n-A$，将 $1\sim n-A-1$ 里 $a_i\ne 0$ 的位置平移到 $n-A$ 后面。从 $n-A$ 从后往前倒，$1\sim n-A$ 变为全 $1$。$n-A$ 后面的通过位置 $1$ 变为全 $1$。 - 非常垃圾，记 $=2$ 的个数为 $B$。$b_i$ 全 $1$ 时次数为 $\frac{n-A}{3}+n-A+(B+A-2B)+2B<\lfloor\frac{4n}{3}\rfloor$。 ## 2025.11.19 http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=3396&tid=m ### B 考虑如何去刻画第二种操作。将 $i$ 所在的两个位置连边，那么第二种操作就变成了交换一个环相邻两条边。即两个环本质相同当且仅当环上的数构成集合相同。 所以题意转换为将 $1\sim n$ 划分成若干环，不存在一个的点的环。或者说划分成若干集合，不存在一个数的集合。发现很类似于错排问题，考虑容斥。 设 $f_i$ 表示钦定有 $i$ 个单元素集合，那么其他 $n-i$ 个数任意分集合，集合互不区分。即是贝尔数，即是行斯特林数。形式化的 $\displaystyle f_i=\binom{n}{i}B_{n-i}$。再设 $g_i$ 表示恰好有 $i$ 个单元素集合，那么 $\displaystyle f_i=\sum_{j=i}^{n}\binom{j}{i}g_{j}\to g_i=\sum_{j=i}^{n}(-1)^{j-i}\binom{j}{i}f_j$。 所以 $\displaystyle ans=g_0=\sum_{i=0}^{n}(-1)^i\binom{n}{i}B_{n-i}$，下面我们来推式子。 $$ \begin{aligned} ans&=\sum_{i=0}^{n}(-1)^{n-i}\binom{n}{i}B_{i}\\ &=\sum_{i=0}^{n}(-1)^{n-i}\binom{n}{i}\sum_{j=0}^{i}{i\brace j}\\ &=\sum_{i=0}^{n}(-1)^{n-i}\binom{n}{i}\sum_{j=0}^{\color{red}n}{i\brace j}\\ &=\sum_{i=0}^{n}(-1)^{n-i}\binom{n}{i}\sum_{j=0}^{n}\sum_{k=0}^{j}\frac{(-1)^{j-k}k^i}{k!(j-k)!}\\ &=\sum_{i=0}^{n}(-1)^{n-i}\binom{n}{i}\sum_{k=0}^{n}\sum_{\Delta =0}^{n-k}\frac{(-1)^{\Delta}k^{i}}{k!\Delta !}\\ &=\sum_{k=0}^{n}\frac{1}{k!}\sum_{\Delta =0}^{n-k}\frac{(-1)^{\Delta}}{\Delta !}\sum_{i=0}^{n}(-1)^{n-i}\binom{n}{i}k^i\\ &=\sum_{k=0}^{n}\frac{1}{k!}(k-1)^n\sum_{\Delta =0}^{n-k}\frac{(-1)^{\Delta}}{\Delta !} \end{aligned} $$ 后面显然可以前缀和，然后欧拉筛筛一下 $n$ 次方即可。发现上界如果没有改成 $\color{red}n$，不方便后续展开和二项式反演。 --- 注意到 $ans_n+ans_{n+1}=B_n$。可以组合意义证。以上。 ### C $type=1,2,3$ 很简单。$type=4$ 考虑将答案变成 $len-cnt-[cnt=len-1]$。其中 $cnt$ 是 $k$ 的个数满足前 $k$ 个数互不相同且后 $k$ 个数互不相同。因为答案一定是一段前缀 $[1,i]$ 加上一个 $j\ne i+1$ 且 $a_j=a_{i+1}$，后缀同理，稍加变形即为这个。$cnt=len-1$ 时会退化成子串。 $\sum len$ 和 $\sum [cnt=len-1]$ 都是好统计的，考虑统计 $cnt$。枚举 $p$ 和 $q$ 分别表示前缀第 $k$ 个数的位置和后缀第 $k$ 个数的位置，其中 $k$ 具体的值是不需要管的。考虑现在两种情况 - $p\le q$。考虑枚举 $k$，相当于要预处理出 $f_{i,j}$ 表示在前 $i$ 个数选出 $j$ 个互不相同的数且与 $a_{i+1}$ 不同的方案数，$g_{i,j}$ 表示后 $i$ 个数。然后 $p+1\sim q-1$ 中间的数是任意选的，所以这一部分答案就是 $\sum f_{p-1,k}g_{q+1,k}2^{q-p-1}$。时间复杂度 $O(n^3)$。 - $p>q$。比较难搞。分成了三段 $[1,q),[q,p],(p,n]$，对于一种数要么只出现一次在 $(q,p)$，要么只出现一次在 $(p,n]$，要么只出现一次 $[1,q)$，要么出现两次分别在 $[1,q)$ 和 $(p,n]$。其合法条件是最终 $p$ 前面的数的个数和 $q$ 后面的数的个数相同。 所以考虑以 $p$ 前面数的个数减去 $q$ 后面数的个数作为下标跑一个背包，转移相当于从 $f'_i,f'_{i-1},f'_{i+1}$ 转移到 $f_i$。然后最终方案数即为 $f_0$。直接做时间复杂度是 $O(n^4)$ 的，因为背包部分现算时间复杂度是 $O(n^2)$。然后发现 $p,q$ 每次移动只会更改 $O(1)$ 个物品，所以用一下回滚背包（从下至上递推算出），时间复杂度是 $O(n^3)$。 ## 2025.11.20 http://oj.daimayuan.top/contest/428 ### B 先考虑全局操作。考虑将 $0\sim 2^n-1$ 建一棵字典树，那么异或 $k$ 相当于就是从高往低如果这一位为 $1$ 就交换左右子树。 所以这启发我们对于区间异或，拆成 $\log$ 个区间，每个区间有一个低位和高位，对于每个区间异或 $k$ 相当于是高位和低位分别异或 $k$，而我们可以找到高位异或 $k$ 之后对应的原来的区间，相当于是将这个区间复制成原来的区间并打上一个异或 $k$ 的标记。 所以是一个可持久化线段树，由于卡空间所以要写标记永久化。当然可以 $O(\log n)$ 次重构做到 $O(n)$ 空间。 ## 2025.11.21 jzy 神秘作业。 ### A https://www.luogu.com.cn/problem/P12624 考虑到交换操作一定是交换 $h_i-a_i$ 最大的，然后又是区间询问，考虑先建出笛卡尔树。 假设 $u$ 是区间 $[l,r]$ 的最大值，考虑统计 $l'\in [l,u]\land r'\in [u,r]$ 的区间答案。记 $sh_i$ 表示 $1\sim i$ 人类获得的分数，$sa_i$ 表示 $1\sim i$ AI 获得的分数 $\times k$。那么 $[l',r']$ 合法的条件是 $sh_{r'}-sh_{l'-1}-(h_u-a_u)\ge sa_{r'}-sa_{l'-1}+k(h_u-a_u)$。 移项后 $sh_{r'}-sa_{r'}-(k+1)(h_u-a_u)\ge sh_{l'-1}-sa_{l'-1}$。容易用启发式合并+可持久化线段树统计答案。 ### B https://www.luogu.com.cn/problem/P7315 注意到 $k\le n$。当 $k<n$ 时根据鸽巢原理一定有一行为 $0$，所以只需枚举这一行便可确定出列的异或情况，然后通过 bitset 算出其他行 $1$ 个数的最小值，时间复杂度为 $O(\frac{n^3}{\omega})$。 而当 $k=n$ 时排除上述情况，那么只能每一行恰好一个 $1$，只需枚举第一行 $1$ 的所在位置便同理用上述操作判断即可。 ## 2025.11.24 https://vjudge.net/contest/769218 ### E wxr 说先考虑一条直线上的情况。 相当于有 $n$ 个数 $a_i$，如果 $i$ 被标记则选择 $j\ne i$ 将 $a_i$ 变为 $2a_j-a_i$，将标记移到 $j$。因为题目只给出了起始态和终止态，这启发我们不关注具体值，而是全局的变化量。 具体的，当 $a_i$ 变为 $2a_j-a_i$ 时，对全局变化量的影响为 $2a_j-2a_i$，然后把整个过程写出来就是 $2a_{i_1}-2a_{s}+2a_{i_2}-2a_{i_1}+\cdots +2a_{t}-2a_{i_k}=2a_t-2a_{s}$。然后发现变化量只跟最后一次和第一次标记的数有关，然后就做完了。显然两维是独立的，分别看即可。 ### A 考虑按位考虑。设 $f_{i,j}$ 表示考虑了前 $i$ 位用了 $j$ 次操作能组成最多的数字个数。转移只需 $2^7$ 枚举这一位的操作情况，再看能填哪些数。然后 $g_{i,j}$ 记一下方案数。 发现只记这个不够，因为可能有前 $i-1$ 位均为空的情况。所以还要加一维 $01$ 表示是否能全空。有一个特殊情况是如果这一位只能是空，$g$ 要用前面所有（不只是最大值）的方案数转移过来，所以还要记一个 $h$。 ### D ### F ## 2025.11.25 http://oi.nks.edu.cn:19360/zh/Contest/Details/3415 ### H 考虑树的情况，如果确定 $T$ 集合，那么容易发现设 $T$ 中所有点构成虚树的大小为 $x$，那么 $S$ 的数量就是 $2^x$。考虑一般情况，发现是所有点构成虚树上的所有点双的并集。 所以直接建出圆方树，并在虚树的根统计答案。将圆点的权值设为 $0$，方点的权值设为所在点双的大小 $-1$，记为 $w_u$。设圆方树上 $T$ 中所有点的权值总和为 $h(T)$，那么方案数就是 $\sum_T 2^{h(T)+1}=2\sum_T 2^{h(T)}$。 设 $f_u$ 表示虚树以 $u$ 为根时所有方案数之和。那么要至少合并两个子树。因为合并时要算上 $v$ 到 $u$ 链上所有点的权值，所以再设一个 $g_u$ 表示 $u$ 子树中所有 $f_v2^{s(v,u)}$ 的和，$s(v,u)$ 表示 $v$ 到 $u$ 不包含 $v$ 的权值和。 - 当 $u$ 为方点时，因为它对应原树是虚点所以不需要看 $u$ 是否在 $T$ 中。有 $f_u=2^{w_u}(\prod (g_v+1)-1-\sum g_v)$，减掉空子树和单子树的情况，$g_u=2^{w_u}\sum g_v+f_u$。 - 当 $u$ 为圆点时，可以抉择是否在 $T$ 中，并且在 $T$ 时没有子树限制。所以有 $f_u=2(\prod(g_v+1))-1-\sum g_v$，$g_u=\sum g_v+f_u$。 ### J 考虑最后一定是一个二叉树结构，使得所有叶子到根的路径权值和的最大值最小。这个东西可以显然直接区间 dp。设 $f_{i,j}$ 表示考虑 $[i,j]$ 区间的答案，那么有转移 $f_{i,j}=\min\limits_{i\le k\le j}\{a_k+\max(f_{i,k-1},f_{k+1,j})\}$。是 $O(n^3)$ 的。 考虑优化，不考虑 $a_k$，那么 $f_{i,k-1}$ 是递增，$f_{k+1,j}$ 是递减的，考虑找到其交界点 $x$，那么将转移式改写为 $f_{i,j}=\min(\min\limits_{i\le k\le x}\{f_{k+1,j}+a_k\},\min\limits_{x<k\le j}\{f_{i,k-1}+a_k\})$。然后当 $i$ 固定时，随着 $j$ 增大左半区间是滑动窗口，$j$ 固定随着 $i$ 减小右半区间是滑动窗口，所以直接优先队列优化一下即可。 ### A 比较神秘，回文串。 1. 去重。 2. 压缩。 ### B 要么就是具体题目具体分析（ad-hoc），要么就是图论建模（传统题）。 拆点，上下两部分。若干环+链。必要条件 - $len\equiv 0\pmod 8$。 一环一链不用管，否则有若干“两点颜色相同”限制。考虑链接虚边。把每个环当作一个点，建出新图。点染色变为边染色，即将环上的点看作边。 给虚点连自环使得每个点度数模 $8$ 余 $0$，给边 01 染色。注意到度数都是偶数，直接找欧拉回路。 $\# 0\equiv 0\pmod 4$，子问题，再做一遍。 ### E Part 1，有向无环图。删掉多余的不影响图偏序关系的边，就是最优解。念题解了： 再考虑SCC内部的边，接下来的原图为单个SCC。 如果删去 u→v 后不改变原图连通性，则不能变无向边，因为无法确定方向。 否则 u→v 反向后一定改变原图连通性。 因为 u→v 属于一个SCC，所以一定有 v⇝u，只有这上面的边影响 u→v 能否变无向边。 于是考虑删掉 u→v 后所点形成的DAG，其中 u 的出度和 v 的入度一定为 0，再将 u→v 放回去，设这张图为 G u,v ​ 。 每条边都对应一张这样的图，而每张这样的图都与其中SCC集合形成双射，所以一条边可以用一个SCC集合表示。 引理： 若两条边的SCC集合不同，那两条边之间是否删除方向互不影响。 证明： 设两条边分别为 u→v 和 x→y。 因为其SCC集合不同，所以两条边不可能同时在对方缩完点后的DAG上。 若两条边都不在对方DAG上则显然互不影响。 否则设 x→y 在 u→v 的DAG上，也就是 u→v 在 x→y 的DAG上被缩在了一个SCC里面，设其为 A，如果 u→v 最后删向也要先保证 A 的连通性，只要 A 连通，内部边是否删向对 x→y 能否删向没有影响。 同理，在 x→y 的DAG上，x→y 是否删向都要先保证 A⇝x→y⇝A 这条路径只能唯一定向，而 u→v 在 A 中不影响这条路径，所以这条路径在 u→v 的DAG上是固定方向的，与 x→y 是否删向无关。 于是我们可以将SCC集合相同的边分到一组一起考虑，不同组之间互不影响。 对于一组边 E，设这种边的数量为 c1，对应的SCC集合中SCC的数量为 c2，有 c2≥c1。 因为这组边对应的 G 上，存在一个环使得 E 是其边集的子集，且对于非环边 u→v，环上路径 u⇝v 的边集与 E 无交。 若 c2=c1 即环的边集就是 E，那至少要保留一条边有方向，方案数为 ∣E∣−1。 否则 c2>c1 则 E 全都可以删向，方案数为 ∣E∣。 对于不同组的边，由于互不影响，方案数由乘法原理可知相乘即可。 时间复杂度 O(nm)。 --- 讲得好，打 100 分。做完了。 ### C 考虑最小值的位置不会变，所以有可递归性。直接记 $f(l,r,L,R)$ 表示区间 $[l,r]$，左边有 $L$ 个可任意排，右边有 $R$ 个可任意排。然后设区间最小值所在位置为 $p$。 - $p\in [l+L,r-R]$。其位置固定，可以直接递归下去。 - $p\in [l,l+L-1]$。那么 $[l,l+L+c]$ 这些数都是可以任意排的且要求 $p$ 最终在 $[l,l+L-1]$。不妨让 $p$ 放在一边即 $l$ 的位置，然后先递归子任务 $f(l+1,r,L+c-1,R)$，最后再将 $p$ 插入，有 $L$ 的方案数。 ### F 打表找规律，找不到。先分析操作次数，感性理解比较少。大概在若干轮后变成 $01$ 交替，每次操作变成左移一位，懒得分析。所以拆分成 $2$ 个部分：最初->循环移位->结束。如果知道中间状态，最后一部分只需要跑 kmp 即可。 手玩一下，比较复杂。不被阻拦的充要条件是所有后缀 $cnt0\ge cnt1$。结论：循环置换。 ### D 1 分钟讲完。能换说明在边双上。 ## 2025.11.26 http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=3396&tid=r ### C 最终一定是 $A$ 一段，$B$ 一段，$C$ 一段。 考虑枚举 $A$ 和 $C$ 中较小的一段，那么则要求另一边跟其回文，然后可能在前面加一段连续的然后跟 $B$ 的一段组成一个回文。 相当于问题变成求从 $A$ 某个位置开始或以 $C$ 某个位置结尾，在 $B$ 中选一段组成一个回文的方案数。这个可以通过类似的方法，即枚举较短的一段，那么就变成在后缀或者前缀加回文的方案数。 不考虑哈希表，时间复杂度 $O(n^2)$。 --- 把三个串拼在一起，考虑区间 dp。$f_{i,j}$ 表示 $i$ 和 $j$ 匹配，区间 $[i,j]$ 的方案数。转移只需考虑从 $i,j$ 是否需要跳到下一段。然后直接做就是 $n^4$ 的，瓶颈在枚举跳到一段的某个位置，但是只需满足值相同就行了，所以开个辅助数组记录一下即可。 ### D 首先需要注意到答案只会是一条边。然后再注意到只有最小生成树上的边有用，通过破圈法可以证明。 转到树上就好做了，只需维护儿子对某个点的贡献，这个可以用权值线段树直接做。