题解：P14924 [GESP202512 八级] 宝石项链

huangzixi071018 · 2026-01-03 21:19:33 · 题解

题目大意：

一个环形项链，将其划分成尽量多的段，使得每一段中包含了所有种类的宝石，求最多的段数。

思路：

这是一道很经典的题目。我们可以破环成链再使用倍增来解决。首先我们可以贪心的知道每段区间的长度越大越不优，所以用双指针处理出以每一个 i 作为左端点的最短包含所有种类宝石的区间。接着使用倍增预处理出以 i 为左端点的区间跳 2 的 j 次方步所跳到的位置。最后对于每一个左端点 i 去枚举他所能跳的步数，使得跳过的区间长度不超过 n。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int a[N],f[N][25],lo[N],c[N];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        a[n+i]=a[i];
    }
    int s=0;
    for(int i=1,j=1;i<=2*n;i++){
        while(j<=2*n&&s<m){
            c[a[j]]++;
            if(c[a[j]]==1){
                s++;
            }
            j++;
        }
        if(s==m){
            f[i][0]=j;
        }
        c[a[i]]--;
        if(c[a[i]]==0){
            s--;
        }
    }
    for(int j=1;j<=20;j++){
        for(int i=1;i<=n;i++){
            f[i][j]=f[f[i][j-1]][j-1];
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        int up=n+i,res=0,x=i;
        for(int j=20;j>=0;j--){
            if(f[x][j]<=up&&f[x][j]){
                res+=(1<<j);
                x=f[x][j];
            }
        }
        ans=max(ans,res);
    }
    cout<<ans<<"\n";
    return 0;
}