一句话题解

不能什么题都随便写写就过了，留点印象好一点。一直更新。

顺便看看 CSP（10.26）到 NOIP（11.30）这段时间能刷多少题。

如果想看某道题的题解可以 Ctrl + F 搜索关键字，也可以在目录里找。

关于题目难度评级：

Easy：完全独立切掉。
Medium：看了题解茅塞顿开并切掉。
Hard：看了题解磨了好久才切掉。

[TOC]

2024.10.29

ABC290F

Medium

组合数数。满足树的形态要有 $\sum deg_i=2n-2$。考虑目前有 $k$ 个儿子节点，直径最大肯定是 $n-k$ 个非儿子点串一条长度为 $n-k+1$ 的链，然后再挂儿子节点。总度数 $2n-2$，给 $n-k$ 个非儿子节点支配的还剩 $2n-2-k$，易得插板：$\binom{(2n-2-k)-2(n-k)+(n-k)-1}{(2n-2-k)-2(n-k)}=\binom{n-3}{k-2}$。答案即为：$\sum\limits_{k=1}^n \binom{n}{k}\binom{n-3}{k-2}(n-k+1)$。

根据吸收恒等式（$k\binom{n}{k}=n\binom{n-1}{k-1}$）和范德蒙德卷积（$\sum\limits_{i=0}^k\binom{n}{i}\binom{m}{k-i}=\binom{n+m}{k}$）可以化简成 $O(1)$：$Ans=(n-1)\binom{2n-3}{n-1}-(n-3)\binom{2n-4}{n-1}$。

ARC156C

Medium

构造。观察可得价值最小无论如何都是 $1$。方向转为构造排列。观察树是链的情况，排列直接为序号翻转过来。考虑树普通情况，每次取两个叶子节点交换序号即可。类似拓扑地，可以处理至原树变成一条链。

正确性证明：一条 $u\to v$ 的简单路径，路上的编号大概形如 $v\to u$ 的路径的编号。刚好是完全相反的，满足了 LCS 为 $1$。

2024.10.30

Luogu P5749 [IOI2019] 排列鞋子

Medium

贪心。对于每种大小用 vector 存鞋的位置，从后往前遍历，每次可配对鞋一定在 vector 最后一个最优。贪心显然成立。可以用树状数组优化求区间 $1$（交换次数）操作。

ABC285E

Medium

DP。可设 $S_i$ 表示一周 $i+1$ 天只有一天休息日的贡献。易得 $S_i=2\sum\limits_{j=1}^{\lfloor\frac{i}{2}\rfloor}a_j+[i\bmod 2=1]a_{\lceil\frac{i}{2}\rceil}$。设 $F_i$ 表示一周有 $i$ 天的贡献，初始状态有 $F_i=S_{i-1}$。可以枚举休息日的个数：$F_i=\max\limits_{j=2}^{i-2} F_j+F_{i-j}$。答案为 $F_n$。

CF79D

Medium

状压 DP + 差分 + 图论建模。对区间翻转的操作，可以把序列转为差分序列后单点修改。设让 $(i,j)$ 两位同时翻转的代价为 $w(i,j)$，再设已清零状态为 $ste$ 的最小代价为 $f_{ste}$。可得：$f_{ste}=\min\limits_{i,j} f_{ste-2^i-2^j}+w(i,j)$。对于 $w(i,j)$ 我们采用图论建模：若 $|u-v|=l_i$，则 $u,v$ 之间有边权为 $1$ 的边。那么可由 $v$ 再拓展到其他边，这样对于每个起点 $s$ 求出来的最短路 $dis_i$ 即为两点同时翻转的最小操作次数。所以跑 $n$ 轮 SPFA 即可得到 $w(i,j)$。

CF1109E

Medium

线段树。除数如果和模数互质，那么转换为乘逆元的操作，非常好做。注意到模数不同的质因子不超 $9$ 个，现在把模数唯一分解，对于操作除数可以先把含有的模数因子剔除出来，剩下的数就可以乘逆元。是因子的数我们存他的指数，除到了他们就是指数减减。要计算权值的时候跑个快速幂把他们乘起来。

CF853C

Medium

二维数点。算相交不好算，就算不相交的。显然在矩形的某一边的一侧或角落上，减去四边上的后多减了一次四角，所以要再加回来。由于可以旋转坐标系，所以我们只考虑左下角。我们把矩形按左下角横坐标排序，双指针维护点横坐标始终小于等于矩形左端，左边的不相交矩形个数是 $\binom{i-1}{2}=\frac{(i-2)(i-1)}{2}$，左下角的矩形个数是 $\binom{k}{2}=\frac{k(k-1)}{2}$。$k$ 表示横纵坐标都小于当前矩形左下角横纵坐标的点数。如何求 $k$？二维偏序，可以树状数组维护。

Luogu P2757 [国家集训队] 等差子序列

Medium

线段树 + 哈希。题意容易转换为找排列中有没有长度为 $3$ 的等差序列。这类题可以想到遍历中间那个数，如果 $a_i-k$ 已遍历（在左边）、$a_i+k$ 未遍历（在右边）就合法，当然大小顺序倒过来也一样。考虑优化掉 $k$ 的枚举。假设我们现在用一个长为 $n$ 的 01 数组来表示下标为 $i$ 的数是否访问过。我们考虑对一个值为 $1$ 的地方将整个数组折叠，如果重合的地方只有其中一个为 $1$ 那么我们就找到了长为 $3$ 的等差序列。这一步可以用两个哈希比较，分别是从左到右的哈希和从右到左的哈希，如果哈希相同，证明找到了等差序列。这一步可以用线段树实现区间哈希。

CF1083C

Medium

线段树 + ST 表。查 mex 就是查一段最大前缀 $1,2,\dots,k$ 使得这权值为 $1,2,\dots,k$ 的 $k$ 个点都在一条链上。考虑对每个 $i$ 维护点权等于 $i$ 的点在树上的编号，用线段树维护 $[l,r]$ 是否都在一条链上。考虑区间信息的合并：如果任意一个区间内的点都不构成链，必然合起来也不构成链。否则考虑两条链的端点 $a,b,c,d$，任选两个作新链的端点，总共有 $\binom{2}{4}=6$ 种可能，枚举即可，同时判断另外两个点是否在这条链上。

如何判断一个点是否在一条链上：$dis(x,u)+dis(x,v)=dis(u,v)$ 是 $x$ 在路径 $(u,v)$ 上的充要条件。用欧拉序 +ST 表 $O(n\log n)\sim O(1)$ 求 LCA 即可。

CF830D

Medium

DP。设 $f_{i,j}$ 表示 $i$ 层的树能选出多少组不相交的 $j$ 条路径。可以由两棵 $i-1$ 层的树合并成 $i$ 层的树。共有 $4$ 种转移：1. 直接转。 2. 增加一条路径，即根节点自己。 3. 将根节点和一条路径合并。 4. 将根节点和两条路径合并。转移方程分别为（$t=f_{i-1,j}\times f_{i-1,k}$）：

$f_{i,j+k}=t$
$f_{i,j+k+1}=t$
$f_{i,j+k}=2t(j+k)$
$f_{i,j+k-1}=2t\binom{j+k}{2}$

目标状态为 $f_{n,1}$。

2024.10.31

CF513E2 & E1

Hard

DP。这个做法可以过 E1。遇绝对值拆绝对值，我们发现真正有贡献的段是比相邻都大或都小的段。抽象成折线图，“峰”可以贡献 $+2s_i$,“谷”可以贡献 $-2s_i$，其余（“升”、“降”）的贡献均为 $0$。当然 $s_1$、$s_k$ 的贡献另说。根据发现，可设 $f_{i,j,0/1/2/3}$ 表示第 $i$ 个数属于第 $j$ 段、当前这一段状态是“谷”、“升”、“峰”、“降”四种状态之一的最大答案。考虑方程：

对于“谷”的转移：

把 $a_i$ 融入这一段，仍然是谷。
$a_i$ 新开一段，上一段可能是降或峰。
所以 $f_{i,j,0}=-2a_i+\max{f_{i-1,j,0},f_{i-1,j-1,3},f_{i-1,j-1,2} }$。

对于“升”的转移：

把 $a_i$ 融入这一段，仍然是升。
$a_i$ 新开一段，上一段可能是谷或升。
所以 $f_{i,j,1}=\max{f_{i-1,j-1,0},f_{i-1,j-1,1},f_{i-1,j,1} }$。

后面两种情况类比上面的两种情况。初始状态为 $f_{i,0,0/1/2/3}=0$，其余为无穷小。目标状态是 $f_{i,k,0/2}$。发现 $i$ 总是由 $i-1$ 转移而来，所以可以滚动压掉一维。

Luogu P9128 [USACO23FEB] Fertilizing Pastures G

Medium

贪心。不用走回根节点的情况显然把深度最大的一条链留到最后再走。设 $sum_u$ 表示子树 $u$ 的点权和，$sz_u$ 表示子树大小。设 $f_u$ 表示零时刻在 $u$ 的最小代价。我们考虑访问子树的顺序使得 $f_u$ 最小。若 $u$ 的儿子为 $p_{1,\dots,k}$，代价为：$\sum\limits_{i=1}^kf_{p_i}+sum_{p_i}+\sum\limits_{i=1}^k 2sum_{p_i}\sum\limits_{j<i} sz_{p_j}$。前面的 $\sum$ 是确定的，后面的 $\sum$ 取决于 $p$ 的顺序。我们考虑 $p_i$ 与 $p_{i+1}$ 交换是否更优。我们钦定排在前面的更优，那么有 $sum_{p_{i+1}}\times sz_{p_i}<sum_{p_i}\times sz_{p_{i+1}}$。按 $\frac{sum_i}{sz_i}$ 降序排序得到的 $p$ 最优。

对于可以不用回到根节点的询问，把有最长链的儿子放到最后，考虑变化量。

Luogu P2737 [USACO4.1] 麦香牛块Beef McNuggets

Easy

DP。学到了一个 trick：在我们无法证明或不确定其正确性的时候，我们就大胆乱搞，程序能跑多少就跑多少，如果这个结论刚好被猜中，效益是很大的！解法：布尔完全背包。

Luogu P2727 [USACO3.2] 01串 Stringsobits

Easy

DP。首先杨辉三角预处理出组合数，那么从高位枚举可不可以放 $1$，充要条件是 $\sum\limits_{j=0}^L \binom{i-1}{j}>k$。边做边输出。

Luogu P2732 [USACO3.3] 商店购物 Shopping Offers

Easy

DP。一定要相信自己的 idea！注意到商品数量极少，所以是五维完全背包 DP。如果不买这么多，可以看成是买 $0$ 个对应物品。

Luogu P1930 [USACO3.3] 亚瑟王的宫殿

Easy

bfs。枚举汇集点，bfs 出每个马的最短步数。再枚举每个骑士 bfs 出国王在哪个点和骑士汇集。

2024.11.1

11 月了啊。

Luogu P6100 [USACO19FEB] Painting the Barn G

Medium

差分 + DP。差分可以把区修变单修。再通过前缀和和起来得到原数组，对于 $k$ 和 $k-1$，前者覆盖后贡献为 $-1$，后者为 $1$。设 $h_{l,r}$ 为 $\max\limits_{i}s[i][l,r]$，设 $w_{l,r}$ 为 $\max\limits_{i}s[l,r][i]$（$s$ 是求和数组）。前者是限定了列，后者是限定了行。答案即为 $cnt+\max\limits_i{h_{1,i}+h_{i+1,200},w_{1,i}+w_{i+1,200} }$，$cnt$ 为原矩阵本来就等于 $k$ 的数量。

2024.11.3

Luogu P5839 [USACO19DEC] Moortal Cowmbat G

Medium

DP + 前缀和/前缀 $\text{min}$ 优化。先跑一边 floyd 求最短路。设 $f_i$ 表示以 $i$ 结尾的连续段的最小代价。DP 方程易得：$f_i=\min{ f_j+\text{get}(j+1,i)}$，$\text{get}$ 表示这一段都换成同一种颜色的最小代价。这里可以预处理前缀和 $O(1)$ 查询。设 $mn_j$ 表示颜色改为 $j$ 的最小代价（前缀 $\text{min}$），可以 $O(1)$ 转移：$mn_j=\min{mn_j+dis_{i,j},f_{i-k}+\text{get}(i-k+1,i,j)}$，这里的 $\text{get}$ 多传了颜色参数。

Luogu P7054 [NWRRC2015] Graph

Medium

拓扑排序变种。要求字典序小相当于在用小根堆做拓扑。考虑当前入度为 $0$ 的点是否能被别的点连接，用大根堆存可以被连接的点。能被连接，充分条件是有一个比他大的节点且比他的访问顺序先（访问顺序后的节点再连会构成环）。以此来把当前入度为 $0$ 的点纳入可被连接的范畴。如果有剩，优先输出剩的；否则输出可被连接的。连边可以按拓扑序上一个连有向边，正确性显然的。

2024.11.4

Luogu P8990 [北大集训 2021] 小明的树

Hard

线段树。视亮灯点为白点，不亮点为黑点。白点不好做，就考虑黑点。因为根节点始终为黑点，所以当满足限制时，黑点只构成一个连通块。怎么判断黑点只构成一个连通块？黑点数减“黑黑边”数就是黑连通块数。白连通块的数量本质上是“黑白边”的数量。有了这个结论，单次询问可以 $O(n)$ 维护“黑黑边”数、“黑白边”数和黑点数并得到结果。现在带修，一次修改查询只能在 $O(\log)$ 内完成。自然想到对于每个时刻维护以上三值。先考虑一条边的断/连会对以上三值有什么影响（只考虑连的情况，断是等价的）。

设 $t_x$ 表示点 $x$ 点亮的时刻，以下钦定一条边 $(x,y)$ 中 $t_x<t_y$。显然对于黑点数不会有影响。对于“黑黑边”数在 $[1,t_x-1]$ 会增一。对于“黑白边”数在 $[t_x,t_y-1]$ 会增一。由于维护黑点数和“黑黑边”数是为了得到黑连通块数，而其中一值不变，干脆直接维护黑连通块数与白连通块数。前者在 $[t_x,n-1]$ 会增一，后者在 $[t_x,t_y-1]$ 会增一。发现这两个东西都是区间维护，可以上线段树。具体地，维护黑连通块最小时大小、存在了几个时刻、以及当前区间黑连通块最小时的答案。

Luogu P7124 [Ynoi2008] stcm

Medium

分治。先得到每个点的 dfn 序，那么一个点及其子树内的节点的编号是连续的。他的子树补就是 $[1,dfn_u-1]\cup [dfn_u+sz_u,n]$。可以分治。对于当前分治区间 $[l,r]$，处理被 $mid$ 分开子树区间的点 $u$。暴力逼近点 $u$ 的子树区间，这个过程输出操作 1 的答案。然后再撤销以上操作 1，暴力将右端点逼近至 $mid-1$，然后递归分治左区间，同样输出，同样撤销；右区间同理。

2024.11.6

Luogu P2739 [USACO4.4] 棋盘游戏Shuttle Puzzle

Easy

dfs。注意不要写宽搜！剪枝是平凡的“深度大于等于最优答案”就回溯。对于优先级的问题搜索顺序调整一下即可。

2024.11.11

前面一周 3 天打了 5 场模拟赛把人打傻了，今天终于来刷题了。

Luogu P6653 [YsOI2020] 造林

Medium

树型 DP + 哈希。“最大子树大小”可以自然想到找出整棵树的重心。以重心为根往下树型 DP。若在当前点 $u$ 下面接一个新的叶子节点，会发现只有当前点到根节点路径上的点的贡献没有加一。可以用一个哈希刻画所有节点贡献的情况，每次修改这个哈希来刻画当前状态。我们可以以不同贡献的数量来设计哈希。直白点就是用桶装贡献，然后把桶放进哈希里面。

Luogu P7393 「TOCO Round 1」Eternal Star

Medium

构造。设最大值为根。若该节点点值为 $u$，那么他的儿子的点值分别为 $1,2,\dots,u-1$。为了保证该点为 $u$，点值为 $i$ 的儿子的数量至少是 $u-i+1$。但是节点数有点过于多了，我们发现 $k$ 有两个值为 $k-1$ 的儿子。如果只保留一个，并把 $k-1$ 的子树构造成和根节点（值为 $k$）一模一样，那么即使 $k$ 和 $k-1$ 交换了树的形态本质相同。显然这样节点数变少了。

2024.11.21

前些天有的题为了赶业绩就没写复盘，所以一拖拖到 10 天才来写复盘。感觉刷题留痕很重要啊，距离 NOIP 也不到两周，业绩什么的先放一边，提升自己实力最为重要。谁知道 NOIP 后我是不是就直接 AFO 了。

这几天重看了一下前面的复盘，一开始刷的题难度在蓝紫以上，中间也刷了一点绿蓝题。鉴别他们的最好办法就是看题解长度，长的就是比较难的，短的就是简单得一批。

Luogu P1514 [NOIP2010 提高组] 引水入城

Easy

bfs + DP。沙漠点显然给峰顶供水即可，所以蓄水点能供给的沙漠点一定是一段区间（有解情况下）。可以通过 bfs 得到每个蓄水点供给沙漠点的个数。然后 DP 选最少的蓄水点使得区间覆盖所有沙漠点。平凡的 $f_{i,j}$ 表示考虑到第 $i$ 个蓄水点、最大右端点覆盖到 $j$ 的最小方案数。简单转移。

Luogu P1967 [NOIP2013 提高组] 货车运输

Easy

Kruskal 重构树 + 倍增 LCA。重构树有个性质就是所有叶子节点才是原图的点，其余的点都代表左右两棵子树的合并权值，所以两个叶子节点的 LCA 代表的权值就是这两个点在生成树上路径的瓶颈。所以可以快速解决此题。

Luogu P1966 [NOIP2013 提高组] 火柴排队

Easy

树状数组。首先贪心的想最优匹配肯定是两个数组都从小到大排序后两两配对，那么可以得到 $c_i$ 表示 $a_i$ 与 $b_{c_i}$ 匹配（这里的 $a$，$b$ 数组均为排序前的数组）。题目要求邻项交换，直觉地想到求 $c_i$ 逆序对数量，套个树状数组就做完了。

2024.11.22

Luogu P5022 [NOIP2018 提高组] 旅行

Easy

模拟 + 贪心。观察数据范围发现图只有可能是树或基环树。树的情况直接贪心跑 dfs，因为树上到达一个点有且仅有一条路径，所以这样显然是对的。对于基环树我们可以对环考虑，边跑边考虑几个事情：

要不要往当前节点的若干儿子的子树跑一跑 dfs。
要不要掉头换个方向跑环。

要注意，在掉头回去的时候要把路径上没跑过的儿子的子树全部跑完。因此选择掉头与否取决于下一个环上的点是否大于环起点另一方向的邻点与回溯时第一个要跑的儿子点。这种题没有什么思维含量，但是细节要考虑很多，稍不留神就会错一些情况。码量 3k，还好。时间复杂度 $O(n)$，可以过加强版，等价于切紫好耶。

【NOIP 模拟 T1】

Medium

大意：有 $n$ 个人（$n$ 为偶数），要把他们分成人数相同的两组，人 $i$ 对该组的贡献为 $\sum\limits_{j\in \text{Team}} w_{i,j}$。（$i,j$ 是无序对）求两组可能的最大差距。（$n\leq 10^3$）

贪心。设当前分组为 $\text{TA}$ 与 $\text{TB}$，分组的值为 $A$、$B$，钦定 $A>B$。若交换不同组的 $x,y$ 两人，则答案由 $A-B$ 变为 $(A-\sum\limits_{i\in \text{TA}}w_{x,i}+\sum\limits_{i\in \text{TA}} w_{y,i})-(B-\sum\limits_{i\in \text{TB}}w_{y,i}+\sum\limits_{i\in \text{TB}}w_{x,i})$。设 $sum_i=\sum\limits_{j=1}^n w_{i,j}$，上式即为 $A-B+sum_y-sum_x$。我们想让交换后答案变大，要保证 $sum_y>sum_x$，所以直接排序，前面一半一组，后面一半一组。答案即为两组的权值差的绝对值除以 $2$（因为 $i,j$ 无序）。

ARC017D

Medium

线段树 + 更相减损术。首先有结论：

$$\gcd (a_l,\dots,a_r)=\gcd (a_l,|a_{l+2}-a_{l+1}|,\dots,|a_{r-1}-a_{r-2}|,|a_r-a_{r-1}|)$$

维护差分数组，答案即为 $\gcd (\sum\limits_{i=1}^l d_i,\gcd(|d_{l+1}|,\dots,|d_r|))$。线段树维护区间和与区间 $\gcd$。

Luogu P2300 合并神犇

Medium

单调队列优化 DP。设 $f_i$ 表示 $[1,i]$ 处理成单调不降序列的最小合并次数，$pre_i$ 表示 $[1,i]$ 最末尾的数。找到一个 $j$ 使得 $sum_i-sum_j\geq pre_j$ 并且 $f_i$ 和 $pre_i$ 尽量小，转移 $f_i=f_j+i-j+1$、$pre_i=sum_i-sum_j$。

考虑单调性。$pre_i$ 显然随 $j$ 增大而减小。$f_i$ 受 $f_j-j$ 影响，考虑邻项：$f_j-j$ 与 $f_{j-1}-(j-1)$。假设前者小于等于后者，移项得 $f_j-f_{j-1}\leq j-(j-1)=1$。由定义得假设成立，所以 $f_i$ 随 $j$ 增大而减小。

用单调队列优化，单调队列维护 $sum_i-pre_i$。由于上面的推导，最优决策是最大的满足条件的 $j$。这也是去除单调队列开头的条件。

若现在有 $sum_j-pre_j\leq sum_k-pre_k=q_r$，由于 $k<j$ 所以 $sum_j>sum_k$，所以 $pre_j<pre_k$，所以果断退队尾。

ARC069E

Easy

扫描线（？） + 离散化。假想一条线从高到底往下扫，扫到一个或多个就取最左边的下标累计答案，然后把扫到的高度都下降一。值域大可以离散化，累计答案时需要一个数组映射离散化后的高度原来的值。

ARC055C

Easy

字符串哈希 + 二分。需要 $O(1)$ 得到一段区间信息的题要想到字符串哈希。首先 $O(n)$ 枚举最右边“AC”的左端点 $i$，然后二分哈希得到最长的第一个“A”的右端点（二分条件是第一个“A”与“AC”的“A”相同），再二分哈希得到最短的第一个“A”的右端点（二分条件是“ABC”的“C”与“AC”的“C”相同）。那么当前这个“AC”的方案数为“右端点 - 左端点 + 1”。时间复杂度 $O(n\log n)$。

2024.11.23

模拟赛又 tm 爆零了，明明昨晚才切了两道蓝题。果然还是提升得不够快。希望 NOIP 正式赛可以发挥出来吧。

Luogu P4107 [HEOI2015] 兔子与樱花

Easy

贪心。自底向上按 $son_i+c_i$ 的顺序从小到大贪心删除一定最优。感性证明：对于排序，一定是选最小的儿子删掉不会劣；对于自底向上，如果点 $u$ 的儿子 $v$ 因为删了 $v$ 的儿子节点而导致不能删 $u$，发现不能被删的只有一个点 $u$，但是 $v$ 删掉的是至少一个 $v$ 的儿子节点。