   B. 薮猫和最终 MEX 每次测试的时间限制1 秒 每个测试的内存限制256 MB    你得到一个数组 $$$a$$$，由 $$$n\ge 4$$$ 个非负整数组成。 您需要对 $$$a$$$ 执行以下作，直到其长度变为 $$$1$$$： 选择两个索引 $$$l$$$ 和 $$r$$$ （$$$1\le {\color{red}{ l < r }} \le |a|$$$），并将子数组 $$$[a_l，a_{l+1}，\ldots，a_r]$$$ 替换为单个整数 $$$\operatorname{mex}（[a_l，a_{l+1}，\ldots，a_r]）$$$，其中 $$$\operatorname{mex}（b）$$$ 表示 $$$b$$$ 中整数的最小排除 （MEX）$$$^{\text{∗}}$$$ 的整数。换句话说，假设 $$$x=\operatorname{mex}（[a_l，a_{l+1}，\ldots，a_r]）$$$，数组 $$$a$$$ 将变为 $$$[a_1，a_2，\ldots，a_{l-1}，x，a_{r+1}，a_{r+2}，\ldots，a_{|a|}]$$$.请注意，在此作后，$$$a$$$的长度减少了$$$（r-l）$$$。 Serval 希望 $$$a$$$ 中的最后一个元素是 $$$0$$$。帮帮他！ 更正式地说，你必须找到一系列作，这样在按顺序执行这些作后，$$$a$$$ 的长度变为 $$$1$$$，而 $$$a$$$ 中的最后一个元素是 $$$0$$$。 可以证明，在问题的约束下至少存在一个有效的作序列，并且任何一个有效作序列的长度不超过 $$$n$$$。 请注意，您不需要最小化作数。 ∗$The整数集合 $$$b_1、b_2、\ldots b_k$$$ 的最小排除 （MEX） 被定义为最小的非负整数 $$$x$$$ 不出现在集合 $$b$$$ 中。    输入 每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ （$$$1 \le t \le 1000$$）。测试用例的描述如下。 每个测试用例的第一行包含一个整数 $$$n$$$ （$$$4\le n\le 5000$$） — 数组 $$$a$$$ 的长度。 第二行包含 $$$n$$$ 整数 $$$

### 解决方案 要通过 MEX 操作将数组缩减为长度为 1 的情况，可以基于以下逻辑： #### 背景分析 MEX（Minimum EXcluded number）是指给定集合中最小的未出现的非负整数。对于一个数组 `a` 来说，其 MEX 值可以通过遍历该数组并记录已存在的元素来计算得出。 为了使最终数组仅剩下一个元素且值为 0，我们需要逐步减少数组中的元素数量，并确保每次操作后的子数组仍然满足条件。以下是具体方法[^1]： --- #### 实现思路 1. **初始化变量** 定义当前处理的区间 `[l, r]` 和对应的 MEX 值。初始时，整个数组即为待处理区间。 2. **迭代过程** 对于每一步操作： - 计算当前区间的 MEX 值。 - 将此 MEX 值加入到新的数组中作为下一步的操作对象。 - 更新剩余部分继续重复上述步骤直到只剩下一个元素为止。 3. **终止条件** 当前数组长度减至 1 并且唯一剩下的那个数值等于零即可停止循环。 4. **伪代码描述** ```cpp #include <bits/stdc++.h> using namespace std; // Function to compute the MEX of an array segment. int get_mex(vector<int> &arr){ unordered_set<int> s; for(auto num : arr) { if(num >=0 && num < (int)arr.size()) s.insert(num); } int mex = 0; while(s.find(mex)!=s.end()){ mex++; } return mex; } void reduce_to_zero(){ vector<int> current_array; cin >> n; for(int i=0;i<n;i++){ int temp; cin>>temp; current_array.push_back(temp); } while(current_array.size()>1){ // Compute MEX and create new array with it. int mex_val=get_mex(current_array); // Prepare next iteration's input by appending computed MEX value at end. vector<int>next_iteration={mex_val}; // Update 'current_array' as per problem statement rules or logic here... swap(next_iteration,current_array); // Move forward logically based on your algo specifics. } // After loop ends check last element is zero indeed. assert(current_array[0]==0); } ``` --- #### 关键点解析 - 使用哈希集高效查找是否存在某个特定数字以辅助快速定位 MEX 值[^2]。 - 动态调整数据结构大小适应不断变化的需求直至达到目标状态——单一节点且值为零[^3]。 --- ### 相关问题