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

[[ slider_text ]]

[[ item.c ]]

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

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

树状数组 gcd 狄利克雷后缀

## 牛客训练营
### 智乃的逆序数
**[K.智乃的逆序数](https://ac.nowcoder.com/acm/contest/95335/K)**
**问题描述**
定义一个序列是紧密的，当且仅当从小到大排序之后，相邻数字的差值是 1，定义两个序列不相交
当且仅当两个序列没有相同元素，现在考虑逆序对下标$$(i, j), i < j, a_i > a_j$$
定义子序列是从原序列中删除任意个元素得到（即可以不连续）

给定$$n$$个互不相交的紧密序列，构造一个长度为$$n$$个序列长度之和的新序列
要求新序列只能由这$$n$$个紧密序列中出现的数构成，并且每个数都会被用到，且只能用一次
同时另外要求这个新序列包含这$$n$$个紧密序列作为子序列，并且逆序对恰好为$$k$$

简单点说，就是$$n$$个序列放一起排序，如果原来是同个序列的，相对顺序要保证，否则没有限制
输出方案，无解输出`-1`

**算法分析**
![](/media/content_img/nowcoder3-k1.png)
![](/media/content_img/nowcoder3-k2.png)

## Codeforces Round 973
### E
**[E. Prefix GCD](https://codeforces.com/contest/2013/problem/E)**
**问题描述**
给你一个序列$$a$$，最小化
```math
gcd(a_1) + gcd(a_1, a_2) + \cdots + gcd(a_1, a_2, \cdots, a_n)
```

**算法分析**
![](/media/content_img/cf973-e1.png)
![](/media/content_img/cf973-e2.png)
![](/media/content_img/cf973-e3.png)
![](/media/content_img/cf973-e4.png)

### E 狄利克雷后缀求解
> 这个问题还可以用狄利克雷后缀来求解

```math
\text{从大到小 for } y \\ 
g(y) = g(y) - g(y \text{ 的倍数})
```
![](/media/content_img/dirichlet-suf01.png)
![](/media/content_img/dirichlet-suf02.png)

#### 算法实现
> 狄利克雷后缀的核心是 g 函数

```bash
void solve(int cas) {
    int n;
    cin >> n;
    vector<int> a(n+1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];
    int G = a[1];
    for (int i = 2; i <= n; i++) G = std::gcd(G, a[i]);
    for (int i = 1; i <= n; i++) a[i] /= G;

int M = *max_element(a.begin()+1, a.end());
    vector<int> exist(M+5, 0);
    for (int i = 1; i <= n; i++) exist[a[i]] += 1;

vector<vector<int> > fac(M+5);
    vector<int> cnt(M+5, 0);
    for (int y = 1; y <= M; y++) {
        for (int x = y; x <= M; x += y) {
            fac[x].emplace_back(y);
            if (exist[x]) cnt[y] += 1;
        }
    }

vector<i64> dp(M+5, inf<i64>), last(M+5, inf<i64>);
    vector<i64> g(M+5, 0);

const int LOG = 20;
    i64 ans = inf<i64>;

for (int x = 1; x <= M; x++) if (exist[x]) dp[x] = x;
    chmin(ans, dp[1] + 1LL * (n - 1));

for (int i = 2; i <= min(LOG, n); i += 1) {
        last = dp, dp.assign(M+5, inf<i64>);

for (int x = 1; x <= M; x++) {
            if (last[x] >= inf<i64>) continue;

for (auto y : fac[x]) g[y] = cnt[y];

for (int k = fac[x].size()-1; k >= 0; k--) {
                auto y = fac[x][k];

if (g[y] > 0) {
                    chmin(dp[y], last[x] + y);
                }

for (auto d : fac[y]) {
                    if (d == y) continue;
                    g[d] -= g[y];
                }
            }
        }

i64 res = dp[1] + (1LL * n - i);
        chmin(ans, res);
    }

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

## Codeforces Round 997 (Div. 2)
**[D. Unique Median](https://codeforces.com/contest/2056/problem/D)**
长度为$$m$$的序列$$b$$被认为是好的，当且仅当，排序之后，有
```math
\displaystyle
b(\lfloor \dfrac{m+1}{2} \rfloor) = b(\lceil \dfrac{m+1}{2} \rceil)
```
如果$$m$$是奇数，那么`b`总是好的
现在给你一个长度为`n`的数组`a`，计算它的子数组中，好数组的数量，子数组必须**连续**

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

> 计数是难点

![](/media/content_img/cf997d3.png)
![](/media/content_img/cf997d4.png)

```bash
void solve(int cas) {
    int n;
    cin >> n;
    vector<int> a(n+1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];

auto calc = [&](int x) -> i64 {
        i64 res = 0;
        vector<int> sl(n+1, 0), sr(n+1, 0);
        for (int i = 1; i <= n; i++) sl[i] = sl[i-1] + (a[i] >= x ? 1 : -1);
        for (int i = 1; i <= n; i++) sr[i] = sr[i-1] + (a[i] <= x ? 1 : -1);

vector<int> perm(n+1, 0);
        iota(perm.begin(), perm.end(), 0);
        sort(perm.begin(), perm.end(), [&](int i, int j) {
            if (sl[i] != sl[j]) return sl[i] < sl[j];
            return sr[i] > sr[j];
        });

Fenwick<i64> tr(2 * n + 5);
        const int base = n + 1;

for (auto i : perm) {
            auto now = sr[i];

res += tr.sum(base + now - 1);
            tr.add(base + now, 1);
        }

return res;
    };
    i64 ans = 0;
    for (int x = 1; x <= 10; x++) ans += calc(x);

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

## 牛客周赛84
### G 小红的陡峭值
**[G 小红的陡峭值](https://ac.nowcoder.com/acm/contest/103152/G)**
给定一个数组，定义陡峭值是$$\sum |a\_i - a\_{i-1}|$$，现在打乱数组，求陡峭值的期望

**算法分析**
根据期望的线性性质
```math
\displaystyle
E = \sum_i E( |a_i - a_{i-1}| ) = \binom{n-2+1}{1} \cdot E(|a_i - a_j|)
```
实际上，对于特定的两个元素$$a_i, a_j$$相邻，都会产生$$E(|a_i - a_j|)$$的代价
将这两个元素**打包**，剩下$$n-2$$个元素，有$$n-1$$个空位可以插入
所以对于特定的相邻元素$$|a_i - a_j|$$，它被加了$$n-1$$次

这样，上述式子就可以写成
```math
\displaystyle
E = \binom{n-1}{1} \cdot E(\sum\text{所有可能的，特定的} a_i, a_j, |a_i - a_j|的值) \\
=(n-1) \cdot \dfrac{2}{n(n-1)} \cdot (\text{所有可能的 } a_i, a_j， |a_i - a_j| \text{的求和})
```
这就很好计算了，前缀和就可以解决

换一个角度来理解，如果从整体来看，那么求期望，分母一定是$$\dfrac{1}{n!}$$
那么分子呢？分子我们要考虑所有可能出现的$$|a_i - a_j|$$，它们的求和
```math
\displaystyle
\sum_{i, j, a_j \leqslant a_i} |a_i - a_j| \cdot (\text{它被加了多少次})  \\ =
\sum_{i, j, a_j \leqslant a_i} 2 \cdot (a_i - a_j) \cdot (a_i, a_j \text{ 相邻的方案数}) \\ =
\sum_{i, j, a_j \leqslant a_i} 2 \cdot (a_i - a_j) \cdot (n-2)!\binom{n-1}{1}
```
最后一项解释为，剩下$$(n-2)$$个数的全排列，然后$$(a_i - a_j)$$相邻插空

## Codeforces Round 1005 (Div. 2)
### E
**[E. Mycraft Sand Sort](https://codeforces.com/contest/2064/problem/E)**
**问题描述**
给你一个排列$$p$$，还有一个长度为$$n$$的序列`c`，要求从上到下
第$$i$$行，放置颜色是$$c_i$$的方块，放$$p_i$$个
按重力操作，能落下的就落下

现在问，有多少种不同的$$(p, c)$$，按重力落下后，能产生相同的方块布局？
注意，布局以初始状态为准，也就是说，初始时候的`(p, c)`，是一定要考虑的

**算法分析**
**性质1**
不难发现，不管怎么变，第一列是填满的，也就是说，第一列是确定的
那么对于$$(p, c), (p', c')$$，一定有$$c = c'$$，才能使得最终形状相同
进一步地，实际上就要考虑，对初始的$$p$$，做哪些变换，才能使得$$p^{\prime} = p$$
**初步结论是**，对于$$c_i = c_j$$，那么$$(i, j)$$才有可能发生交换，否则一定不会交换

**性质2**
对于$$p_i = p_j$$，要满足什么样的额外条件，二者才可以交换？
手动模拟后发现，对于$$c_l = c_r = A$$，$$l, r$$两行可不可以交换呢？
不难发现，只有满足$$\forall j \in [l, r]$$并且$$c_j \neq A$$，**对于所有这样的**$$j$$，满足$$p_j \leqslant \min(p_l, p_r)$$
此时$$l, r$$两行可以交换

**性质3**
![](/media/content_img/cf1005e1.png)
![](/media/content_img/cf1005e2.png)
![](/media/content_img/cf1005e3.png)
![](/media/content_img/cf1005e4.png)

**性质4 线段树二分**
好像不可以做，因为`k`两端的`len`，并不单调

### 算法实现
```bash
void solve(int cas) {
    int n;
    cin >> n;
    vector<int> a(n+1, 0), c(n+1, 0);

for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> c[i];

vector<vector<int> > pos(n+1);
    for (int i = 1; i <= n; i++) pos[c[i]].emplace_back(i);
    auto ord = pos;

segtree<int, op> tr(a, n);

DSU<int> dsu(n+5);
    for (auto &vec : pos) {
        if (vec.size() == 0) continue;
        for (int i = 0; i < vec.size(); i++) {
            auto p = vec[i];
            dsu.mn[p] = dsu.mx[p] = i;
        }
    }

for (auto &vec : ord) {
        sort(vec.begin(), vec.end(), [&](int x, int y) {
            return a[x] < a[y];
        });
    }

mint ans = 1;
    auto calc = [&](int c) -> void {
        for (auto p : pos[c]) tr.change(1, 1, n, p, 0);

for (auto p : ord[c]) {
            int k = lower_bound(pos[c].begin(), pos[c].end(), p) - pos[c].begin();
            auto len = a[p];

// [0, k-1], [k+1, pos[c].size)
            for (int j = k-1; j >= 0; j--) {
                auto maxv = tr.query(1, 1, n, pos[c][j], p);
                if (maxv >= len) break;

dsu.merge(p, pos[c][j]);
                j = dsu.mn[dsu.find(p)];
            }

for (int j = k+1; j < pos[c].size(); j++) {
                auto maxv = tr.query(1, 1, n, p, pos[c][j]);
                if (maxv >= len) break;

dsu.merge(p, pos[c][j]);
                j = dsu.mx[dsu.find(p)];
            }

auto rt = dsu.find(p);
            auto sz = dsu.size(rt), del = dsu.used[rt];

ans *= mint(sz - del);
            dsu.used[rt] += 1;
        }

for (auto p : pos[c]) tr.change(1, 1, n, p, a[p]);
    };

for (int c = 1; c <= n; c++) {
        if (pos[c].size() == 0) continue;
        calc(c);
    }

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

上一篇：Catalan 数下一篇：2025年四月算法竞赛选题（一）

看完文章有啥想法