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

[[ slider_text ]]

[[ item.c ]]

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

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

数位dp 中位数 线性基

## 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)

### 数位dp视角
首先不难推出，真正要填的位就是`K = topbit(l ^ r)`
如果第`K`位`x`填上`0`，那么对`l, r 的 [0...K-1]`位**截断**，下界依然是`l`，上界依然是`r`
如果第`K`位`x`填上`1`，那么**截断**`[0...K-1]`位之后，下界是`r`，上界是`l`

**数位 dp 主要做两件事情**，枚举`x in {0, 1}`，检查有没有爆上界/爆下界的

对于下界，我们希望从`>= 下界`的数中间选出某个数`?`，使得$$\oplus x$$的值尽可能小
如果这个最小值都`>= 下界`，那么当前`x`填法就合法

对于上界也是类似的，希望从`<= 上界`的数中，选出$$\oplus x$$的值尽可能大的
如果这个值都`<= 上界`，`x`的填法就合法

> 第一，保证选取的数在区间内

那么我们希望从`l`中得到什么数呢？如果`第 k 位填 0`，那么`l 作为下界`，我们希望选`x`
这样异或起来就是`0`，尽可能小，`第 k 位填 1`的话，`l 作为上界`，希望选`x ^ 1`
```bash
wantl = !rev ? x : (x ^ 1)
```
但是这个`wantl`并不是总能取得到，因为你取的这个数，受到`tightl`的制约\

如果你选的数高位前缀跟`l`的一样，你怎么保证接下来选的一定`>= l`呢？
如果`l >> i & 1 = 0`，那么你可以选到`{0, 1}`都可以，否则呢，`l 第 i 位是 1`，你只能取`1`
所以实际上`takel = (tightl and li == 1) ? 1 : wantl`

但是，你`takel`选走的数，一旦出现某个位已经`> l`了，之后就可以放飞自我了，`{0, 1}`都随便选
此时`tightl`的限制解除，所以`ntightl = tightl and (takel == li)`

> 第二，保证$$\oplus x$$异或后，生成的数在区间`[l, r]`内

以下界举例，如果`rev = 0`，那么我们用`takel`来生成**最小值**，这个值如果$$\geqslant l$$就合法
怎么判断呢？还是设计数位`dp`的状态
我们生成的这个数第`i`位就是`mni = takel ^ xi`，跟`li`去比较

如果之前这个数的某个高位已经比`l`对应的大了，那么不管怎么样都会满足
否则生成的数的高位前缀跟`l`的一样，那么`mn < li`就一定不满足

于是在数位`dp`中还需要设计一个状态，`lo`表示下界是否是**紧致**的
这里紧致的定义，表示高位前缀一样

状态转移就是`nlo = lo and (mni == li)`

#### 算法实现
```bash
const int LOG = 53;

void solve(int cas) {
    i64 l, r;
    cin >> l >> r;

if (l == r) {
        cout << "0\n";
        return;
    }

// rev, i, tightl, sl, tightr, sr
    static i64 dp[2][LOG+5][2][2][2][2];
    memset(dp, -1, sizeof(dp));

auto dfs = [&](this auto &&self, int rev, int i, int tightl, int tightr, int lo, int hi) -> i64 {
        if (i < 0) return 1;
        auto &res = dp[rev][i][tightl][tightr][lo][hi];
        if (res != -1) return res;

res = 0;
        int li = l >> i & 1, ri = r >> i & 1;

for (int xi : {0, 1}) {
            int wantl = !rev ? xi : (xi ^ 1);
            int takel = (tightl and li == 1) ? 1 : wantl;

int wantr = !rev ? (xi ^ 1) : xi;
            int taker = (tightr and ri == 0) ? 0 : wantr;

int nlo = lo, nhi = hi;
            if (!rev) {
                // l -> mn, r -> mx
                auto mni = takel ^ xi;
                if (lo and mni < li) continue;
                nlo = lo and (mni == li);
                
                auto mxi = taker ^ xi;
                if (hi and mxi > ri) continue;
                nhi = hi and (mxi == ri);
            }
            else {
                // l -> mx, r -> mn
                auto mni = taker ^ xi;
                if (lo and mni < li) continue;
                nlo = lo and (mni == li);

auto mxi = takel ^ xi;
                if (hi and mxi > ri) continue;
                nhi = hi and (mxi == ri);
            }

res += self(rev, i-1, tightl and (takel == li), tightr and (taker == ri), nlo, nhi);
        }

return res;
    };

auto K = topbit(l ^ r);
    i64 ans = dfs(0, K-1, 1, 1, 1, 1) + dfs(1, K-1, 1, 1, 1, 1);
    ans -= 1;

cout << ans << "\n";
}
```

上一篇：2026年二月算法竞赛选题（一）下一篇：2026年四月算法竞赛选题（一）

看完文章有啥想法