寒假训练第3周（牛客冬训营）

whatdo / 2024-02-06 / 原文

F-Tokitsukaze and Eliminate (hard)_2024牛客寒假算法基础集训营2 (nowcoder.com)

脑袋堵住了，红温没有写出来，后面想到思路直接给否定了，可惜

题解：需要你找最右边第一个，直接先统计一下有多少个颜色的宝石，然后从左往右依次放入set到相应的颜色数就加答案，然后如果这种颜色宝石没有了就需要把一开始统计数减一下即可，后面继续放到set就好了

#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
//#define double long double
#define int long long
//#define endl '\n'
using namespace std;
const int N=1e6+10,M=1e1;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int mod=998244353;
typedef pair<int,int> PII;

int a[N];
set<int> b;
map<int,int> mp;
void solve()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        mp[a[i]]++;
    }
    int l=mp.size();
    int ans=0;
    int c=0;
    for(int i=n;i>=1;i--)
    {
        b.insert(a[i]);
        mp[a[i]]--;
        if(mp[a[i]]==0) c++;
        if(b.size()==l)
        {
            ans++;
            l-=c;
            c=0;
            b.clear();
        }
    }
    cout<<ans<<endl;
    mp.clear();
}
signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}