五月算法竞赛选题（一）

[[ slider_text ]]

[[ item.c ]]

五月算法竞赛选题（一）

发布时间 2025-06-10 作者：zhangminchen 来源：算法小站

构造

## Rayan Programming Contest 2024
### E
**[E. Permutations Harmony](https://codeforces.com/contest/2034/problem/E)**
**问题描述**
定义 k-排列集合是$$k$$个排列$$p_1, p_2, \cdots, p_k$$，其中每个排列都是长度为$$n$$的，还必须满足
排列两两不同，并且对于$$1 \leqslant i, j \leqslant n$$
```math
p_1(i) + p_2(i) + \cdots + p_k(i) = p_1(j) + p_2(j) + \cdots + p_k(j)
```
现在给你$$n, k$$，要求输出一个 k-排列集合，不存在输出 NO

**算法分析**

> 想法一，从环的角度来想，发现不好保证**不重复**

![](/media/content_img/rayan01.png)
![](/media/content_img/rayan02.png)

> 想法二，暴力枚举，每次考虑暴力地让他们的和相等，并用哈希去重

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

### 算法实现
```bash
void solve(int cas) {
    int n, K;
    cin >> n >> K;

if (K == 1 && n != 1) {
        cout << "NO\n";
        return;
    }

set<vector<int> > st;

vector<int> p(n+1, 0);
    iota(p.begin(), p.end(), 0);

auto calc = [&]() -> void {
        do {
            vector<int> with(n+1, 0);
            for (int i = 1; i <= n; i++) with[i] = n + 1 - p[i];

if (st.contains(p) || st.contains(with)) continue;

st.insert(p), st.insert(with);

if (st.size() >= K) break;
        } while (next_permutation(p.begin() + 1, p.end()));
    };

if (K % 2 == 0) {
        calc();

if (st.size() < K) {
            cout << "NO\n";
            return;
        }

cout << "YES\n";
        for (auto vec : st) {
            for (int i = 1; i < vec.size(); i++) cout << vec[i] << " ";
            cout << "\n";
        }

return;
    }

if (n % 2 == 0) {
        cout << "NO\n";
        return;
    }

auto prework = [&]() -> void {
        auto m = n / 2;
        auto S = 3 * m + 3;

vector<int> p1(n+1, 0), p2(n+1, 0), p3(n+1, 0);

for (int i = 1; i <= n; i++) p1[i] = i;
        for (int i = 1; i <= n; i++) p2[i] = (i - 1 + m) % n + 1;
        for (int i = 1; i <= n; i++) p3[i] = S - p1[i] - p2[i];

st.insert(p1);
        st.insert(p2);
        st.insert(p3);
    };

prework();
    if (st.size() < K) {
        calc();
    }

if (st.size() < K) {
        cout << "NO\n";
        return;
    }
    cout << "YES\n";

for (auto vec : st) {
        for (int i = 1; i < vec.size(); i++) cout << vec[i] << " ";
        cout << "\n";
    }
}
```

## Hello 2024
### C
**[C. Grouping Increases](https://codeforces.com/contest/1919/problem/C)**
**问题描述**
要求把序列$$a$$划分成$$s$$集和$$t$$集，定义代价$$p(b)$$，表示序列$$b$$中，满足$$i \in [1, m-1], b(i) < b(i+1)$$的不同的$$i$$的个数
现在要求你**最小化**$$p(s) + p(t)$$
注意，$$s$$集和$$t$$集都可以是空的

**算法分析**

> 方法一，贪心

这种贪心算法类似**杨表**，一开始`S, T`集合中分别放入$$+\infty$$，然后尝试贪心构造
考虑** S, T 分别以什么数结尾**？尽量贪心地让`S, T`尽可能单调递减

假设放入`x`，如果$$S, T$$的末尾元素都$$< x$$，那么不论如何都会产生代价，我们要让**暴露出来的**那个末尾元素，
尽可能大，这样才更有机会构造出**单调递减的序列**
所以我们选择较小的那个末尾插入

否则，如果`x`只能单调递减插入一个集合的末尾，就贪心地插入
如果两个都可以成功插入呢？$$back \geqslant x$$，那么插哪个都会使得暴露出来的减小
那么我们也是选择较小的那个插入，保留较大的末尾

> 方法二，线段树优化 dp

不难发现，设计$$dp$$方程的时候，考虑`S 集和 T 集`分别以哪些数结尾？
以$$i$$作为`dp`的阶段，假设我们考虑放完$$a_i$$，那么可能的情况是什么呢？
可能是$$a[j\cdots i]$$，往前连续的一段都在一个集合中，然后另一个集合末尾以$$y$$结尾

将这样的状态定义为$$dp(i, y)$$，考虑如何转移

转移时候，打表上一个阶段**可能出现的所有的结尾的值**$$y \in [1, n]$$
初始阶段呢？所有数都不存在，所以**所有的**$$y \in [1, n]$$都不需要代价，代价就是`0`

转移分两种，第一种就是$$a\_{i}$$接在$$a\_{i-1}$$后面
那么`for all y in [1, n]`，$$dp(i, y) \leftarrow dp(i-1, y) + [a\_{i-1} < a\_{i}]$$

第二种呢，$$a\_{i}$$接在$$y$$后面
对于所有$$y \in [1, a\_{i}-1]$$的状态，有$$dp(i, a\_{i-1}) \leftarrow dp(i-1, y) + 1$$
对于$$y \in [a\_{i}, n]$$呢，有$$dp(i, a\_{i-1}) \leftarrow dp(i-1, y) + 1$$

更新到$$n$$的时候，把所有$$y \in [1, n]$$状态取一个最小值即可

这可以用线段树优化
第一，$$dp(i, a\_{i-1})$$的更新可能涉及单点修改，我们要知道所有可能的$$y$$，最小的`dp`值
```bash
dpv1 = {[1...a[i] - 1] 的区间 min} + 1
dpv2 = {[a(i)...n] 的区间 min}

那么 dp(i, a[i-1]) 的新的 dp 值有可能是 ndp = min(dpv1, dpv2)
```

第二，如果$$a\_{i-1} \geqslant a\_{i}$$，对于所有的$$y$$，$$dp$$状态都是从$$i-1$$继承过来，不要修改
否则如果$$a\_{i-1} < a\_{i}$$，存在转移，对所有$$y \in [1\cdots n]$$，$$dp\_{i}(y) = dp\_{i-1}(y) + 1$$
```bash
如果 a[i-1] < a[i]:
	执行[1....n] 区间加 1，区间修改
```
那么这个时候$$dp\_{i}(a\_{i-1})$$的值也会被修改了，和之前的`ndp`取一个最小值即可
这是一个单点修改

```bash
lazy_segtree<i64, op, i64, mapping, comp, id> tr(vector<i64> (n+1, 0), n);
tr.change(1, 1, n, a[1], 0);

for (int i = 2; i <= n; i++) {
	auto x = a[i];
	i64 dpv1 = (1 <= x - 1) ? tr.query(1, 1, n, 1, x-1) + 1 : inf<int>;
	i64 dpv2 = tr.query(1, 1, n, x, n);

i64 ndp = min(dpv1, dpv2);

if (a[i-1] < a[i]) tr.modify(1, 1, n, 1, n, 1);
	tr.change(1, 1, n, a[i-1], ndp);
}

auto ans = tr.query(1, 1, n, 1, n);
```

## Codeforces Round 919
### C
**[C. Partitioning the Array](https://codeforces.com/contest/1920/problem/C)**
给定一个长度是`n`的序列，对于$$k \mid n$$，Allen 做了下面的事情
他把序列划分成不相交的$$k$$个子序列
```math
[a_1, a_2, \cdots, a_k], [a_{k+1}, a_{k+2}, \cdots, a_{2k}], \cdots,  [a_{n-k+1}, a_{n-k+2}, \cdots, a_n]
```
注意，必须有序
此外，Allen 获得一分，当且仅当存在$$m \geqslant 2$$，使得把上面数组中的数$$x \to x \bmod m$$
所有子数组都一样，问他能够获得的最大分数，（就是问有几个不同的$$m$$）

**算法分析**

> 同余，即$$x \equiv y (\bmod m)$$，要想到$$m \mid (x-y)$$
进一步地，多个数，考虑 gcd

```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 check = [&](int k) -> bool {
        vector<int> G;
        vector<vector<int> > mat;

for (int i = 1; i <= k; i += 1) {
            vector<int> col;
            for (int j = i; j <= n - k + i; j += k) {
                col.push_back(a[j]);      
            }
            //debug(col);
            mat.push_back(col);
        }

for (auto col : mat) {
            auto g = 0;
            for (int i = 1; i < col.size(); i++) g = std::gcd(g, abs(col[i] - col[i-1]));
            
            if (g == 1) return false;
            G.push_back(g);
        }

auto g = 0;
        for (auto x : G) g = std::gcd(g, x);

return g != 1;
    };

vector<vector<int> > fac(n+5);
    for (int x = 1; x <= n; x++) {
        for (int y = x; y <= n; y += x) {
            fac[y].push_back(x);
        }
    }

int ans = 0;
    vector<int> vis(n+5, 0);
    for (auto k : fac[n]) {
        if (k == n) {
            ans += 1;
            continue;
        }
        if (check(k)) ans += 1;
    }

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

## Codeforces Round 921
### C
**[C. Did We Get Everything Covered?](https://codeforces.com/contest/1925/problem/C)**
**问题描述**
给定字符串`s`，两个数$$n, k$$，考虑所有长度为$$n$$的串，这些串都必须用小写字母表的前$$k$$个数构成
问这些能构成的串，是不是都构成$$s$$的子串？（子串不要求连续）
比如`n = 2, k = 2`，那么用`{a, b}`构成的串的集合是`{aa, ab, ba, bb}`
但是如果`s = abb`，注意到`aa`并不是`s`的子串，那么答案是`NO`，你只需要输出任意一个，
长度为$$n$$的串，并且这样的串仅由前`k`个小写字母组成，并且串不是`s`的子串

### 算法实现
这题自己想出来了，用 dp 来做
```bash
void solve(int cas) {
    int n, K, m;
    cin >> n >> K >> m;

string str;
    cin >> str;
    str = " " + str;

if (n > m) {
        cout << "NO\n";
        auto res = string(n, 'a');
        cout << res << "\n";
        return;
    }

map<char, int> cnt;
    for (int i = 1; i <= m; i++) cnt[str[i]] += 1;

bool bad = false;
    char badch;
    for (int k = 1; k <= K; k++) {
        char ch = 'a' - 1 + k;
        if (n > cnt[ch]) {
            bad = true, badch = ch;
            break;
        }
    }

if (bad) {
        cout << "NO\n";
        cout << string(n, badch) << "\n";
        return;
    }

map<char, vector<int> > pos;
    for (int i = 1; i <= m; i++) pos[str[i]].emplace_back(i);

// debug(pos);

vector dp(n+5, vector<int>(26+5, 0));

for (int i = 1; i <= K; i++) {
        char ch = 'a' - 1 + i;
        
        if (!pos.contains(ch)) continue;

auto p = *pos[ch].begin();
        dp[1][ch-'a'+1] = p;
    }
    debug(dp[1]);

using pii = pair<int, int>;
    pii broken = {-1, -1};

vector<int> pre(n+5, 0);

auto check = [&]() -> bool {
        for (int i = 2; i <= n; i++) {
            int last = 0;
            for (int k = 1; k <= K; k++) chmax(last, dp[i-1][k]);

if (cas == 3) debug(last);

for (int x = 1; x <= K; x++) {
                char ch = 'a' - 1 + x;
                // debug(pos[ch]);
                // debug(last);
                auto it = upper_bound(pos[ch].begin(), pos[ch].end(), last);

if (it == pos[ch].end()) {
                    broken = pii{i, x}, pre[i] = last;
                    return false;
                }

// auto p = it - pos[ch].begin();
                // debug(p);
                dp[i][x] = *it, pre[i] = last;
            }
        }
        return true;
    };

bool ok = check();

if (ok) {
        cout << "YES\n";
        return;
    }

string head;
    auto [i, x] = broken;

for (int j = i; j >= 2; j--) {
        auto p = pre[j];
        char ch = str[p];

head += string(1, ch);
    }

reverse(head.begin(), head.end());

head += string(n-i+1, 'a'+x-1);

cout << "NO\n";
    cout << head << "\n";
}
```

上一篇：六月算法竞赛选题——概率与期望（一）已经是最后一篇啦

看完文章有啥想法