2026 晚练记录

# 注意

• 数组不要开小了（1.20）

• 剪枝不要剪错了（1.25）

• continue 和 break 不要写混了（2.26）

• 写区间操作时一定要判 l>r （3.26）

• 注意 long long （4.14）

• st 表查询可以 $O(1)$（4.14）

• 用 STL 弹出时一定要判空（4.15）

• 猜性质时一定要手模样例（4.16）

# 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$，一个计算左儿子计算过了的情况，一个计算父亲计算过了的情况。

# Sunday（3.22）

AT_abc319_g [ABC319G] Counting Shortest Paths

• 赛时

我们发现，对于比较大的数，它的最短路径一定比较小（正确性显然），所以可以考虑数据点分治，考虑跑 dij 处理 $n \le 5000$ 的情况，剩下的判一下即可获得 74pts。

• 赛后

因为赛时考虑了数据点分治，这里仍可以接着讨论 $n \ge 5000$ 的情况，我们发现，对于此的答案是有限的（具体是多少我也不知道），但我们可以考虑计算 $f_{i,j}$ 表示走 $i$ 步到达 $j$ 的所有方案数。

转移应当是简单的：

$$f_{i,j}=\sum _{(j,k) \in E} f_{i-1,k}$$

但是这样下来复杂度有点高，可以考虑从总方案中减去不合法的，即：

$$f_{i,j}=sum - \sum _{(j,k) \not \in f_{i-1,k}} f_{i-1,k}$$

其中 $sum$ 为上一轮中的各个点的方案数之和。

# Week 4

# Monday（3.23）

P5665 [CSP-S 2019] 划分

难得的没有挂分。

赛后听 hb314 说这似乎是去年暑假集训的一场 T3，但当时都没人改（主要对于当时的我们还是太难了）。

• 赛时

首先先想到 $O(n^2)$ 的一个 DP ，可以定义 $f_i$ 表示前 $i$ 个数处理起来的最小值，$g_i$ 则表示 $i$ 所在块的和是多少。

这个应当是好转移的，只需找到从后往前第一个满足 $g_j \le sum_i - sum_j$ 的位置即可，虽然不会证明正确性。

对于 $O(n \log n)$ 的做法，思考了很久，考虑过双指针和二分，但 $g$ 数组似乎不满足单调性，所以这里就考虑用堆来实现。

可以考虑实现一个小根堆（这里需要将上面的式子转化成 $g_j + sum_j \le sum_i$），每次取出堆顶的元素，看看是否满足要求，满足就更新最大值即可。

这样可以获得 88pts 的成绩。

• 赛后

原本通过不能二分和双指针已经觉得和单调性没啥关系了，结果来了个单调队列？

事实上，我们可以考虑在计算完 $i$ 之后剔除掉在 $i$ 之前出现的且 $sum_j + g_j \ge sum_i + g_i$ 的所有值，正确性是显然的，这只需要一个单调队列维护即可。

# Tuesday（3.25）

P15819 [JOI 2015 Final] 舞会 / Ball & AT_joi2015ho_d 舞踏会 (Ball)

唐飞的一天。

我们发现对于不确定的位置是不好贪心求解的（赛时还在想这个的正确性），我们可以考虑二分和模拟，以及树形 DP。

这里提供二分加模拟的做法。

我们可以考虑对于数 $x$，要使它作为最后一个的最小代价是多少

有一个很经典的 trick：将所有的 $d_i \ge x$ 贵族改为 1，其他改为 0。

考虑到我们最后若想要此种情况成立，需要最后留下来的贵族是 1 才行。

我们观察题目的操作，容易得出当知道所有数时，可以用 deque 来维护，这里 deque 中存的每一位是当前局面下使得这一位为 1 的最小值。

那么对于初始固定的位置，若它对应的贵族是 1，则值是 0，若是 0，则设为极大值（即不行），若这个位置没有初始值，则设为 1，因为需要往这里填入一个是 1 的贵族。

按照题意模拟，每次取出前三个，若要使得加到最后的是 1，则前三个中必须至少有两个 1，枚举三种情况，取最小值，将其加到末尾。

最后将最后一个提取出来，并判断它为 1 时所需要的 1 数量是否小于等于总的 1 数量即可。

# Wednesday（3.25）

P9018 [USACO23JAN] Moo Route G

又是赛后秒改的一天。

赛时想了个线段树维护区间最小值，考虑以 $i$ 为起点所连出的不同种类的边的数量，结果直接伪了。

我们发现最优策略肯定是一次往返中所经过的点的数量越多越好，那这里我们就可以考虑对于位置 $i.5$ 所对答案造成的贡献。

• a_i \le a_

在这种情况下，经过了 $i.5$ 的边一定会经过 $(i-1).5$，对此，我们只需计算上一个点所经过的边（即 $a_{i-1}$）中选出 $a_i$ 即可。

• a_i \ge a_

在这种情况下，经过了 $(i-1).5$ 的边一定会经过 $i.5$，这时，我们只需要考虑经过 $i.5$ 的边中，插入以 $i$ 为起点的边的方案。

因为这之间有 $a_i - 1$ 个不同的位置，所以相当于是在 $a_i - 1$ 个位置中塞入 $a_i - a_{i-1}$ 个球。

总的方案：

$$\prod _{i=1} ^ {n-1} {\binom {a_{i-1}} {a_i} + \binom {a_i - 1} {a_i - a_{i-1}}}$$

# Thursday（3.26）

P9352 [JOI 2023 Final] 训猫 / Cat Exercise & AT_abc435_f [ABC435F] Cat exercise

赛时看错题导致先写了第二题和第一题的 41pts 的，但为何没有判断 l>r 挂飞了呢？

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

对于 T2 & T1 Subtask 5 应当是容易的，考虑分治的同时用 ST 表来维护即可（但为何砸了颗线段树呢？）。

对于 T1，我们发现贪心去查找似乎复杂度极高，所以这里可以考虑 DP。

定义 $f_i$ 表示以 $i$ 为根的子树中可以走的最大距离，设 $g_i$ 表示以 $i$ 为根的子树中的最大点的值。

转移是显然的：

$$f_i = \max _{v \in son_i} {f_{g_v} + dis_{i,g_v}}$$

其中 $dis_{i,j}$ 表示 $i$ 和 $j$ 之间的距离。

接下来考虑如何实现。

由于猫行走到的节点的高度呈单调递减，则必须先转移小的值 $v$，才能对大的值 $u$ 进行转移。

那么我们可以考虑在连边时连接 $u$ 和 $v$，这样我们从 $1$ 至 $n$ 对每一个节点进行转移。

对于 $g_i$ 我们可以用并查集来维护，对于 $dis_{i,j}$，我们使用 lca 进行求解即可，时间复杂度：$O(n (\log n + \alpha(n)))$。

# Sunday（3.29）

P9322 [EGOI 2022] Superpiece / 超级棋子

大分讨，好难写。

这里我们主要思考马的情况，打打表找一下规律：

 0  3  2  3  2  3  4  5  4  5  6  7  6  7  8  9  8  9 10
 3  2  1  2  3  4  3  4  5  6  5  6  7  8  7  8  9 10  9
 2  1  4  3  2  3  4  5  4  5  6  7  6  7  8  9  8  9 10
 3  2  3  2  3  4  3  4  5  6  5  6  7  8  7  8  9 10  9
 2  3  2  3  4  3  4  5  4  5  6  7  6  7  8  9  8  9 10
 3  4  3  4  3  4  5  4  5  6  5  6  7  8  7  8  9 10  9
 4  3  4  3  4  5  4  5  6  5  6  7  6  7  8  9  8  9 10
 5  4  5  4  5  4  5  6  5  6  7  6  7  8  7  8  9 10  9
 4  5  4  5  4  5  6  5  6  7  6  7  8  7  8  9  8  9 10
 5  6  5  6  5  6  5  6  7  6  7  8  7  8  9  8  9 10  9
 6  5  6  5  6  5  6  7  6  7  8  7  8  9  8  9 10  9 10
 7  6  7  6  7  6  7  6  7  8  7  8  9  8  9 10  9 10 11
 6  7  6  7  6  7  6  7  8  7  8  9  8  9 10  9 10 11 10
 7  8  7  8  7  8  7  8  7  8  9  8  9 10  9 10 11 10 11
 8  7  8  7  8  7  8  7  8  9  8  9 10  9 10 11 10 11 12
 9  8  9  8  9  8  9  8  9  8  9 10  9 10 11 10 11 12 11
 8  9  8  9  8  9  8  9  8  9 10  9 10 11 10 11 12 11 12
 9 10  9 10  9 10  9 10  9 10  9 10 11 10 11 12 11 12 13
10  9 10  9 10  9 10  9 10  9 10 11 10 11 12 11 12 13 12
11 10 11 10 11 10 11 10 11 10 11 10 11 12 11 12 13 12 13
10 11 10 11 10 11 10 11 10 11 10 11 12 11 12 13 12 13 14
11 12 11 12 11 12 11 12 11 12 11 12 11 12 13 12 13 14 13

我们发现有几个点需要特殊判断一下：

• $(1,0)$ & $(0,1)$

这两个点的值都是 $3$。

• $(2,2)$

这个值是 $4$。

单独讨论之后可以算出最基础的值，即：

$$num = \max(\lceil \frac{x}{2} \rceil,\lceil \frac{y}{2} \rceil,\lceil \frac{x+y}{3} \rceil);$$

我们又需要考虑额外的附加值，即：

$$(x \oplus y \oplus num) \& 1$$

这样马也就计算完了。

# Week 5

# Monday（3.30）

P4364 [九省联考 2018] IIIDX

这是三月份最后一场了。

• 赛时

想到一种错误的解法，可以考虑对于位置 $x$ 有多少个值是要 $\ge d_x$，这里提示我们可以考虑向受它影响的点建边然后计算子树内的点的数量，贪心去取即可获得 60pts。

为什么错了呢，hack 是这个： 4 3 1 1 2 2 这里我们会输出 1 1 2 2 但事实上 1 2 2 1 也是一个正确的选择。

通过这组数据我们发现，基于 DFS 的贪心都不能够确保正确性，由于存在重复，所以儿子节点可能可以选择和父亲节点相同的数，把更大的数留给其他节点，使解更优。

• 赛后

我们发现，假如我们要选的数为 $x$，那 $sz_x$ 一定是 $\le f_x$ 的，其中 $f_x$ 表示剩余的 $\ge x$ 的数的后缀和。

这里我们就可以考虑对于同一层的数来集中求解。

因为要求字典序最小，所以父亲选的值越大越好，如果说父亲选的值的数量不只一个，那父亲选择最靠前的一个一定是更优的，这样儿子的选择就更多了。

这样提示我们可以考虑线段树二分来解决问题，每次选完之后要给儿子留下足够的点数，于是需要减去自己的子树数量。

查询儿子时，只需考虑父亲节点是否还原了再查询即可。

# April

# Week 1

# Wednesday（4.1）

P15567 [COCI 2025/2026 #5] 五步 / Pet

咋说，赛时的转移，初始化都没问题，只是从 93pts -> 110pts 的优化炸了，直接 0pts。

link

转移是简单的，我们考虑记录 $f_{i,j,k,0/1}$ 表示走 $k$ 步走到 $(i,j)$ 且最后一步是横 / 竖着走的方案数。

转移是显然的：

$$f_{i,j,k,0} = \sum _{l=1} ^ {n} f_{l,j,k-1,1} - f_{i,j,k-1,1} \\ f_{i,j,k,1} = \sum _{l=1} ^ {m} f_{i,l,k-1,0} - f_{i,j,k-1,0}$$

用前缀和优化即可。

我们发现，在只走 $5$ 步的情况下，只有可能最后一步和第一步重合，只会形成一个长方形。

于是开始考虑枚举长方形的左上角与右下角进行容斥，这样就获得了 0pts 的好成绩。

事实上，我们可以考虑设第 $i$ 行与第 $j$ 行有 $k$ 个都有荷叶的位置（$i < j$），用答案减去 $k \times (k-1) \times 4$ 即可，这样你可以获得 93pts。

我们考虑用 bitset 优化这一过程，这样复杂度就是 $O(nm + \frac {n^2 m} {w})$。

# Thursday（4.2）

P13308 故障 & P12247 跳舞机

不想多说（至少现在）： f[i-k] -> f[i-k+1] 。

“身为迷失的孩子，即使那么不情愿，也还是需要那份爱吗？”

真 TM 想死。

• P12247 跳舞机

我们可以考虑维护这个明显具有单调性的三维偏序问题，如果没有考虑兴奋值，这只需一个 set 即可，在考虑兴奋值的情况下用两个 set 维护一下即可。

• P13308 故障

不想多说了，直接暴力 $O(n^2 m)$ 离散化一下再加上卡常，可以做到 $O(nm \log m)$。

# Week 2

# Tuesday（4.7）

P15939 [JOI Final 2026] 传奇团子吃家 / Legendary Dango Eater & AT_joi2026final_a 伝説の団子食通 (Legendary Dango Eater)

依旧 JOI，依旧写不出来。

我们考虑 $O(q n)$ 的暴力，这里给出一个性质，我们记录 $s$ 表示上一位剩余的数量，发现当 $s \ge 0$ 时它所做出的贡献正是 $\frac {sum} {k}$ 其中 $sum$ 是前缀和。

对于 $s<0$ 的情况，但这时 $s$ 取到 0，再继续往后遍历。

这可以视作重新开始，于是将整个过程分为若干段，每段从 $s=0$ 开始，一直到 $s<0$ 结束，然后重置 $s=0$，开启下一段。

若我们将每走一段看做 “跳”，那么从任意点开始 “跳” 的路径是确定的，所以倍增预处理出来，查询时倍增跳即可。

这里可以考虑用颜色均摊或线段树维护，时间复杂度 $O(n \log n)$。

# Wednesday（4.8）

P14645 [POI 2025/2026 #1] 传话 / Dostawy

link

我们发现贪心是好想的，只需考虑每个点所到达的最短时间，按照时间大小从大往小排序即可。

因为不同出发的点都带有权值（即它的出发时间），这个东西是不好维护的，但我们可以发现它的出发时间每次最多只会 $+1$ 或 $-1$，而这个操作又是区间修改，这提示我们往线段树上想。

我们可以用线段树维护区间最大值，这样查询是 $O(1)$ 的，我们考虑对于未出现的时间，这些点是不需要更新的，所以初始值可以直接赋为 0。

考虑对于时间 $\ge$ 新的时间的点是无需改动的，接下来考虑 $<$ 它的部分。

我们发现加入与删除的性质相同，考虑加入即可。

我们发现对于完全 $<$ 加入的时间只需区间 $+1$ 就可以了。

但对于 $=$ 它的点只需修改有多少个数 $\ge$ 它即可，这一点可以用树状数组维护。

赛时没想到可以直接区间减去之前的权值，原本以为需要在 push_up 时来完成，复杂度就变为了 $O(n \log ^2 n)$。

# Friday/Thursday（4.9/4.10）

P11022 「LAOI-6」Yet Another Graph Coloration Problem & P12415 「YLLOI-R1-T4」枫

依旧绿绿得紫，依旧切 T2，不切 T1。

事实上现在还不知 T1 为何 WA。

• P11022 「LAOI-6」Yet Another Graph Coloration Problem

我们可以考虑边双缩点后看连接两个边双的路径的两点必须是同一颜色，而边双内部的点是啥颜色都可以，用并查集优化即可。

• P12415 「YLLOI-R1-T4」枫

我们发现可以考虑每一层对答案做出的贡献，这需要考虑之前所出现点的数量（即考虑有多少个点能作为这一层点的父亲），剩下的就是 DP 或 DFS 解决了，定义 $f_{i,j}$ 表示还剩 $i$ 层且前面有 $j$ 个父亲可以选择，转移是显然的：

$$f_{i,j}=\sum ^{m} _{k=0} f_{i-1,j+k} \times j^k \times \binom {m} {k}$$

# Week 3

# Monday（4.13）

P3523 [POI 2011] DYN-Dynamite

难崩的是只需把我自认为错误的 40pts 暴力删掉一维，改一下参数就过了。

容易的是想到二分答案，考虑二分最短时间 $val$。

我们考虑定义 $f_{i,0/1}$ 分别表示在 $i$ 的子树内没有被覆盖到的点到 $i$ 的距离和距离 $i$ 最近的起始点的位置。

当然，初始情况下的转移是显然的：

$$f_{i,0} = \min _{v \in son_i} f{v,0} + 1 \\ f_{i,1} = \min _{v \in son_i} f{v,1} + 1$$

剩下就是分讨了：

• $f_{i,0} + f_{i,1} \le val$

这样子树内都会被覆盖完，重置一下 $f_{i,0}$ 即可。

• 如果说 $i$ 号点上有炸药且 $f_{i,1} > val$

我们可以考虑扔给它的父亲节点来处理，即：$f_{i,0} = \max {f_{i,0},0}$。

• $f_{i,0}=val$

这种情况下必须选择 $i$ 了，然后让统计个数的 $cnt$ 加一，重置 $f_{i,0/1}$。

最后特判一下根即可。

# Tuesday（4.14）

P11187 配对序列 & P12000 扶苏出勤日记

为何把 T2 的前缀和写错、没开 long long 、写 st 表查询写成 $O(\log n)$ 的了呢？

• P11187 配对序列

考虑用记录 $f_{i,0/1}$ 表示当前结尾为 $i$ 且长度为偶数 / 奇数的最长距离。

转移是显然的：

$$f_{a_i,0} = f_{a_i,1} + 1 \\ f_{a_i,1} = \max _{j \not = a_i} f_{j,0} +1$$

发现对于 $f_{i,1}$ 是可以用数组维护的，我们可以考虑用线段树来维护 $f_{i,0}$。

• P12000 扶苏出勤日记

很明显，这题是具有二分性质的，我们可以考虑二分答案。

对于二分出来的数 $x$，我们考虑贪心的留下尽可能多的钱为后续买币提供便利。

每当当前所存的币不够是，我们要考虑尽量用早出现的钱来花费（记录 $l$ 表示最早的还剩钱的时间），我们考虑在剩余钱在 $a_i$ 最大的时间来花费钱即可。

查询 $(l,i)$ 之间花费最大的位置可以用 st 表来实现。

# Wednesday（4.15）

P3545 [POI 2012] HUR-Warehouse Store

为何没有判 !q.empty() ? 被 STL 背刺的一天。

做题 20 分钟，写 check 半小时。

事实上，我们发现如果当前这个点比之前的选的数出现的最大值要小，那可以把之前这个最大值所在编号的点弹出，并把之后的值往前移动一位即可。

对于最后一步，可以在最后来处理。

# Tuesday（4.16）

P15093 [UOI 2025 II Stage] Odd Rows

link

不难想到这是一个我为人人的 DP，我们定义 $f_{i,j}$ 表示对于前 $i$ 列能否做到其中有且仅有 $j$ 行存在奇数个 1。

我们发现对于 $f_{i,j}$ 它所能转移到的位置是一个区间，并且这个区间中只有奇数或者偶数能被修改，这提示我们可以拿一颗线段树来维护 $f_{i+1,x}$。

答案显然是所有的 $f_{m,j} = 1$ 中 $j$ 的最大值，这样你可以获得 50pts。

我们考虑答案的构造，我们需要知道当第 $i$ 列构造完了有多少行包含奇数个 1，我们发现，对于这个是好维护的，倒着再模拟整个过程一次就可以了。

考虑记录第 $i$ 列结束后有 $g_i$ 个位置包含奇数个 1，那对于第 $i$ 列，我们考虑它相较于第 $i-1$ 列多出现了几个位置包含奇数个 1（记为 $p$）。

我们发现，对于剩下的值即 $c_i - p$ 均匀的覆盖包含和不包含奇数个 1 的位置即可。