专栏文章

题解：P13504 [OOI 2024] More Gifts

SSunburstFan
P13504题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mimzwzbj
此快照首次捕获于
2025/12/01 18:17
3 个月前
此快照最后确认于
2025/12/01 18:17
3 个月前
查看原文
OOI 超级无敌强强题。
不难发现，如果初始序列中的元素种类本身就只有 x≤tx\le t 种，那么答案就是 11。
如果原序列中有大于 tt 中元素，显然一个人能拿走的长度一定小于 nn。
我们可以把两个序列 aa 拼接起来，就可以计算一个人从某一种元素出发最多能拿多少长度。
注意到 ai∈[1,109]a_i \in [1,10^9]，值域很大，而本题中我们只需要关心元素之间是否相等，所以先将 aia_i 离散化一下。
我们考虑维护 jumpijump_i 表示从第 ii 个元素开始一个人最多能拿多少个礼物。
这个东西可以用滑动窗口维护。
计算出 jumpijump_i 后就可以模拟我们可爱的小学奥数《周期问题》 的解题过程计算答案，详细过程见代码。
进入循环节前最多走 nn 步，走出循环节之后也最多走 nn 步，因此这部分的时间复杂度是 O(N)O(N) 的。
整个算法的瓶颈在于离散化，总体时间复杂度 O(Nlog⁡N)O(N\log N)，常数有点大但是通过 n≤3×105n\le 3\times 10^5 没什么问题。
代码：
CPP
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();
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...