【Codeforces Round #643 (Div. 2) C】Count Triangles
题目链接
翻译
让你找 (3) 条边 (x,y,z), 要求 (Ale xle Ble yle Cle zle D)
且 (x,y,z) 能组成三角形。
问你这样的 (x,y,z) 的个数。
题解
对于最后选出来的边，我们只需要关注 (x+y) 是不是大于 (z) 就好了 (两边之和大于第三边)。
因为 (x<=y<=z) 且 (x,y,z) 都是正整数。所以 (y+z>x) 和 (z+x>y) 恒成立。
首先, 比较明显的是我们可以先枚举其中一条边 (x) 。
然后 (y) 的话会从 (B) 到 (C) 变化，那么 (x+y) 就会在 [(x+B),(x+C)] 这个区间内变化。
这个区间和 ([C,D]) 这个区间的相交情况有 (5) 种可能(除去完全在 ([C,D]) 左边这种情况不可能)。
分别把这 (5) 种情况画出来, 算一下 (y) 在这个区域里面对答案的贡献就好了((z) 的值要比 (x+y) 来的小)。
会对应很多的类似1,2,3,4... 的公差为 (1) 的等差数列。以及整个 ([C,D]) 区域的值都可以取的情况(x+y>D)。
强烈建议画个数轴来统计!
solution2
枚举 (x), 每次让 a[x+B]++ 然后让 a[x+C+1]--，这样我们就能统计出来有多少个 (x+y) 的值为 (s) 了，也即 (a[s])。
然后，我们对 (a) 做一个前缀和。
对于 (z) 属于 (C) 到 (D)，判断有多少个 (s) 满足 (s>z) 就好。也即累加 (a[N]-a[z])。
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
LL a,b,c,d;
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin >> a >> b >> c >> d;
LL ans = 0;
for (LL x = a;x <= b;x++){
if (x+b>d){
ans += (d-c+1)*(c-b+1);
continue;
}
if (x+b <= c && x+c <= d){
ans += (1+x)*x/2;
}
if (x+b <= c && x+c > d){
ans += (1+d-c)*(d-c)/2+(x+c-d)*(d-c+1);
}
if (x+b > c && x+c <= d){
LL a1 = x+b-c,n = c-b+1;
LL an = a1 + n - 1;
ans += (a1+an)*n/2;
}
if (x+b > c && x+c > d){
LL a1 = x + b - c;
LL n = (d-x-b+1);
LL an = a1 + n-1;
ans += (a1+an)*n/2;
ans += (x+c-d)*(d-c+1);
}
}
cout << ans << endl;
return 0;
}