题解：AT_abc397_c [ABC397C] Variety Split Easy

xyx4042025-03-162025-03-22

引用站外地址，不保证站点的可用性和安全性

洛谷文章链接

xyx404

题意：

将数组分割成两个非空连续子数组，使得两个子数组中不同元素的数量之和最大。

思路：

定义数组 $pre$ ，其中 $pre_i$ 表示前 $i$ 个元素中不同元素的数量。
定义数组 $suf$ ，其中 $suf_i$ 表示从位置 $i$ 到末尾的不同元素数量。

将两个数字预处理完成后，对于所有满足 $1 \le i < n$ 的 $pre_i+suf_{i+1}$ 中取最大值就是答案。

代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define itn int
#define ull unsigned long long
const int N=3e5+5;
int n,a[N],pre[N],suf[N];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	unordered_set<int>spre;
	pre[0]=0;
	for(int i=1;i<=n;i++){
		spre.insert(a[i]);
		pre[i]=spre.size();
	}
	unordered_set<int>ssuf;
	suf[n+1]=0;
	for(int i=n;i>=1;i--){
		ssuf.insert(a[i]);
		suf[i]=ssuf.size();
	}
	int maxx=0;
	for(int i=1;i<n;i++){
		maxx=max(maxx,pre[i]+suf[i+1]);
	}
	cout<<maxx;
	
	return 0;
}