Problem - 1355C - Codeforces

题目大意:定义三条边$x,y,z$,满足$A\le x\le B\le y\le C\le z\le D$,求出有多少组$x,y,z$的值可以作为三角形的三边长.

解题思路:根据题目的条件可以推断出,当满足$x+y>z$时,这样的一组值就是一组符合值.
$z$的范围是$[C,D]$,那么应该满足$x+y>C$,直接枚举$x+y$的值,$x,y$的最小值分别为$A,B$,则枚举的范围的下界是$max(C+1,A+B)$.上界是$B+C$.
而对于枚举的每个$x+y$的值,对应的$z$的取值小于$x+y$,且$z$最大为$D$,则可以选择的$z$的范围是$min(x+y-C,D-C+1)$.
对于$x+y$的可选组合。
$x$的可选值为 { a , a + 1 , a + 2 , . . . , b } \{a, a+1, a+2, ..., b\} {a,a+1,a+2,...,b}
$y$的可选值为 { b , b + 1 , b + 2 , . . . , c } \{b, b+1,b+2,...,c\} {b,b+1,b+2,...,c}.
对于已经枚举出来的定值$x+y$与之对应的每个$x$的取值为
{ x + y − a , x + y − a − 1 , x + y − a − 2 , . . . , x + y − b } \{x+y-a, x+y-a-1, x+y-a-2, ...,x+y-b\} {x+y−a,x+y−a−1,x+y−a−2,...,x+y−b}.
对应$x$本身的范围$[A,B]$,即可得$x+y$的选取范围为$min(b,x+y-a)-max(a,x+y-b)+1$.
$z$的选择方式乘以$x+y$的选择方式即为当前枚举$x+y$值的总数。

#include
using namespace std;
#define ll long long
#define syncfalse ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
ll a, b, c, d;
int main(){syncfalse#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);#endifcin>>a>>b>>c>>d;ll ans = 0;for (ll i = max(c+1, a+b); i <= b+c; ++i){ans+=(min(d+1,i)-c)*(min(i-b,b)-max(i-c,a)+1);}cout << ans << "\n";return 0;
}