题解：AT_abc397_c [ABC397C] Variety Split Easy

xyx404 · 2025-03-16 08:31:43 · 题解

题意：

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

思路：

定义数组 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;
}

提交记录。