第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（昆明） AC（带悔贪心）

71 阅读 0 评论 47 点赞

我是靠谱客的博主平常芒果，最近开发中收集的这篇文章主要介绍第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（昆明） AC（带悔贪心），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

下面两个题都是选择 $i$ 有个价值如果选择 $i$ 则不能选择 $i - 1, i + 1$ ，让价值最大或最小

P1792 [国家集训队]种树

野心qwq 的博客

#include<bits/stdc++.h>

using namespace std;

const int N=200010;
int n,m;
int a[N];
int fr[N],to[N];
priority_queue<pair<int,int>> q;
long long ans;
bool del[N];
int main()
{
    ios::sync_with_stdio(false);cin.tie();cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    if(n<m<<1) return cout<<"Error!",0;
    
    for(int i=1;i<=n;i++)
    {
        fr[i]=i-1;
        to[i]=i+1;
        q.push({a[i],i});
    }
    fr[1]=n,to[n]=1;
    
    for(int i=1;i<=m;i++)
    {
        while(del[q.top().second]) q.pop();
        ans+=q.top().first;
        int u=q.top().second;q.pop();
        int l=fr[u],r=to[u];
        
        fr[u]=fr[l];
        to[u]=to[r];
        
        to[fr[l]]=u;
        fr[to[r]]=u;
        
        del[l]=del[r]=1;
        a[u]=a[l]+a[r]-a[u];
        q.push({a[u],u});
    }
    cout<<ans<<'n';
    
    return 0;
}

A-AC

imiMppPpPpPpp题解

#include<bits/stdc++.h>

using namespace std;

const int N=500010;
char s[N];
int a[N],n,m;
int fr[N],to[N];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
int del[N];
int mp[N];
int L[N],R[N];
int main()
{
    ios::sync_with_stdio(false);cin.tie();cout.tie(0);
    cin>>n>>m>>s+1;
    for(int i=1;i<=n;i++) fr[i]=i-1,to[i]=i+1;
    fr[0]=n,to[n]=0;
    for(int i=0;i<=n;i++) L[i]=R[i]=i;
    for(int i=1;i<=n;i++) a[i]=(s[i]!='a')+(s[i+1]!='c');
    a[0]=a[n]=0x3f3f3f3f;
    
    for(int i=0;i<=n;i++) q.push({a[i],i});
    int ans=0,cur=0;
    while(q.size())
    {
        auto [w,u]=q.top();q.pop();
        if(del[u]) continue;
        
        if(cur+a[u]>m) break;
        
        ans++;cur+=a[u];
        
        int l=fr[u],r=to[u];
        
        mp[u]=1;
        L[u]=L[l];
        R[u]=R[r];
        
        fr[u]=fr[l];
        to[u]=to[r];
        
        to[fr[l]]=u;
        fr[to[r]]=u;
        
        del[l]=del[r]=1;
        
        a[u]=a[l]+a[r]-a[u];
        q.push({a[u],u});
        
    }
    
    for(int i=1;i<=n;i++)
    {
        if(!mp[i]||del[i]) continue;
        
        for(int j=L[i]+1;j+1<=R[i];j+=2) s[j]='a',s[j+1]='c';
    }
    cout<<ans<<'n';
    cout<<s+1<<'n';
    return 0;
}