2025年四月算法竞赛选题（一）

[[ slider_text ]]

[[ item.c ]]

2025年四月算法竞赛选题（一）

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

排列与置换 dp计数 背包问题

## Codeforces Round 936 (Div. 2)
### E
**[E. Girl Permutation](https://codeforces.com/contest/1946/problem/E)**
**问题描述**
有一个未知的`n`的排列，给定`premax`和`sufmax`，问排列的方案数
定义$$a_i$$是`premax`，当且仅当$$\forall j < i$$，均有$$a_j < a_i$$
`sufmax`同理，当且仅当$$\forall j > i$$，均有$$a_j < a_i$$

给定`n, m1, m2`，分别是排列的长度，`premax`的个数，`sufmax`的个数
接着`m1`个数，分别是能成为前缀最大值的下标，再给`m2`个数，表示能成为后缀最大值的下标

**算法分析**
![](/media/content_img/cf936e1.png)
![](/media/content_img/cf936e2.png)

## Codeforces Round 940
### D
**[D. A BIT of an Inequality](https://codeforces.com/contest/1957/problem/D)**
**问题描述**
给你一个序列`a[1...n]`，问有多少个三元组$$(x, y, z)$$满足
```math
1 \leqslant x \leqslant y \leqslant z \leqslant n \\
f(x, y) \oplus f(y, z) > f(x, z)
```
定义$$f(l, r) = a\_l \oplus a\_{l+1} \oplus \cdots \oplus a\_r$$

**算法分析**
![](/media/content_img/cf940d.png)

坑点在于`pre 和 suf`在第`T`位都是`0`的时候，实际上`pre`有`pre(y-1, T, 0) + 1`种选择的
最开始的`0`（也就是说， `[1...y]`一整个前缀都选进去的情况），也要计算

## Codeforces Round 979
### E
**[E. MEXimize the Score](https://codeforces.com/contest/2030/problem/E)**
**问题描述**
考虑将数组`b`分成`k`组，$$S_1, S_2, \cdots, S_k$$，其中$$k > 0$$
定义$$b$$的分数是`max value of MEX(S1) + MEX(S2) + ... + MEX(SK)`
现在你有一个长度为$$n$$的数组$$a$$，现在考虑计算它所有的$$2^n - 1$$个非空子数组的分数之和
结果对`998244353`取模

**算法分析**

> 不对`a`进行划分的话，score 怎么算？怎么最大化 mex？

![](/media/content_img/cf979e1.png)

> 考虑 dp

![](/media/content_img/cf979e2.png)

> 优化 dp

![](/media/content_img/cf979e3.png)

## 背包问题再谈
![](/media/content_img/bag-dp.png)

上一篇：2025年三月算法竞赛选题（一）下一篇：积性函数，莫比乌斯反演（三）

看完文章有啥想法