题解：P9317 [EGOI2022] SubsetMex / 子集 mex

· · 题解

题目传送门

题意太复杂了，看了好久才看懂。

简化题意

给你一个可重复的集合 S，现在你可以对 S 进行两种操作：

  1. 删除 0, 1, \cdots , x - 1，再往 S 中添加 x。
  2. 往 S 中添加一个 0。

现在给出一个数 n，让你求出使得 n \in S 的最小操作次数。

题意分析

因为我们要让 n \in S，所以就至少需要 0, 1, 2, \cdots , n - 1 各一个。

如果达到了需要的个数，就直接跳过。但其中肯定有不够的，有不够的怎么办呢？那就继续进行操作 1。

我们设这个不够的数为 x，其中 x 还差 t 个。那我们还需要 0, 1, \cdots , x - 1 每个数各 t 个。这时候我们就可以拿一个数组来统计每个数所需要的个数。最后，注意从大到小遍历就做完了。

代码

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int N = 55;
ll f[N], ff[N];
int main()
{
    int T; cin >> T;
    while (T--)
    {
        int n; cin >> n;
        ll ans = 1;
        for (int i = 1; i <= n; i++) cin >> f[i], ff[i] = 1; // 初始化 ff 
        for (int i = n; i; i--) // 从大到小遍历
        {
            if (f[i] >= ff[i]) continue; // 如果已经达到了，就跳过 
            for (int j = 1; j < i; j++) ff[j] += ff[i] - f[i];
            ans += ff[i] - f[i];
        } 
        cout << ans << endl;
    }
    return 0;
}