CF2117C 酷分割

Andy1101 · 2025-06-19 20:15:11 · 题解

题目传送门

思路

从题目中不难看出，b_j 需要包含 b_1 \sim b_{j-1} 所出现过的所有数。我们可以建两个 set，一个记录一个段的数 s，另外一个记录之前的所有数 sall，当两个 set 的长度一样说明成功找到了一个段，那么此时数量 +1，并且清空 s。

最后还要再特判一下，当数量为 0 时，说明无法分割，只有一大段（即原数组），此时答案为 1。

AC Code：

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N]; 
void solve()
{
    set<int> s,sall;
    int n;
    cin >>n;
    int cnt=0;
    for(int i=1;i<=n;i++) cin >>a[i];
    for(int i=1;i<=n;i++)
    {
        s.insert(a[i]);
        sall.insert(a[i]);
        if(s.size()==sall.size())
        {
            cnt++;
            s.clear();
        }
    }
    if(!cnt) cout <<cnt<<'\n';
    else cout <<cnt<<'\n';
}
int main()
{
    int t;
    cin >>t;
    while(t--)
    {
        solve();
    }
    return 0;
}