提高+/省选-

P15352 [COCI 2025/2026 #4] 魔术 / Magija 思路 倍增并查集，以下描述忽略反阿克曼函数 $\alpha(n)$。 首先考虑直接 $O(nq)$ 的维护，显然简单，用并查集维护哪些点可以相互到达，合并时压缩路径并统计答案，数据比较水所以甚至有 $73$ 分。 ▶ [73 pts Code] 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071#include<bits/stdc++.h>#define fir first#define sec second //#define int long long#define pii pair<int,int>#defin...

P15093 [UOI 2025 II Stage] Odd Rows 思路 首先考虑求答案的 subtask。 我们考虑维护四个值：$jmx,jmi,omx,omi$ 分别表示奇数和偶数的最大最小可能取到的值，$cnt$ 表示本次要填入多少个 $1$，发现 $jmx+omi=n,jmi+omx=n$，所以更新时只需要更新两个最大值。 对于 $jmx$ 有三种情况： $omi\ge cnt$：此时一定是将所有 $cnt$ 个 $1$ 都放在原先是偶数的位置最多，即更新为 $jmx+cnt$ 个。 $omx\le cnt$：此时无论怎么选，都一定会有一部分奇数被转为偶数，而所有偶数都被转为奇数，所以新的奇数最大值就是总数减去被转换的奇数数量，要使得这个东西最大，只需使得被转换的奇数最少，即偶数最多，取 $omx$，更新为 $omx+jmi-(cnt-omx)$。 $omi\le cnt\le omx$：这是最重要的一种情况，同时需要用到本题的关键结论：一种数一定可以取到上下界之间所有与上界（下界）奇偶性相同的所有数，也就是 $o\in [omi,omx],o\equiv omi(...

P16318 [ICPC 2023 Jinan R] 彩虹子数组 思路 首先注意到一段公差为 $1$ 的等差数列等价于将所有值减掉其位置后的连续相等数。 所以先给每个 $a_i$ 减掉 $i$，这样就把原问题转化为求一段连续相等区间的代价。 此时对于一段区间成为彩虹子数组的代价即为所有数都向上或向下变成同一个数的代价。 则这个最终数显然是中位数。 求出中位数，然后把所有数往中位数靠近，维护大于，小于中位数的各有多少个和它们的值的和，然后大的值的和减去中位数乘以大的的个数，中位数乘以小的的个数减去小的值的和，两部分相加即为代价。 若某区间可实现在 $k$ 代价之内成为彩虹子数组，则其子区间区间也可实现（少操作一部分数，代价显然更小），所以可以用双指针来优化这一部分。 中位数部分，由于有增加也有删除，优先队列不太好做，我用的是可重集。 代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566...

B4281 [蓝桥杯青少年组国赛 2023] 月球疏散行动 思路 显然直接考虑 DP。 我们设 $f_{tim}$ 表示在时间为 $tim$ 时可以发车的情况中的等待时间最小值，且每次发车一定是接走所有人。 也就是说上一次发车一定最晚在 $tim-m$，不然此时就还在路上。 先对所有人的抵达时间排序。 每次发车造成的等待时间总和按照定义就是所有人的到达时间与本次发车时间的差值，也就是等待人数乘以本次发车时间，再减去这些人的到达时间总和。 等待的人在一段连续的区间内，对于某发车时间可带上的最晚到达的人的编号 $ed$ 和不可带上的最早的人的编号 $pl$ 数组可以由二分求得，而他们的到达时间可以前缀和到 $s$ 数组，在这里做预处理。 两次发车时间的间隔至少为 $m$，至多为 $2\times m-1$，若大于了上界，则可以在不影响这两次的前提下在中间多发一次车，一定不劣。 对于所有 $t$，假设这是首次发车，那么等待时间就为 $ed\times i-s_{ed}$，可以对 $f_t$ 赋这个值作为初始化。 然后正式开始 DP。 可以容易的得到转移方法，对于 $i\in[1,t_n...

P14645 [POI 2025/2026 #1] 传话 / Dostawy 思路 首先我们一定将先招募的英雄派遣至更远的堡垒。 每个英雄在出发后一定互不干扰，且走的是到达目的地的最短路。 证明 假设会在某点相遇，导致某个英雄无法继续行走。 先出发的在到达前会一直在行进的路上，先到达相遇点。 若其后到达或与另一名同时到达，则一定不是走的最短路线，不成立。 在其到达终点后，若另一名继续行进，被其阻挡，则另一名要么走的不是最短路，要么路径更远，均不符合要求。 故假设不成立，得证。 然后障碍的数量不会增多，位置也不会改变，所以不管某位置上是不是堡垒，从出发点到它的所需时间都不会变。 这个时间我们可以用 bfs 求，最劣 $O(n^2)$。 然后因为英雄们互不干扰，所以我们可以把问题转化为一维的。 设所有所需时间从大到小排序后的数组为 $dis$，共有 $cnt$ 个。 则最开始出发的会在 $dis_{cnt}$ 时间内走完，而每晚出发的一位，其所用时间都会是 $dis_i+(cnt-i)$。 那么我们对这个东西求 $\max$ 就是最终答案。 但是线性仍然不够优秀，所以考虑用权值线段树...

题解：P15567 [COCI 2025/2026 #5] 五步 / Pet 思路 我们发现一共经过 $5$ 片荷叶等同于跳 $4$ 次。 而如果每次都不是原地跳的话，只有跳出一个矩形才会造成第 $5$ 片和第 $1$ 片是同一片。 但是我们很难限制在中途不形成矩形，否则会产生很多种状态，所以考虑正难则反。 首先忽略不形成矩形的条件。 那么可以很容易地得出一个状态：$f_{x,y,i,0/1}$ 表示现在在 $(x,y)$，一共跳了 $i$ 次，上次跳了 $0/1$ 的方向（分别代表同一列和同一行）。 转移也不是很难想，$f_{x,y,i,0}=\sum_{j=1}^{m}f_{x,j,i-1,1}-f_{x,y,i-1,1}$，同理可得 $f_{x,y,i,1}=\sum_{j=1}^{n}f_{j,y,i-1,0}-f_{x,y,i-1,0}$。 对式子进行分析，首先若此次的转移方向是同一列，则是要从所有同一列的少跳一步且上一次是同一行的状态转移而来，并且由于不能原地跳，所以还要再减掉由自己转移而来的状态。 但是这个时间复杂度无法接受，那么先提前对每一行和每一列的值做加和预处...

CF266D BerDonalds 思路 最小直径生成树板子题。 假设答案是 $ans$。 首先发现 $n$ 是非常小的，所以我们可以先用 Floyd 跑出所有点两两之间的距离。 然后最优点可能在点上，也可能在边上。 我们先考虑在点上的情况。 假设 $i,j$ 之间的距离为 $dis_{i,j}$，那么将中心设在 $u$ 时，最大距离即为最大的 $v\in [1,n],dis_{u,v}$。 枚举所有点，找到最小的一个最大距离，更新 $ans$。 然后考虑在边上的情况，容易发现一定是在最长的一条路径的中点会最优。 存下所有边并枚举，假设端点是 $u,v$，长度是 $w$。 那么点 $a$ 到达取到点的距离即为 $dis_{u,a}$ 加上 $u$ 到取到点的距离和 $dis_{v,a}$ 加上 $v$ 到取到点的距离。 假设 $u$ 到取到点的距离为 $x$，则 $a$ 到取到点的距离为 $\min{dis_{u,a}+x,dis_{v,a}+(w-x)}$。 那么这个东西的左边值与 $x$ 同增，右边值与 $x$ 同减。 当 $x$ 取到特定值的时候可以让左右两个值相等。 画出...

P9322 [EGOI 2022] Superpiece / 超级棋子 思路 显然难点在于骑士。 较近的几个点步数可以由枚举得到。 我们考虑转移方法。 一个点可以向所有与它距离为 $2$ 的点用两步扩展，也可以向与它横纵坐标距离均为 $1$ 的点用两步扩展。 结合初始几个点所需的步数，易得最终大概是这样的（搬一张以前题解的图）： 1234567891011121314151617181920212223 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...

P9923 [POI 2023/2024 R1] Przyciski 思路 首先看到 01 矩阵，还是关于行和列的计算，考虑从每个点的行向这个点的列连边。 容易发现这是一个二分图，但是其实没什么用（行与行，列与列之间显然无法连边）。 最后我们要使每个点的度数相同。 首先考虑偶数情况，是容易的，选出一个环，环上的点均度数为 $2$，不在环上的点度数均为 $0$ 即可构造。 这一部分直接 dfs 即可。 然后是奇数情况。 首先若有环，则偶数情况成立，不会考虑，故此时图上无环，是一个森林。 我们发现叶子的度数均为 $1$，无法增加到更大的奇数，所以考虑从叶子到根枚举，若其父亲度数为偶数则断掉父亲到父亲的父亲的连边（不能断掉其与儿子的连边，否则儿子的度数会变为偶数），若父亲为根节点且度数为偶数，则不成立。 代码 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747...

CF1919D 01 Tree 模拟赛赛时做了一道非常类似的题，但题面是一条为 $0$ 的边和一条可能为 $0$ 或 $1$ 的边，修改合并条件后就能通过此题。 与现有题解做法均不同（雾），求通过。 思路 因为这道题目中的两条边都是固定的，所以为 $0$ 的节点一定有且仅有一个。 我们不考虑拆分点，而是合并点，将新点权设为。 发现两点之差为 $1$ 的时候就可以合并这两个点。 那我们考虑维护四个值：$l_{mi},l_{mx},r_{mi},r_{mx}$ 分别代表某个区间从左/右开始往中间合并能合并出的最大/小值。 显然最大值和最小值之间的所有值都是可以取到的。因为合并的值最大差值为 $1$，并且必须连续。 不妨维护多个区间的这四个值，判断可否合并，再判断最后剩下的那个区间最小值是否为 $0$ 即可。 具体的： 两个最小值显然都更新为合并完所有点后的值； 左/右最大值为左/右边区间的左/右最大值，因为它们显然无法变的更大，也不需要变小； 若一个区间的合并方向最大值加 $1$ 后还是小于另一个区间的合并方向最小值，显然无法合并。 若两个区间的合并方向的四个值均相等，则这两个值只能...