codeforces 572 C. Lengthening Sticks（数学）

题目链接：http://codeforces.com/contest/572/problem/C

题意：给出a,b,c,l要求a+x,b+y,c+z构成三角形，x+y+z<=l，成立的x,y,z有多少种

题解：看上去感觉挺复杂的其实就是简单枚举一下就行，首先要知道可以将总的取法减去不满足的取法就可以得到答案，

当然也可以直接枚举可行的方案但是会很复杂。所以最好采用减的方案。

总的方案的求法：就是将l分成3份，显然分法有C(i+2)取(2)。

然后再分别减去以a,b,c为最长边不符合条件的种类即可，具体看一下代码挺好理解的。

#include <iostream>

using namespace std;

typedef long long ll;

ll GET(int x , int y , int z , int l , int MAX) {

    ll sum = 0;

    for(int i = MAX - x ; i <= l ; i++) {

        if(x + i >= y + z) {

            int num = min(l - i , i + x - (y + z));

            sum += (ll)(num + 1) * (num + 2) / 2;

        }

    }

    return sum;

}

int main() {

    int a , b , c , l;

    cin >> a >> b >> c >> l;

    ll sum = 0;

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

        sum += (ll)(i + 1) * (i + 2) / 2;

    }

    int MAX = max(max(a , b) , c);

    sum -= GET(a , b , c , l , MAX);

    sum -= GET(b , a , c , l , MAX);

    sum -= GET(c , a , b , l , MAX);

    cout << sum << endl;

    return 0;

}

巴特西

codeforces 572 C. Lengthening Sticks（数学）

最新文章

热门文章