Lengthening Sticks
Problem's Link: http://codeforces.com/contest/571/problem/A
Mean:
给出a,b,c,l，要求a+x,b+y,c+z构成三角形，x+y+z<=l，成立的x,y,z有多少种。
analyse:
这题在推公式的时候细心一点就没问题了。
基本的思路是容斥：ans=所有的组合情况-不满足条件的情况。
1.求所有的组合情况
方法是找规律：
首先只考虑l全部都用掉的情况。
l=1：3
l=2：6
l=3：10
l=4：15
......
到这可能你会发现，其实l=i时，结果就是1+2+...+(i+1)，即：C(i+2,2)，也就是三角数。
然而i可以取0~l中的任何一个，那也很简单，一路累加上去就可。
2.不满足条件的情况：
三角形满足的条件是什么？任意两边之和大于第三边，那么不满足的必要条件就是第三边小于等于其它两边之和。
分别枚举a,b,c做第三边的情况，再考虑将剩下的l拆分三份分配给a,b,c依旧不满足的情况即可。
Time complexity: O(N)
Source code:
/*
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-08-23-12.24
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
LL cal( LL a , LL b , LL c , LL l)
{
LL ans = 0;
for( LL i = max(b + c - a , 0LL); i <= l; ++ i)
{
LL x = min( l - i , a + i -b - c);
ans +=( 1 + x) *( 2 + x) / 2;
}
return ans;
}
int main()
{
ios_base :: sync_with_stdio( false);
cin . tie( 0);
LL a ,b , c , l;
cin >> a >>b >> c >> l;
LL ans = 0;
for( LL i = 0; i <= l; ++ i)
ans += LL( 1 + i) *( 2 + i) / 2;
ans -= cal( a ,b , c , l);
ans -= cal(b , a , c , l);
ans -= cal( c , a ,b , l);
cout << ans;
return 0;
}
/*
*/
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-08-23-12.24
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
LL cal( LL a , LL b , LL c , LL l)
{
LL ans = 0;
for( LL i = max(b + c - a , 0LL); i <= l; ++ i)
{
LL x = min( l - i , a + i -b - c);
ans +=( 1 + x) *( 2 + x) / 2;
}
return ans;
}
int main()
{
ios_base :: sync_with_stdio( false);
cin . tie( 0);
LL a ,b , c , l;
cin >> a >>b >> c >> l;
LL ans = 0;
for( LL i = 0; i <= l; ++ i)
ans += LL( 1 + i) *( 2 + i) / 2;
ans -= cal( a ,b , c , l);
ans -= cal(b , a , c , l);
ans -= cal( c , a ,b , l);
cout << ans;
return 0;
}
/*
*/
![洛谷P2871-[USACO07DEC]Charm Bracelet S（01背包模板题）](https://ucc.alicdn.com/images/user-upload-01/20200725131735571.png?x-oss-process=image/resize,h_160,m_lfit)