【CF-1355 BCount Triangles】枚举

Count Triangles

题意

给出(A,B,C,D)，保证(Aleq Bleq C leq D),

有多少个三角形，三条边的长度满足(Aleq x leq B leq y leq C leq zleq D)

思路

之前有一次比赛是随便输出一个满足的三角形，这次直接问个数了。

三角形两边之和大于第三边。

我们枚举(x+y)的和，对于每一个和，分别算出(z)的取值个数和((x,y))的取值个数

乘起来，求和。

代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<vector>
#define pb push_back
typedef long long ll;
using namespace std;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 2e5+10;

int arr[N];
int main()
{
    int a,b,c,d;
    scanf("%d%d%d%d",&a,&b,&c,&d);
    ll ans=0;
    for(int i=a+b;i<=b+c;i++)
    {
        int r=min(d-c+1,max(0,i-c));
        int l=min(b-a,i-a-b)-max(0,i-a-c)+1;
        ans+=1LL*l*r;
    }
    printf("%lld
",ans);
    return 0;
}