专栏文章

*1600~1900 狂做

BBrotherCallIllenials
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miopvzyz
此快照首次捕获于
2025/12/02 23:12
3 个月前
此快照最后确认于
2025/12/02 23:12
3 个月前
查看原文

CF2124D *1700

猜测是找到第 kk 小的数，然后大于它的都可以直接删掉。
如何证明？
对于一个数，在全局的排名为 rkrk，扩展一个端点，排名 +0+0 或 +1+1，最终会扩到 rkrk。也就是说若 rk>krk > k，一定会有一个区间它的排名为 kk。
然后和第 kk 小的数相同的怎么处理呢，两边往中间扫看最多能留多少个，如果最后留的个数 ≥k−1\ge k - 1 就合法。

CF2123F *1700

首先发现如果一个子序列 {xi}\{x_i\} 有共同的大于 11 的因子，轮换一下就全满足题意了。
现在你发现所有合数都能和它的质因子这么轮换。
选什么质因子轮换呢？我是从小到大枚举质因子，选还没用过的质因子轮换。这个能过。
然后质因子用埃氏筛筛就行了。
思考为什么能过，不难发现 ≤⌊n2⌋\le \lfloor \displaystyle \frac{n}{2} \rfloor 的质数都能参与轮换，>⌊n2⌋> \displaystyle \lfloor \frac{n}{2} \rfloor 都不能参与轮换，这种情况直接把每个数和最大质因子轮换即可。

CF2121G *1900

max⁡(x,y)=x+y+∣x−y∣2\max(x,y) = \displaystyle \frac{x + y + \lvert x - y \rvert}{2}
前者是 ∑i=1ni⋅(n−i+1)\sum\limits_{i = 1}^n i\cdot(n-i+1)。
后者的话，设 00 个数的前缀和为 fif_i，答案是 2fr−r−(2fl−1−(l−1))2f_r - r - (2f_{l-1} - (l - 1))。

CF2121F *1800

感觉这个评高了。
所有大于 xx 的位置像墙一样隔开。
墙内枚举右端点前缀和即可。
有个另解的 trick：对于每一个点 ii，找到左边第一个比 aia_i 大/小 的位置 ll 和右边第一个比 aia_i 大/小 的位置 rr，则 ∑min⁡(i−l,r−i)\sum \min(i - l , r - i) 数量级为 nlog⁡nn\log n。证明参考笛卡尔树上启发式合并。

CF2120D *1800

沟槽鸽巢原理啊。
首先要保证行最短，那肯定是一定存在一列有 aa 个某一个数。
根据鸽巢原理得到答案为 k(a−1)+1k(a-1) + 1。
然后算列有多少种本质不同的种类数，本质不同指出现 aa 次的位置不同且值不同，位置不同为 (na)n \choose a，不同值为 kk，所以乘起来就是本质不同种类数。
所以 n=k(a−1)+1n = k(a - 1) + 1，m=k(na)(b−1)+1m = k {n\choose a}(b - 1) + 1。

CF2117G *1900

找到一条 1→n1\to n 的路径（不要求是简单路径），最小化边最大值和最小值的和。
看起来无从下手，但你发现如果是最小化最大值的话会做，就是直接建最小生成树就行了。
这时候发现你可以在定最大值的时候去找更小的最小值再走回来，或者选一个稍微更大的最大值再找一个超级小的最小值，这个在以 11 为根的生成树上 dp 即可。

CF2117F *1800

首先发现叶节点最多只能有两个。
也就是说最多有一个点有两个孩子，其他都是一个孩子。
然后这棵树的形态其实就定死了，否则答案为 00。
找到有两个孩子的点孩子的两条链的深度即可算下面的方案数，然后和上面的方案数乘起来即可。

CF2117E *1600

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

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...