题解：P13504 [OOI 2024] More Gifts

· · 题解

OOI 超级无敌强强题。

不难发现，如果初始序列中的元素种类本身就只有 x\le t 种，那么答案就是 1。

如果原序列中有大于 t 中元素，显然一个人能拿走的长度一定小于 n。

我们可以把两个序列 a 拼接起来，就可以计算一个人从某一种元素出发最多能拿多少长度。

注意到 a_i \in [1,10^9]，值域很大，而本题中我们只需要关心元素之间是否相等，所以先将 a_i 离散化一下。

我们考虑维护 jump_i 表示从第 i 个元素开始一个人最多能拿多少个礼物。

这个东西可以用滑动窗口维护。

计算出 jump_i 后就可以模拟我们可爱的小学奥数《周期问题》 的解题过程计算答案，详细过程见代码。

进入循环节前最多走 n 步，走出循环节之后也最多走 n 步，因此这部分的时间复杂度是 O(N) 的。

整个算法的瓶颈在于离散化，总体时间复杂度 O(N\log N)，常数有点大但是通过 n\le 3\times 10^5 没什么问题。

代码：

void solve(){
    cin>>n>>k>>t;
    for(int i=1;i<=n;i++) cin>>a[i];

    // 离散化 a
    vector<ll> vec;
    for(int i=1;i<=n;i++) vec.push_back(a[i]);
    sort(vec.begin(),vec.end());
    vec.erase(unique(vec.begin(),vec.end()),vec.end());
    for(int i=1;i<=n;i++) a[i]=lower_bound(vec.begin(),vec.end(),a[i])-vec.begin()+1;

    int m=vec.size(); // 种类
    if(vec.size()<=t) return cout<<1<<'\n',void();

    for(int i=1;i<=n;i++) a[n+i]=a[i];
    for(int i=0;i<=m;i++) cnt[i]=0;

    int cur=0,r=1;
    for(int l=1;l<=n;l++){
        while(r<=2*n){
            if(cnt[a[r]]==0){
                if(cur==t) break;
                cur++;
            }
            cnt[a[r]]++,r++;
        }
        jump[l]=r-l;

        cnt[a[l]]--;
        if(cnt[a[l]]==0) cur--;
    }

    ll tot=n*k,cur_dis=0;
    vector<pii> vis(n+1,{-1,-1});
    ll ans=0,u=1;
    while(cur_dis<tot){
        if(vis[u].fi!=-1){
            ll cyc_lenseg=ans-vis[u].fi,cyc_lendis=cur_dis-vis[u].se; 
            ll rem=tot-cur_dis,loops=rem/cyc_lendis; 
            if(loops>0){
                ans+=loops*cyc_lenseg;
                cur_dis+=loops*cyc_lendis;

                fill(vis.begin(),vis.end(),make_pair(-1,-1));
                continue;
            }
        }

        vis[u]={ans,cur_dis};

        ll step=jump[u];
        cur_dis+=step;
        ans++;
        u=(u+step-1)%n+1;
    }

    return cout<<ans<<'\n',void();
}