第 45 届国际大学生程序设计竞赛（ICPC）亚洲网上区域赛模拟

(有空再解释，自己看吧~)

题解1：https://blog.csdn.net/hhuhgfhggy/article/details/109425017
题解2：https://blog.csdn.net/m0_46744670/article/details/109447261
题解3：差分

#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn=1e7;
int a,b,c,d;
ll p[maxn],f[maxn];
int main(){
    cin>>a>>b>>c>>d;
    for(int i=0;i<=a;i++){
        f[i]++;
        f[i+b+1]--;
    }
    for(int i=1;i<=a+b;i++)f[i]+=f[i-1];
    for(int i=0;i<=a+b;i++){
        p[i]+=f[i];
        p[i+c+1]-=f[i];
    }
    for(int i=1;i<=a+b+c;i++)p[i]+=p[i-1];
    ll ans=0;
    for(int i=0;i<=d;i++)ans+=p[i];
    cout<<ans<<endl;
    return 0;
}

一下动规+前缀和

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
#include<cmath>
#define  pii pair<int,int>
#define mem(kk,i) memset(kk,i,sizeof kk)
using namespace std;
typedef long long ll;
const int maxn=1e7;
const int INF=0x3f3f3f3f;
/*next_permutation();
prev_permutation():
*/
ll b[maxn],c[maxn];
int x,y,z,d;
int main(){
    mem(b,0);
    mem(c,0);
    cin>>x>>y>>z>>d;

    if(x>y)swap(x,y);
    if(x>z)swap(x,z);
    if(y>z)swap(y,z);

    for(int i=0;i<=x+y;i++){
        if(i<=x)b[i]=i+1;
        else if(x+y-i<=x)b[i]=x+y-i+1;
        else b[i]=x+1;
    }
    if(x+y>=z){
        c[0]=b[0];
        for(int i=1;i<=x+y;i++)
            c[i]=b[i]+c[i-1];
        for(int i=x+y;i>=z+1;i--)
            c[i]=c[i]-c[i-(z+1)];
        c[x+y+z]=b[x+y];
        for(int i=x+y+z-1,e=z-1;i>=x+y+1;i--,e--)
            c[i]=c[i+1]+b[e];
    }
    else{
        c[0]=b[0];
        for(int i=1;i<=x+y;i++)
            c[i]=b[i]+c[i-1];
        for(int i=x+y+1;i<=z;i++)
            c[i]=c[i-1];
        for(int i=z+1,e=0;i<=x+y+z;i++,e++)
            c[i]=c[x+y]-c[e];
    }
    ll ans=0;
    for(int i=0;i<=d;i++)
        ans+=c[i];
    cout<<ans<<endl;
    return 0;
}

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
#include<cmath>
#define  pii pair<int,int>
#define mem(kk,i) memset(kk,i,sizeof kk)
using namespace std;
typedef long long ll;
const int maxn=1e7;
const int INF=0x3f3f3f3f;
/*next_permutation();
prev_permutation():
*/
ll b[maxn],c[maxn];
int x,y,z,d;
int main(){
    mem(b,0);
    mem(c,0);
    cin>>x>>y>>z>>d;

    if(x>y)swap(x,y);
    if(x>z)swap(x,z);
    if(y>z)swap(y,z);

    for(int i=0;i<=x+y;i++){
        if(i<=x)b[i]=i+1;
        else if(x+y-i<=x)b[i]=x+y-i+1;
        else b[i]=x+1;
    }
    ll ans=0;
    for(int i=0;i<=x+y;i++){
        //cout<<b[i]<<endl;
        if(d-i>=z){
            ans+=b[i]*(z+1);
        }else if(d-i<z&&d-i>=0){
            ans+=b[i]*(d-i+1);
        }
    }
    cout<<ans<<endl;
    return 0;
}