swift's blog

swift's blog

题解 CF571A 【Lengthening Sticks】

posted on 2019-09-01 19:43:18 | under 题解 |

我们先求出来所有可能的方案,共有 $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;
}