目录
题目概述
原题参考：B. Informatics in MAC
给出一个长度为n的数组，问是否可以将其分为k个（k>1）mex相同的数组，如果可以的话，作出一种划分
思路想法
假设一个数组可以被分为k(k>2)个区间，每个区间的mex相同，那么可以确定的是，该数组中一定不存在mex这个数，假设存在mex，那么mex无论划分到任意区间，那么该区间的mex都不可能是mex；因此，我们可以知道数组中不存在mex元素，因此假如可以将数组划分为k(k>2)个区间，那么也可以将数组划分为2个区间，这两个区间的mex相同，那么只需要对数组分别正向和逆向求一遍mex即可
如何快速的求mex，已知mex是一段区间中未出现的最小正整数，也就是说，可以将该区间分为两部分（以上），也就是说，该区间是不连续的，求解连续性问题，很容易想到并查集，那么对于并查集的初始化就是每个点只能链接自己，当出现某一点时，可以知道，mex不可能是她，也就是说，他和下一位链接起来了，对于每次求当前区间的mex，只需要找到从0开始的最远的区间即可
参考代码
#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define pll pair<long long, long long>
#define pii pair<int, int>
#define vi vector<int>
#define vl vector<long long>
#define ll long long
#define ull unsigned long long
const ll INF = 9187201950435737471;
const int inf = 2139062143;
const ll mod = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1.0);
const int N = 2e5+7;
int n, a[N], mmax = 0;
struct DSU {
int fa[N];
DSU(int n) {for(int i=0; i<=n; i++) fa[i] = i;}
void init(int n) {for(int i=0; i<=n; i++) fa[i] = i;}
int find(int x) {
if(fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
};
void solve() {
int lt[N], rt[N];
cin >> n;
for(int i=1; i<=n; i++) cin >> a[i], mmax = max(mmax, a[i]);
DSU k(mmax+5);
for(int i=1; i<=n; i++) {
k.fa[a[i]] = k.find(a[i]+1);
lt[i] = k.find(0);
}
k.init(mmax+5);
for(int i=n; i; i--) {
k.fa[a[i]] = k.find(a[i]+1);
rt[i] = k.find(0);
}
int ans = -1;
for(int i=1; i<=n-1; i++) {
if(lt[i] == rt[i+1]) {
ans = i;
break;
}
}
cout << (ans == -1 ? -1 : 2) << endl;
if(ans != -1) cout << 1 << " " << ans << endl << ans+1 << " " << n << endl;
}
int main() {
#ifdef xrl
freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout);
#endif
FAST_IO;
int t = 1;
cin >> t;
while(t --) solve();
#ifdef xrl
cout << "Time used = " << (double)(clock() * 1.0 / CLOCKS_PER_SEC) << "s";
#endif
return 0;
}
做题反思
去接静态mex问题，可以使用并查集求解
标签：const,并查,int,区间,MAC,数组,Informatics,mex,define From： https://www.cnblogs.com/notalking569/p/18057363