当前位置：首页 > news >正文

[10月考试] F

news 2025/7/28 6:57:27

[10月考试] F

题目描述

给定长度为 $n$ 的序列 $a_n$ ，保证 $a_i$ 为非负整数。

$m$ 次询问，每次给定区间 $l, r$ ，求出 $al,al+1,…,ara_l,a_{l+1},\ldots,a_r$ 的 $m e x$ 。

对于一个序列，定义其 $m e x$ 为不在序列中出现的最小非负整数。

例如序列 $1, 2, 5, 7$ 的 $m e x$ 为 $0$ ，序列 $3, 0, 1, 2, 5$ 的 $m e x$ 为 $4$ 。

对于所有数据， $n,m≤1000n,m\leq 1000$ ， $1≤l≤r≤n1\leq l\leq r\leq n$ ， $0≤ai≤10000\leq a_i\leq 1000$ 。

输入格式

输入共 $m + 2$ 行。

第 $1$ 行输入 $2$ 个正整数 $n, m$ 。

第 $2$ 行输入 $n$ 个非负整数 $a1,a2,…,ana_1,a_2,\ldots,a_n$ 。

接下来 $m$ 行，每行输入 $2$ 个正整数 $l, r$ 代表一次询问。

输出格式

输出共 $m$ 行，每行输出 $1$ 个非负整数，代表一次询问的答案。

样例 #1

样例输入 #1

样例输出 #1

5
1
0

提示

对于 $30%30\%$ 的数据， $n,m≤5n,m\leq 5$ 。

对于 $60%60\%$ 的数据， $n,m≤100n,m\leq 100$ ， $ai≤5a_i\leq 5$ 。

对于所有数据， $n,m≤1000n,m\leq 1000$ ， $1≤l≤r≤n1\leq l\leq r\leq n$ ， $0≤ai≤10000\leq a_i\leq 1000$ 。

题目解析

这道题要求我们对给定序列区间 [l, r] 求其 mex（即不在该区间内的最小非负整数）。mex 是序列中不包含的最小整数。例如，给定一个序列 1, 2, 3, 4，其 mex 为 0，因为 0 是最小的且不在这个序列中。

解题思路

暴力解法：
- 对每一个查询区间 [l, r]，我们可以直接扫描区间 [l, r]，找到其中所有的数，记录这些数。
- 然后从 0 开始，找到最小的一个没有出现在区间内的数，返回这个数作为 mex。
由于题目中的 n 和 m 最大为 1000，所以暴力方法的时间复杂度是 O(n * m)，每次查询的时间复杂度是 O(n)。最坏情况下，总时间复杂度为 O(n * m)，在最坏情况下（n = 1000, m = 1000）是可以接受的。

具体实现

读取输入数据。
处理每个查询，对于每个查询区间 [l, r]，我们：
- 利用一个数组 count 来记录区间中各个数值的出现情况。
- 找到最小的非负整数 mex，它不在区间内出现。

#include
#include
#include
using namespace std;

int main() {
int n, m;
cin >> n >> m;

vector<int> a(n);
for (int i = 0; i < n; i++) {cin >> a[i];
}// 处理每次查询
for (int i = 0; i < m; i++) {int l, r;cin >> l >> r;l--; r--;  // 转换为0-index// 用一个set来记录区间内的所有数set<int> nums_in_range;for (int j = l; j <= r; j++) {nums_in_range.insert(a[j]);}// 找到mexint mex = 0;while (nums_in_range.count(mex)) {mex++;}cout << mex << endl;
}return 0;
}

代码解析

输入处理：
- 首先读取 n 和 m。
- 然后读取长度为 n 的序列 a。
查询处理：
- 对于每个查询区间 [l, r]，我们通过 set<int> nums_in_range 来记录该区间中所有不同的元素。
- 通过遍历区间 [l, r]，将区间中的所有数插入到 nums_in_range 中（set 会自动去重）。
计算 mex：
- 从 0 开始查找最小的没有出现的数，即 mex。我们使用 count 方法来检查 mex 是否出现在 set 中，直到找到一个不在其中的 mex。
输出结果：
- 对于每次查询，输出对应的 mex 值。

时间复杂度

对于每个查询，扫描区间的时间复杂度是 O(r - l + 1)，而构建 set 的时间复杂度是 O(r - l + 1)。
查找 mex 的时间复杂度是 O(mex)，但是 mex 最大也不会超过区间中最大数值 + 1，所以它的时间复杂度是 O(n)（理论上最多为 n）。
因此，每个查询的时间复杂度为 O(n)，总时间复杂度为 O(n * m)，这是可以接受的。

简单算法思路

遍历查询区间：对于每一个查询，我们需要遍历区间 [l, r]，将该区间内的所有数保存到一个集合中。
计算 mex：mex 是从 0 开始，找到最小的一个不在集合中的数。

优化：直接使用一个数组来记录该区间内数字的出现情况，而不使用 `set`。

#include
#include
using namespace std;

int main() {
int n, m;
cin >> n >> m;

vector<int> a(n);
for (int i = 0; i < n; i++) {cin >> a[i];
}// 处理每次查询
for (int i = 0; i < m; i++) {int l, r;cin >> l >> r;l--; r--;  // 转换为0-index// 用一个数组记录区间内的数是否出现过bool appeared[1001] = {false};// 标记区间内的数for (int j = l; j <= r; j++) {appeared[a[j]] = true;}// 找到最小的没出现的数即为mexint mex = 0;while (appeared[mex]) {mex++;}cout << mex << endl;
}return 0;
}

代码解析

输入处理：
- 首先读取 n 和 m。
- 然后读取长度为 n 的序列 a。
查询处理：
- 对于每个查询区间 [l, r]，我们创建一个布尔数组 appeared，该数组用于标记区间内出现的数字。数组大小为 1001，涵盖了所有可能出现的数字（0 到 1000）。
计算 mex：
- 对于每个区间 [l, r]，我们将区间内的每个数对应的 appeared 数组位置标记为 true。
- 然后从 0 开始，查找最小的没有被标记为 true 的数字，那个数字就是 mex。
输出结果：
- 对于每次查询，输出对应的 mex 值。