2026年二月算法竞赛选题（二）

[[ slider_text ]]

[[ item.c ]]

2026年二月算法竞赛选题（二）

发布时间 2026-04-27 作者：秋千月 来源：算法小站

中位数 线性基

## Codeforces Round 1081 (Div. 2)
### D
**[D. Cost of Tree](https://codeforces.com/contest/2192/problem/D)**
给定一棵根是$$r$$的树，每个节点`u`有点权`a[u]`，这棵树的成本定义成
```math
\sum_{u \in T} (a_u \cdot d(r, u))
```
其中$$d(r, u) = dep(u) - dep(r)$$
对每个$$T_r \in 1 \sim n$$独立回答下面的问题，这里的$$T_r$$考虑`r 及其子树`（仍然是`1`为根）
对子树进行**最多一次**操作之后，求子树的最大成本
每次操作断开任意节点$$v, v \neq r$$，然后把它接在子树中任意一个节点$$u$$后面

**算法分析**
> 不进行操作，代价怎么算

实际上可以用**递推**，考虑$$v \to u$$的过程
假设说$$v$$及其子树的代价我们已经算好了，记为$$dp(v) = \sum a_i \cdot d_i$$
那么从$$v \to u$$，实际上应该求$$\sum a_i\ \cdot (d_i + 1) = (\sum a_i \cdot d_i) + \sum a_i$$
也就是说，有$$dp(u) = dp(v) + \sum a_i$$，	其中$$i \in T_u$$

> 还可以怎么算？

考虑`u 及其子树`，$$\sum a_v (d_v - d_u) = \sum a_v d_v - d_u \sum a_v$$
预处理深度`d`的话，也可以算出来

> 操作的话又会怎么样呢？一定是把一个儿子及其子树**整个拆下**，接在另一个**深度最深的链**之后

可以考虑贪心，假设说`u`只有一个儿子，那么没有`u`什么事情了，我们要考虑的在`u`的某个
**有分叉的儿子`v`的时候**再考虑

现在考虑`u`的儿子$$(v_1, v_2, \cdots)$$，按链的深度$$h_v$$对儿子排序
情况一，枚举$$(v_2, \cdots)$$所有的儿子，将其接到最深的儿子处
这样耗费的额外代价是$$\Delta = h(u) \cdot S(v)$$

其中$$S(v) = \sum\_{i \in T\_v} a\_i$$

情况二，将**最深的儿子**拆下来，即$$v_1$$拆下，接到第二深的儿子上，即$$v_2$$
那么代价变化是$$\Delta = (h(v_2) + 1) \cdot S(v_1)$$

针对上面两种情况，求出$$\max \Delta(u)$$，最后的答案就是$$dp(u) + \max \Delta(u)$$

## Codeforces Round 1083 (Div. 2)
### D
**[D. Simons and Beating Peaks](https://codeforces.com/contest/2205/problem/D)**
一个序列是好的，当且仅当不存在波峰，即$$b\_i = \max(b\_{i-1}, b\_i, b\_{i+1})$$
现在给你一个长度是`n`的排列，问你想把他变成好的，需要的**最小操作次数**
每一次操作，选择一个满足$$a\_i = \max(a\_{i-1}, a\_i, a\_{i+1})$$的`i`，删除$$a\_{i-1}$$或者$$a\_{i+1}$$

**算法分析**
不难发现，最大值一定删不掉，那么问题就变成了，找到最大值的位置$$p$$
分两种情况，往左，往右下降，构成`V`字形

对于每种情况，枚举`V`字形波谷的位置，然后往左往右求**最长下降子序列**好像就可以了？

但这还有一个**坑点**，一般问题下的`LDS/LIS`中间都可以跳过元素的
枚举以$$y$$结尾的最长子序列的长度，$$dp(i) = (\max\_{y > a\_i} dp(y)) + 1$$

在这个问题中，你选了$$a_i$$，以$$a_i$$结尾，就意味着之前如果出现了$$[1, a_i - 1]$$这些数
这些数**是过不来的，被**$$a_i$$卡住了，所以要区间修改$$[1, a_i-1] \to 0$$

## Codeforces Round 1094
### C
**[C. Median Partition](https://codeforces.com/contest/2222/problem/C)**
给定长度为**奇数**的序列，要求你划分成若干长度为**奇数**的子序列，子序列必须连续
要求每个子序列的中位数都相同，并且最大化子序列的个数

**算法分析**
为什么强制是奇数？每个子序列的长度是奇数，总长度也是奇数？

要么不划分，最后的那个中位数一定等于整个序列的中位数

划分的话，每一段长度都是奇数，并且这些段的中位数都相等，不妨设为`M`
每一段$$\leqslant M$$和$$\geqslant M$$的数都抵消，这样分成若干**奇数的段**
这些奇数的段合并，就是`[M, M, ... 奇数个 M]`，中位数一定是`M`

而不等于`M`的数呢？每一个$$\leqslant M$$的数都可以找到$$\geqslant M$$的数配对
抵消掉，所以最后这个相同的中位数是**确定的**，一定等于整个序列的中位数

这样，`dp(i) = max(dp(j) + 1)，[j+1...i] 是合法的段`
合法的段，首先长度是奇数，其次`< med 的个数 <= len / 2`，并且`> med 的数的个数 <= len / 2`

### D
**[D. Permutation Construction](https://codeforces.com/contest/2222/problem/D)**
构造一个排列，给定一个序列`a`，定义逆序对$$(i, j)$$的价值是
```math
\sum_{k = i}^{j-1} a_k
```
要求构造`n`的排列，使得逆序对**价值之和最大**

**算法分析**
最后的价值之和，求前缀和
```math
\displaystyle
\sum_{i, j} S(j-1) - S(i-1), \quad (i, j) \text{构成逆序对}
```
算贡献，对于特定的下标$$x$$，$$S_x$$什么会被加多少次，减多少次？

> 什么时候$$S_x$$会被加？

对于$$(i, x+1)$$，有$$p\_i > p\_{x+1}$$，如果$$x$$是确定的，那么只要看，$$< x+1$$的位置
即$$x$$左边，包括$$x$$，有多少个数满足$$> p\_{x+1}$$

> 什么时候$$S_x$$会被减

对于$$(x+1, j)$$，有$$p\_{x+1} > p\_j$$，换句话说，$$x$$右边$$> x+1$$的位置
有多少个数$$< p\_{x+1}$$

```bash
cnt = (x 左边包括 x 有多少个 > p[x+1] 的数) - (x 右边不包括 x 有多少个 < p[x+1] 的数)
```
不妨设$$x$$左边包括$$x$$，`> p[x+1]`的数是`lar`，那么$$x$$左边`< p[x+1]`的数就是$$x - lar$$

那么$$< p[x+1]$$的数一共有`p[x+1] - 1`个
所以第二项的值是`p[x+1] - 1 - (x - lar)`

由此`cnt = lar - (p[x+1] - 1 - x + lar) = x + 1 - p[x+1]`

从而$$S\_x$$对答案的贡献是$$((x+1) - p\_{x+1}) \cdot S\_x$$

由此$$(x+1) \cdot S\_x - p\_{x+1} \cdot S\_x$$，其中$$(x+1) \cdot S\_x$$是确定的
而$$-p\_{x+1} \cdot S\_x$$是我们要构造的，这一项要尽可能小

排序不等式，对$$S[0...n-1]$$排序，然后`S[0] 对应放 p[1] = n`
`S[1] 对应放 p[2] = n - 1`，这样就是最优的

## Codeforces Global Round 31
### E
**[E. No Effect XOR](https://codeforces.com/problemset/problem/2180/E)**
给定区间$$[l, r]$$，求有多少个$$x$$，满足对于区间所有数$$i \in [l, r]$$，$$i \oplus x  \in [l, r]$$
即$$[l, r] \oplus x \to [l, r]$$

**算法分析**
![](/media/content_img/global31-E1.png)
![](/media/content_img/global31-E2.png)
![](/media/content_img/global31-E3.png)
![](/media/content_img/global31-E4.png)
![](/media/content_img/global31-E5.png)

上一篇：2026年二月算法竞赛选题（一）已经是最后一篇啦

看完文章有啥想法