【MEX】CF1629 C

た入场券 2024-03-17 19:35 142阅读 0赞

[Problem - C - Codeforces][]

题意：

![3b96010d5d4e4308a6e03f37a292c9af.png][]

![c730263310574e67b7d915b008db4a40.png][]

![e54ece15cb5f42eabe5d0ca23e367657.png][]

思路：

模拟样例

![5195b1f0f70a425691be9f1bd998a408.jpeg][]

可以发现做法是对该数列进行分段，当当前mex在后缀没有出现过时，形成一个区间\[l,r\]

然后有两个问题：

1.mex怎么去维护

2.怎么看mex在后缀有没有出现过

对于第一个，直接用set维护集合中出现过的数是哪几个

idx为区间mex

第二个问题只需要用桶记录一下即可

Code：

#include <bits/stdc++.h>
     
    #define int long long
     
    using namespace std;
     
    const int mxn=1e6+10;
    const int mxv=1e6+10;
    const int mxe=1e6+10;
    const int mod=1e9+7;
    const int Inf=0x3f3f3f3f;
    
    int N;
    int a[mxn],vis[mxn];
    
    void solve(){
    	cin>>N;
    	for(int i=1;i<=N;i++) vis[i]=0;
    	for(int i=1;i<=N;i++) cin>>a[i];
    	for(int i=1;i<=N;i++) vis[a[i]]++;
    	int idx=0;
    	set<int> S;
    	//维护集合中出现过的数
    	vector<int> ans;
    	for(int i=1;i<=N;i++){
    		S.insert(a[i]);
    		while(S.count(idx)) idx++;
    		vis[a[i]]--;
    		if(!vis[idx]){
    			ans.push_back(idx);
    			idx=0;
    			S.clear();
    		}
    	}
    	cout<<ans.size()<<'\n';
    	for(int i=0;i<ans.size();i++) cout<<ans[i]<<" \n"[i==ans.size()-1];
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

[Problem - C - Codeforces]: https://codeforces.com/contest/1629/problem/C
[3b96010d5d4e4308a6e03f37a292c9af.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/97cc1787699f4f188e56b69852b3ad5c.png
[c730263310574e67b7d915b008db4a40.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/75c521734c134613b3f23a0a3a8ff476.png
[e54ece15cb5f42eabe5d0ca23e367657.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/c02dd1926c1541b0b8b493fe1a3d0a42.png
[5195b1f0f70a425691be9f1bd998a408.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/9e8feea4ab484bd8a17b2253964f0601.png