2026 晚练记录

January

Week 4

Tuesday（1.20）

P3092 [USACO13NOV] No Change G

水题（但我为什么数组开小了呢）。

不难发现，$k$ 的值很小，我们可以考虑状态压缩。

令 $f_i$ 表示我状态为$i$ 时我能走到的最大距离，最后用二分和前缀和优化即可。

Wednesday（1.21）

P5664 [CSP-S 2019] Emiya 家今天的饭

很好的题，我们可以考虑正难则反，发现如果没有第三个约束条件，那么答案就是 $\prod _{i=1} ^{n} (num_i+1)-1$，其中 $num_i$ 就是第 $i$ 排的和。

我们来考虑什么时候不合法。

不难发现，如果一个方案不合法只会有一个主要食材的数量越界了，不需要考虑其他的容斥。

由此，我们可以枚举越界的数 $col$ 并设计出状态：$f_{i,j}$ 表示对于前 $i$ 行，$col$ 中选的数量比其他数多 $j$ 的方案数。

转移也很好想：

$$f_{i,j}=f_{i-1,j}+f_{i-1,j-1}*a_{i,col}+f_{i-1,j+1}*(num_i-a_{i,col})$$

最后用方案数减去每一次枚举的 $col$ 所对应的 $\sum _{i=n+1} ^{2 \times n} f_{n,i}$ 即可。

注：这里是 $n+1$ 到 $2 \times n$ 的原因是在转移中有可能出现 $j$ 为负数的情况，需要加个偏移量。

Thursday（1.22）

P3953 [NOIP 2017 提高组] 逛公园

我为什么会在一个数组上犯唐。

难得的图论题，但还是有 DP 的成分。

我们发现，所有的统计都是基于最短路的，所以可以先把每个点的最短路求出来。

我们可以考虑记 $f_{i,j}$ 表示对于第 $i$ 个点，有多少种方案可以使路径长度为 $dis_i+j$，其中 $dis_i$ 表示从 1 到 $i$ 的最短路径。

因为不是所有点都需要转移，我们可以考虑建反图，倒序处理，这里就是记忆化搜索了。

Sunday（1.25）

P3119 [USACO15JAN] Grass Cownoisseur G

为何 28pts？

哦，剪枝剪错了。

我们发现数据存在 SCC，那直接一波缩点。

我们又可以发现答案是一个满足以下条件的链：

• 链中包含 $1$ 号点所在的 SCC
• 链的始端有一条存在连向末端的边

而答案就是这条链的长度。

Week 5

Monday（1.26）

P2491 [SDOI2011] 消防

为何 MLE？dfs(vl,fa)

我要和这世界爆了!!!

你问我为什么不想二分？因为不会写 check。

思路很简单，我们发现答案的端点所在的区域只可能在树的直径上，那我们可以考虑求出直径上的所有点，并求出这个点的子树内所对应的最大与次大深度，最后用单调队列维护区间最大值即可。

哦，我太 TM 唐了。

Tuesday（1.27）

P1941 [NOIP 2014 提高组] 飞扬的小鸟

哦，我觉得这玩意儿应该叫挂分日志。

开局把题看错了，写了 30min 才反应过来，后来才知道原来界面最右边不是第 $n$ 列。

定义 $f_{i,j,0/1}$ 对于第 $i$ 列，要求到达 $j$ 高度的最小操作次数。

转移：

$$f_{i,j,1}= \min \ (f_{i-1,j-x_{i-1},l}+1,f_{i-1,j-x_{i-1},0}+1,f_{i,j-x_{i-1},1}+1)$$

$$f_{i,j,0}= \min \ (f_{i-1,j+y_{i-1},1},f_{i-1,j+y_{i-1},0})$$

当 $j=m$ 时我们还可以：

$$f_{i,m,1}= \min ^m _{m-x_{i-1}} \ (f_{i-1,j,1}+1,f_{i-1,j,0}+1,f_{i,j,1}+1);$$

特殊处理一下这一列上有水管的情况即可。

真 TM 想死。

February

Week 4

Wednesday（2.25）

P1772 [ZJOI2006] 物流运输

难得的场切。

• 赛时做法：

发现港口数量很少，可以考虑状压，定义 $f_{i,j}$ 表示第 $i$ 天只通过 $j$ 中的点所需的最小成本。

令 $bis_{i,j}$ 表示第 $i$ 天中除去 $f_{i,j}$ 外的最小成本，$dis_{j}$ 表示嵌定只通过 $j$ 中的点所需的最小成本，那转移很好想了：

$$f_{i,j}= \min (f_{i-1,j},bis_{i-1,j}+k)+dis_j$$

我们发现 $dis$ 数组可以预处理，$f$ 和 $bis$ 数组可以滚掉第一维，所以复杂度为 $O(2^m e \log m + n 2^m)$，可以考虑用 SPFA 再加点卡常通过。

• WWX 提供的解法：

发现对于每个位置 $i$ 可以考虑枚举上一个和它路径不同的点，然后计算 $f_i$ 从哪转移即可，复杂度：$O(n^2 m \log n)$。

Tuesday（2.26）

P2254 [NOI2005] 瑰丽华尔兹

再次痛失 100 pts。

为什么把 continue 写成了 break 呢？

思路很简单，可以考虑定义 $f_{t,i,j}$ 对于第 $t$ 号区间，要求最后会出现在 $i$ 行 $j$ 列的位置上。

发现转移需要知道上一个点的位置，这会在时间上出现一个 $T_t - S_t + 1$ 的复杂度，由此可以考虑用单调队列优化掉。

代码分情况讨论即可。

March

Week 1

Monday（3.2）

P9921 [POI 2023/2024 R1] Budowa lotniska

笑点解析：钦定了 $i$ 行都是横着的，但还需避开 $j$ 列。

首先处理出两个都为行和列的情况，然后考虑钦定一行选第一个，在取一列作为第二个。

至于重复的情况可以选择分别令 $a_{i,j}$ 是在第 $i$ 行和第 $j$ 列即可。

Tuesday（3.3）

P9923 [POI 2023/2024 R1] Przyciski

赛时题目看错了，只来得及打上暴力，但暴力也挂了。

我们发现题目中会存在两个不同的修改，一种思路是 DP（事实上，赛时就是这样想的），另一种是考虑建图。

我们可以考虑根据按钮所在位置 $x_i$ 和 $y_i$ 分别建图，随后可以考虑通过分类讨论来解决问题。

分奇偶性来讨论：

• 对于偶数情况，发现只需图中有环即可。这个正确性是显然的，每一个点会有两个度，即会被修改两次，这就是偶数情况。
• 对于奇数情况，我们发现图中是不存在环的，这会形成一片森林，我们发现对于叶子节点，它与它父亲的边是必选的，而对于其余点，只需考虑有多少边连向了它，以及是否向它的父亲连边即可。需要特殊判断一下根节点。

Wednesday（3.4）

P7961 [NOIP2021] 数列

赛时发现 $S$ 过大，不好判断，没考虑按位处理。

我们考虑定义 $f_{i,j,l,x}$ 表示当前处理好了 $S$ 的第 $i$ 位，此时向第 $i+1$ 位进位了 $j$ 并且前面有 $l$ 个 $1$ 以及确定了 $x$ 个 $a$。

这是一个我为人人的转移，我们发现对于 $f_{i,j,l,x}$ 我们来枚举下一个位置用 $y$ 个 $a$ 它可以转移到的位置其实就是 $f_{i+1,(j+y) \div 2,l+(j+y) \bmod 2,x+y}$ 但是 $a$ 是无序的，所以需要转移中要乘上 $\binom {n-x}{y} \times v_{i+1}^y$。

令最后一遍转移的位置是 $pos$，则答案就是：

$$\sum _{i=0} ^{k} f_{pos,0,i,n}$$

Thursday（3.6）

P2668 [NOIP 2015 提高组] 斗地主

又是一道大模拟。

我们可以考虑记录每种牌共有多少个，再考虑把它压缩成五进制数，用 unordered_map 来记忆化搜索。

接着就是细节问题。

但是你这样只能跑 90pts，我们发现考虑单出的时候太耗费时间了，可以直接单独处理。

此题代码也可通过加强版。

Sunday（3.8）

「JOI 2013 Final」现代豪宅

回归 rk 7。

• 赛时：

思路很简单，我们发现对于 $n,m \le 2 \times 10^3$ 的数据，只需考虑从 $(1,1)$ 到当前点的最短路即可。

再次思考会发现我们似乎只用考虑起点，终点以及有按钮的点的最短路即可，这只需转移同一行与列即可。

最终拿到 80pts。

• 赛后：

再次思考后发现，似乎不用向其他点转移，只需向左右两个点转移即可。

Week 2

Monday（3.9）

P6007 [USACO20JAN] Springboards G

赛时以为和前一天的题类似，一直在思考如何优化建图（好像是用 CDQ 分治），赛时没调出来，炸飞了。

我们发现如果这题是建图跑拓扑的话，就像一个我为人人的 DP，这样是不好做的。

我们可以考虑换一种思路，考虑人人为我的 DP。

这似乎就显然了，只需考虑在 $x$、$y$ 值比我小的数转移即可。

这只需按照 $x$ 排序，然后把剩下的数扔到树状数组上即可。

Tuesday（3.10）

P5017 [NOIP 2018 普及组] 摆渡车

如此唐题，为何没切？

（原来是自信提交后才发现做法假了）。

好像可以斜率优化来做，但是记忆化搜索应该就够了。

• 赛时：

似乎可以考虑区间 DP，只需转移 $f_{i,j}$ 以及 $g_{i,j}$ 分别定义为 $i$ 到 $j$ 号点最短等待时间和 $i$ 到 $j$ 号点且 $i-1$ 号点所在时间点被运走的最短等待时间。

很明显，假了。

• 赛后：

我们发现无法定义上一辆车是啥时候走的，那可以考虑直接枚举，这样可以得到 30pts。

后来又发现，我们只需考虑当前这个点与上一个开车点的间隔即可转移，复杂度 $O(n^2)$。

Wednesday（3.11）

P10138 [USACO24JAN] Cowmpetency G

又是数数题，又是挂分的一天。

我们可以考虑计算 $f_{i,j}$ 表示对于前 $i$ 个数，最大值为 $j$ 的所有合法方案，再用前缀和优化即可做到 $O(nc \log v)$。

我们可以考虑区间离散化，把它按照区间离散成点，这样就可以做到 $O(qc \log v)$。

Thursday（3.12）

P9981 [USACO23DEC] Minimum Longest Trip G

这应该是最长路树的板子，也是难得的场切。

首先，处理出最长路的长度还是容易的，只需一个拓扑排序即可。

我们可以考虑把会考虑的点拎出来，这样就会形成一颗最长路树，我们发现对于这样一棵树，深度（这里把结点的深度定义为最长路长度，因为有可能存在多个根节点但不同根节点之间的深度可能不同）相同的点之间是可以根据它们子节点的字典序大小来排序的，具体方法如下：

• 比较与子节点连边的边权内最小的边权

• 比较所选子节点的排名

就做完了，有点常数，但不需要优化。

Sunday（3.15）

P7201 [COCI 2019/2020 #1] Džumbus

这个满级题面，不想喷了。

思路还是很简单的，发现建边之后就是一个森林，这启发我们可以设置一个超级源点来转化题面为树上背包问题。

我们发现，对于点 $x$ 它的贡献可能为 $0$ 到 $2$ 之间不等，所以需要分讨。

定义 $f_{x,j,0/1,0/1}$ 表示对于点 $x$ 及其子树内选择了 $j$ 个有效点，当前这个点没选、选，且其儿子没有、有被选的最小代价。

转移有点难写，这边直接把代码粘上去：

f[x][j+k+2][1][1]=min(f[x][j+k+2][1][1],f[x][j][1][0]+f[it][k][1][0]);

f[x][j+k+1][1][1]=min({f[x][j+k+1][1][1],f[x][j][1][0]+f[it][k][1][1],f[x][j][1][1]+f[it][k][1][0]});

f[x][j+k][1][1]=min({f[x][j+k][1][1],f[x][j][1][1]+f[it][k][0][0],f[x][j][1][1]+f[it][k][1][1]});

f[x][j+k][1][0]=min(f[x][j+k][1][0],f[x][j][1][0]+f[it][k][0][0]);

f[x][j+k][0][0]=min({f[x][j+k][0][0],f[x][j][0][0]+f[it][k][0][0],f[x][j][0][0]+f[it][k][1][0],f[x][j][0][0]+f[it][k][1][1]});

Week 3

Monday（3.16）

P5021 [NOIP 2018 提高组] 赛道修建

最小值最大，这很容易想到二分，但如何在 $O(n \log n)$ 的复杂度内写出 check 是需要考虑的。

我们容易想到一个 $O(n^2)$ 的 DP 来解决，定义 $f_{i,j}$ 表示在以 $i$ 为根的子树内，$i$ 所在链的长度为 $j$ 的情况下有多少条链满足要求。

虽然有了思路，但这个 DP 并不好优化，由此，我们可以考虑贪心。

我们发现，对于当前这个点 $i$ 它及它的子树内的满足的链的长度是可以确定的，这只需贪心处理当前这个节点与它的儿子节点之间的边，如果说儿子节点所在的链 $\ge$ 所验证的长度，那答案就加一，否则贪心的匹配结果即可。

Tuesday（3.17）

P11830 [省选联考 2025] 幸运数字

我在 CWOI 2026 2,3月晚练中只挂了 389pts，你也来试试吧

这次是因为忘记判断区间不连续导致的。

我们发现对于 A 性质是好做的，对于 $x$，我们只需处理出一定小于它的数量的最大与最小值，以及一定大于它的数量的最大与最小值，最后判断这个值是否可行即可。

至于 100pts，只需处理离散化一下即可。

Wednesday（3.18）

我咋这么唐。

P3647 [APIO2014] 连珠线

事实上，$O(n^2)$ 的 DP 还是好想的，我们可以枚举节点 $x$ 作为根节点，并定义 $f_{i,0/1}$ 表示当前这个点是不是在父亲生成之前生成的，定义有很多种，但转移都是一样的：

$$f_{i,0}= \sum _{j \in son_i} \max {f_{j,0},f_{j,1}+w} \\ f_{i,1}=\sum _{j \in son_i} f_{i,0} - \max {f_{j,0},f_{j,1}+w} + f_{j,1} + w$$

最后考虑换根 DP 即可。

Thursday（3.19）

2、3 月榜单已经废了。

P4006 [清华集训 2017] 小 Y 和二叉树

我们可以考虑最后答案中的第一个位置是什么，发现只要它不会强制作为根（即边数不超过 $2$）即可，这只需找到第一个点满足条件的然后考虑即可。

对于点 $x$，我们需要考虑它以及它的子树内的点的最小字典序，因为每个点的编号是不同的，这启示我们只需统计第一位（后文记为 $mn_x$）即可。

在这里，对于不同的边数我们需要分类讨论（$x$ 是从左儿子传上来的）：

• 边数为 0。

这很显然了，把 $x$ 加入答案即可。

• 边数为 1。

我们需要考虑当前这个点唯一连向的点（记为 $v$）当 $x$ 的父亲还是儿子，比较显然的是如果 $mn_v>=v$ 则当父亲，至于为什么可以取等，因为当父亲的情况一定是包含当儿子的。

• 边数为 2。

这只需要考虑两个节点的 $mn$ 谁更小，更小的当儿子，大的当父亲。

具体实现只需处理三个 DFS，一个计算 $mn_x$，一个计算左儿子计算过了的情况，一个计算父亲计算过了的情况。