G8018 [GESP202512 八级] 宝石项链 题解

知识点：双指针、倍增、环形序列。

解题思路

把项链复制一遍，双指针求每个起点包含全部m种颜色的最短段结束位置nxt。对此建立倍增表，枚举切开起点，在总长度n内贪心接尽可能多段。

为什么正确

固定起点时最早结束的合法段给后面保留最多空间，逐段贪心最优；倍增仅加速同一贪心链，枚举起点覆盖环的所有切法。

易错点

下一段起点是当前段右端开区间位置；最多使用一整圈，不能因复制数组把同一宝石用两次。

复杂度

时间O(n log n+m)，空间O(n log n+m)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<int>a(2*n);
    for(int i=0;i<n;i++) {
        cin>>a[i];
        a[i]--;
        a[i+n]=a[i];
    }
    vector<int>ct(m),nxt(2*n+1,2*n+1);
    int kinds=0,r=0;
    for(int l=0;l<2*n;l++) {
        while(r<2*n&&kinds<m) {
            if(ct[a[r]]++==0)kinds++;
            r++;
        }
        if(kinds==m)nxt[l]=r;
        if(--ct[a[l]]==0)kinds--;
    }
    int L=1;
    while((1<<L)<=n)L++;
    vector<vector<int>>jump(L,vector<int>(2*n+2,2*n+1));
    for(int i=0;i<=2*n;i++)jump[0][i]=nxt[i];
    for(int k=1;k<L;k++)for(int i=0;i<=2*n+1;i++)jump[k][i]=jump[k-1][jump[k-1][i]];
    int ans=0;
    for(int i=0;i<n;i++) {
        int x=i,ct=0;
        for(int k=L-1;k>=0;k--)if(jump[k][x]<=i+n) {
            x=jump[k][x];
            ct+=1<<k;
        }
        ans=max(ans,ct);
    }
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用18个自行生成的测试点。