题解 CF571A 【Lengthening Sticks】
swiftc
2019-09-01 19:43:18
我们先求出来所有可能的方案,共有 $C(l+3,3)$ 种(插板法),再减去不合法的方案数
不合法的方案数要分三类讨论,$a$ 为最长边; $b$ 为最长边; $c$ 为最长边;对于每一种情况,枚举给最长边加多少长度,然后求出剩下的长度(注意,需要和$c+i-a-b$ ( $c$ 为最长边)取$min$,因为我们需要保证这种情况不合法),然后就可以用插板法求了
__代码:__
```cpp
#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;
}
```