题解 CF571A 【Lengthening Sticks】

swiftc · 2019-09-01 19:43:18 · 题解

我们先求出来所有可能的方案，共有 C(l+3,3) 种（插板法），再减去不合法的方案数

不合法的方案数要分三类讨论，a 为最长边; b 为最长边; c 为最长边;对于每一种情况，枚举给最长边加多少长度，然后求出剩下的长度（注意，需要和c+i-a-b ( c 为最长边)取min，因为我们需要保证这种情况不合法)，然后就可以用插板法求了

代码:

#include<bits/stdc++.h>
#define int long long
#define max(a,b) a>b?a:b
using namespace std;
int ans;
int C(int a,int b){
    if(a<b)return 0;
    if(b==2){
        return a*(a-1)/2;
    }
    else{
        return a*(a-1)*(a-2)/6;
    }
}
void work(int a,int b,int c,int l){
    for(int i=max(0,a+b-c);i<=l;i++){
        int tmp=min(l-i,c+i-a-b);
        ans-=C(tmp+2,2);
    }
}
main(){

    int a,b,c,l;
    cin>>a>>b>>c>>l;
    ans+=C(l+3,3);
    work(a,b,c,l);
    work(a,c,b,l);
    work(b,c,a,l);
    cout<<ans<<endl;
}