Codeforces Round #317 (Div. 2) C Lengthening Sticks （组合，数学）

一个合法的三角形的充要条件是a<b+c，其中a为最长的一边，可以考虑找出所有不满足的情况然后用总方案减去不合法的情况。

对于一个给定的总长度tl（一定要分完，因为是枚举tl，不分配的长度已经考虑过了），分成三份，因为可以有两份为零，采用插空法的时候

增加两个假想长度为零的单位，所以方案数是C(tl+2,2)，

假设a是增加长度以后最长的一边，r是tl减去给a增加长度之后剩下的长度，

那么不满足的情况的条件就可以写成a+tl-r>=b+c+r，很容易转化为r<=(a-b-c+tl)/2，显然r<=tl，如果r<0，

说明tl全部加到a上也不会超过b+c的和，方案数为0。对于剩下的r，分成三份l_b,l_c和没用上的，类似之前总长度的分配，方案数为C(r+2,2)，

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll cal(int a,int b,int c,int tl)

{

    int r = (a-b-c+tl)>>;

    if(r<) return ;

    if(r>tl) r = tl;

    return (ll)(r+)*(r+)>>;

}

int main()

{

    int a,b,c,l; scanf("%d%d%d%d",&a,&b,&c,&l);

    ll ans = ;

    for(int i = ; i <= l; i++){

        ans += (ll)(i+)*(i+)>>;

        ans -= cal(a,b,c,i);

        ans -= cal(b,a,c,i);

        ans -= cal(c,a,b,i);

    }

    printf("%I64d",ans);

    return ;

}

巴特西

Codeforces Round #317 (Div. 2) C Lengthening Sticks （组合，数学）

最新文章

热门文章