House_of_Fan

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$ 取到特定值的时候可以让左右两个值相等。 画出...

题解：CF2211C1 Equal Multisets (Easy Version) 思路 考虑什么情况下不成立。 如果 $n>2\times k$，一定需要使得每个 $a_i$ 都与 $b_i$ 相等，否则一定会存在一个子序列包含某个不该在此子序列中的值而少了一个应该在此子序列中的值；而如果 $n\le 2\times k$，在中间的某一段由于被每个子序列都使用且没有被分开使用，所以可以是乱序的。 换句话说，我们发现对于每个 $k$，都有区间 $[1,n-k]$ 和区间 $[k,n]$ 被多个子序列使用，且某个值被一些区间使用而不被另一些区间使用，所以必须使得 $\sum_{i=1}^{n-k} a_i=b_i$ 且 $\sum_{i=k}^{n} a_i=b_i$。 而如果有某个值出现或被给出的次数超过了一次，则一定不成立，因为它无法同时出现在两个位置，这样会导致某个区间中的值少一个，无法与 $a$ 中的子序列相等。 按照上面的两步模拟即可。 代码 1234567891011121314151617181920212223242526272829303132333435...

CF2211B Mickey Mouse Constructive 思路 容易发现这个题把所有 $1$ 和 $-1$ 分开放一定是不劣的。 首先交换 $1$ 和 $-1$ 的个数是与原问题等价的，这样只是将所有值的正负性取反，不影响分配，该相等的依旧相等，不相等的依旧不相等。 假设 $1$ 的数量较少，在前面连续放，$-1$ 则在后面连续放。 那么平均值一定是非正的，若是正的，则后面一定会剩下一段 $-1$，最终无法凑出正的值。 所以我们将前面的所有 $1$ 与等量的 $-1$ 绑定在一起，和为 $0$。 如果此时后面没有剩余的 $-1$，则只有这一种情况，而如果有的话，情况数则为剩余 $-1$ 个数的因子数量。 即问题求 $|x-y|$ 的因子数量，若为 $0$ 则是 $1$。 代码 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include<bits/stdc++.h>#define fir first#define sec ...

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...

P15819 [JOI 2015 Final] 舞会 / Ball 思路 首先我们发现直接做是困难的，所以考虑二分最后一个贵族的 $d_i$ 大小大于等于多少。 有一个很经典的 trick：将所有 $\ge d_i$ 的贵族改为 $1$，其他改为 $0$。 考虑到我们最后若想要此种情况成立，需要最后留下来的贵族是 $1$ 才行。 我们观察题目的操作，容易得出当知道所有数时，可以用 deque 来维护。 定义 deque 中的每一位是当前局面下使得这一位为 $1$ 的最小值。 那么对于初始固定的位置，若它对应的贵族是 $1$，则值是 $0$，若是 $0$，则设为极大值。 若这个位置没有初始值，则设为 $1$，因为需要往这里填入一个是 $1$ 的贵族。 按照题意模拟，每次取出前三个，若要使得加到最后的是 $1$，则前三个中必须至少有两个 $1$，枚举三种情况，取最小值，将其加到末尾。 最后因为每次会删除三个，增加一个，所以就是减少两个，又因为初始是奇数，所以相当于最后一定只剩一个。 将最后这一个提取出来，并判断它为 $1$ 时所需要的 $1$ 数量是否小于等于总的 $1$ 数量即可。...

P15399 [NOISG 2026 Prelim] Area 2 水题解来的。 思路 矩形由两组长度相同的对边，即两对长度相同的边组成。 矩形的面积由这两对边的长度的乘积决定。 若存在更长的边，用其替换更短的一定不劣。 故此题答案为最长和次长的两对边的长度乘积。 用一个变量存最长的，一个变量存次长的。 若当前枚举的值是 $x$，最大值为 $fir$，次大值为 $sec$。 若 $x>fir$，则 $x\to fir$； 若 $x\le fir,x>sec$，则 $x\to sec$； 其他情况不修改。 代码实现简单，就不放了。