04 d1d2

wcqk

2026-08-03 09:43:25

发布于：浙江

11阅读

0回复

0点赞

https://www.acgo.cn/problemset/info/117715

#include<bits/stdc++.h>
using namespace std;

int n,m;


int main(){
    cin>>n>>m;
    vector<vector<int>>ele;
    for(int i=1;i<=n;i++){
        int x,y;cin>>x>>y;

        if(m-x>=1)ele[m-x].push_back(y);
    }

    multiset<int>sa;

    long long ans=0;

    for(int i=m-1;i>=1;i--){
        for(auto y:ele[i]){
            sa.insert(y);
        }
    

        if(!sa.empty()){
            auto it=--sa.end();
            ans+=*it;
    
            sa.erase(it);
        }
    }

    cout<<ans;
    
}

https://www.acgo.cn/problemset/info/103701

void solve(){
    int n,sum[100100],a[100010];cin>>n;
    string s;
    cin>>s;
    s=" "+s;

    for(int i=1;i<=n;i++){
        sum[i]=sum[i-1]+(s[i]-'0');
    }

    for(int i=0;i<=n;i++){
        a[i]=sum[i]-i;
    }
    
    //原问题 $\sum^r_{i=l}a_i=r-l+1$ 可以转化为
    //sum[r]-r=sum[l-1]-(l-1)
    //于是想到 用 a[i] 存 sum[i]-i;
    // 等价于 a[r]=a[l-1];
    // 于是考虑以 r 结尾时，前面有多少个值与 a[r] 相同。
    
    map<int,int>mp;
    int ans=0;
    mp[a[0]]=1;

    for(int i=1;i<=n;i++){
        ans+=mp[a[i]];
        mp[a[i]]++;
    }
    cout<<ans<<endl;
}

int main(){
    int t;cin>>t;
    while(t--){ 
        solve();
    }
}

有帮助，赞一个

去预览

0/2000

这里空空如也

热门讨论