*1600~1900 狂做

BrotherCall · 2025-07-26 19:23:52 · 个人记录

猜测是找到第 k 小的数，然后大于它的都可以直接删掉。

如何证明？

对于一个数，在全局的排名为 rk，扩展一个端点，排名 +0 或 +1，最终会扩到 rk。也就是说若 rk > k，一定会有一个区间它的排名为 k。

然后和第 k 小的数相同的怎么处理呢，两边往中间扫看最多能留多少个，如果最后留的个数 \ge k - 1 就合法。

首先发现如果一个子序列 \{x_i\} 有共同的大于 1 的因子，轮换一下就全满足题意了。

现在你发现所有合数都能和它的质因子这么轮换。

选什么质因子轮换呢？我是从小到大枚举质因子，选还没用过的质因子轮换。这个能过。

然后质因子用埃氏筛筛就行了。

思考为什么能过，不难发现 \le \lfloor \displaystyle \frac{n}{2} \rfloor 的质数都能参与轮换，> \displaystyle \lfloor \frac{n}{2} \rfloor 都不能参与轮换，这种情况直接把每个数和最大质因子轮换即可。

\max(x,y) = \displaystyle \frac{x + y + \lvert x - y \rvert}{2}

前者是 \sum\limits_{i = 1}^n i\cdot(n-i+1)。

后者的话，设 0 个数的前缀和为 f_i，答案是 2f_r - r - (2f_{l-1} - (l - 1))。

感觉这个评高了。

所有大于 x 的位置像墙一样隔开。

墙内枚举右端点前缀和即可。

有个另解的 trick：对于每一个点 i，找到左边第一个比 a_i 大/小的位置 l 和右边第一个比 a_i 大/小的位置 r，则 \sum \min(i - l , r - i) 数量级为 n\log n。证明参考笛卡尔树上启发式合并。

沟槽鸽巢原理啊。

首先要保证行最短，那肯定是一定存在一列有 a 个某一个数。

根据鸽巢原理得到答案为 k(a-1) + 1。

然后算列有多少种本质不同的种类数，本质不同指出现 a 次的位置不同且值不同，位置不同为 n \choose a，不同值为 k，所以乘起来就是本质不同种类数。

所以 n = k(a - 1) + 1，m = k {n\choose a}(b - 1) + 1。

找到一条 1\to n 的路径（不要求是简单路径），最小化边最大值和最小值的和。

看起来无从下手，但你发现如果是最小化最大值的话会做，就是直接建最小生成树就行了。

这时候发现你可以在定最大值的时候去找更小的最小值再走回来，或者选一个稍微更大的最大值再找一个超级小的最小值，这个在以 1 为根的生成树上 dp 即可。

首先发现叶节点最多只能有两个。

也就是说最多有一个点有两个孩子，其他都是一个孩子。

然后这棵树的形态其实就定死了，否则答案为 0。

找到有两个孩子的点孩子的两条链的深度即可算下面的方案数，然后和上面的方案数乘起来即可。

敏锐地发现这就是两个波浪形就做完了。