The 15th Shandong CCPC Provincial Collegiate Programming Contest（很有一些经典算法题，以后可以做）

L. Stella

简单比较

D. Distributed System

学习积累了差分有头尾两截的情况

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long

const int N=200010;
int n,q;
int d[N];
signed main(){
    std::ios::sync_with_stdio(false);
    int T;cin>>T;
    while(T--){
        cin>>n>>q;for(int i=0;i<=n;i++)d[i]=0;
        int ans=0;
        while(q--){
            int a,b;
        cin>>a>>b;
        
        ans+=a/n;a%=n;
        if(a){
            int l=b;int r=(b+a-1)%n;
        if(l<=r){
            d[l]++;d[r+1]--;
        }else {
            d[l]++;d[n]--;
            d[0]++;d[r+1]--;
        }
        }
        
    
        }
        int cur=0;
        for(int i=0;i<=n-1;i++){
            cur+=d[i];
            cout<<cur+ans<<" ";
        }cout<<'\n';
    }
}

A.Project Management

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

const int N=200010;
int n;

signed main(){
    std::ios::sync_with_stdio(false);
    int T;cin>>T;
    while(T--){
        
        cin>>n;
        vector<vector<pair<int,int>>> A(n+1);for(int i=1;i<=n;i++)A[i].clear();
        for(int i=1;i<=n;i++){
            int ta,tb;cin>>ta>>tb;
            A[ta].push_back({tb,i});
        }
        vector<int> ans;
        for(int i=n;i>=1;i--){
        sort(A[i].begin(),A[i].end());

int m=A[i].size();
            int p=-1;int mx=0;
            for(int j=0;j<m;j++){
                int sub=max(0,(int)ans.size()-A[i][j].first);
                int add=m-j;//后面的相同a，b更大的可以拿上
                if(mx<add-sub){
                    mx=add-sub;
                    p=j;
                }
            }

            if(p!=-1){
                int sub=max(0,(int)ans.size()-A[i][p].first);
                while(sub--)ans.pop_back();
                for(int j=p;j<m;j++){
                    ans.push_back(A[i][j].second);
                }
            }
        }

        cout<<ans.size()<<'\n';
        for(auto x:ans){
            cout<<x<<' ';
        }cout<<'\n';
    }
}

G. Assembly Line

每个工件理想完成时间是t+k-w,如果前面的完成时间在这个之前，会阻碍一个单位时间

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long

const int N=200010;
int n,k;
int a[N];

void solve(){
        cin>>n>>k;
        for(int i=1;i<=n;i++){
            int wi,ti;cin>>wi>>ti;
            a[i]=ti+k-wi;
        }

        sort(a+1,a+n+1);
        for(int i=2;i<=n;i++){
            a[i]=max(a[i],a[i-1]+1);
        }
        cout<<a[n]<<'\n';
}

signed main(){
    std::ios::sync_with_stdio(false);
    int T;cin>>T;
    while(T--){
        solve();
    }
}