专栏文章

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

lljk8886
P9317题解参与者 3已保存评论 7

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
7 条
当前快照
1 份
快照标识符
@miqz0b2o
此快照首次捕获于
2025/12/04 13:03
3 个月前
此快照最后确认于
2025/12/04 13:03
3 个月前
查看原文
题目传送门
题意太复杂了，看了好久才看懂。

简化题意

给你一个可重复的集合 SS，现在你可以对 SS 进行两种操作：
  1. 删除 0,1,⋯ ,x−10, 1, \cdots , x - 1，再往 SS 中添加 xx。
  2. 往 SS 中添加一个 00。
现在给出一个数 nn，让你求出使得 n∈Sn \in S 的最小操作次数。

题意分析

因为我们要让 n∈Sn \in S，所以就至少需要 0,1,2,⋯ ,n−10, 1, 2, \cdots , n - 1 各一个。
如果达到了需要的个数，就直接跳过。但其中肯定有不够的，有不够的怎么办呢？那就继续进行操作 11。
我们设这个不够的数为 xx，其中 xx 还差 tt 个。那我们还需要 0,1,⋯ ,x−10, 1, \cdots , x - 1 每个数各 tt 个。这时候我们就可以拿一个数组来统计每个数所需要的个数。最后，注意从大到小遍历就做完了。

代码

CPP
#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;
}

评论

共 7 条评论，欢迎与作者交流。

正在加载评论...