2024 暑假友谊赛 1

A.096 - Cooking

对于一个食物要么放入一号烤箱要么放入二号烤箱，类似于一号烤箱取或者不取该食物。

那么对于dp[i][j]，表示前i个物品中占用j时间是否成立。那么在成立的情况下，对于二号烤箱所占的时间就是sum-j。

#include<bits/stdc++.h>
#define endl '\n'
#define mk make_pair
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 3e5+10;
int n,m,k;

void sovle(){
    cin>>n;
    vector<int>a(n);
    int sum=0;
    for(int i=0;i<n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    int dp[n+1][sum+1];
    for(int i=0;i<=n;i++){
        for(int j=0;j<=sum;j++){
            dp[i][j]=0;
        }
    }
    dp[0][0]=1;     //前0个物品占用1号烤箱0分钟
    for(int i=0;i<n;i++){
        for(int j=0;j<=sum;j++){
            if(dp[i][j]){
                dp[i+1][j]=1;   //相当于不将该物品放入1中
                dp[i+1][j+a[i]]=1;  //将该物品放入1中
            }
        }
    }
    int ans=sum;
    for(int i=0;i<=sum;i++){
        if(dp[n][i]) ans=min(ans,max(i,sum-i));
    }
    cout<<ans<<endl;
}

signed main()
{	
    ios::sync_with_stdio(false), cin.tie(0),cout.tie(0); 
    int t = 1; 
    //cin>>t;
    while (t--){
        sovle();
    }

    return 0;
}

B.C - 2D Plane 2N Points

贪心地对红点按x从大到小排序，蓝点按x从小到大排序。然后枚举a，再枚举b，对于满足条件的b，再去找到最小y值的b。我们担心的是，会不会有b点与当前a配对后会造成其他b点浪费的情况。但实际上红点从大到小，蓝点从小到大排序的情况下，因为枚举第一层a的x会不断减小，第二层枚举的x会不断增大，在u处蓝点x满足条件，后面蓝点的x对于u处后面红点的x也一定满足条件，相当于x被忽略掉了，但是y越靠近红点的y越不会浪费。

#include<bits/stdc++.h>
#define endl '\n'
#define mk make_pair
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 3e5+10;
const int mod = 998244353;
int n,m,k,sum,num;
map<int,int>v;

void sovle(){
    cin>>n;
    vector<pair<int,int> >a(n),b(n);
    for(int i=0;i<n;i++) cin>>a[i].first>>a[i].second;
    for(int i=0;i<n;i++) cin>>b[i].first>>b[i].second;
    sort(b.begin(),b.end());
    sort(a.begin(),a.end(),greater<pair<int,int> >());
    for(int i=0;i<n;i++){
        int u=-1;
        for(int j=0;j<n;j++){
            if(v[j]||a[i].first>=b[j].first||a[i].second>=b[j].second) continue;
            if(u==-1) u=j;
            if(u!=-1&&b[u].second>b[j].second) u=j;
        }
        if(u!=-1){
            v[u]=1;
            sum++;
        }
    }
    cout<<sum<<endl;
}

signed main()
{	
    ios::sync_with_stdio(false), cin.tie(0),cout.tie(0); 
    int t = 1; 
    //cin>>t;
    while (t--){
        sovle();
    }

    return 0;
}

D.D - Cake 123

要求k个三个数的和的最大和，分治思想先求k个前两个数的最大和，再求出这些数与第三个数的最大和。

#include<bits/stdc++.h>
#define endl '\n'
#define mk make_pair
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 3e5+10;
const int mod = 998244353;
int n,m,k,sum,num;
int x,y,z;

void sovle(){
    cin>>x>>y>>z>>k;
    vector<int>a(x),b(y),c(z);
    for(int i=0;i<x;i++) cin>>a[i];
    for(int i=0;i<y;i++) cin>>b[i];
    for(int i=0;i<z;i++) cin>>c[i];
    sort(a.begin(),a.end(),greater<int>());
    sort(b.begin(),b.end(),greater<int>());
    sort(c.begin(),c.end(),greater<int>());
    int xx=0,yy=0,zz=0;
    int aa1=0,bb1=0,cc1=0;
    vector<int>aa,bb,cc;
    for(int i=0;i<x;i++){
        for(int j=0;j<y;j++){
            aa.push_back(a[i]+b[j]);
        }
    }   
    sort(aa.begin(),aa.end(),greater<int>());
    while(aa.size()>k){
        aa.pop_back();
    }
    for(auto ed:aa){
        for(int j=0;j<z;j++){
            bb.push_back(ed+c[j]);
        }
    }
    sort(bb.begin(),bb.end(),greater<int>());
    for(auto ed:bb){
        if(aa1==k) return;
        aa1++;
        cout<<ed<<endl;
    }
}

signed main()
{	
    ios::sync_with_stdio(false), cin.tie(0),cout.tie(0); 
    int t = 1; 
    //cin>>t;
    while (t--){
        sovle();
    }

    return 0;
}