C/C++教程

CF1355C Count Triangles

本文主要是介绍CF1355C Count Triangles,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

思路:

枚举z,对于每个可能的z,计算有多少种可行的x,y组合。

实现:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 
 5 ll sum(ll l, ll r)
 6 {
 7     return (l + r) * (r - l + 1) / 2;
 8 }
 9 
10 ll cal(ll z, ll l, ll r)
11 {
12     ll x = min(l, r), y = max(l, r);
13     ll tmp = 0; 
14     if (y >= z - 1) tmp = sum(z - x, z - 1); 
15     else
16     {
17         tmp = y * min(z - y, x);
18         if (x > z - y) tmp += sum(z - x, y - 1);
19     }
20     return l * r - tmp;
21 }
22 
23 ll work(ll z, ll a, ll b, ll c, ll d)
24 {
25     return cal(z, b, d) - cal(z, b, c - 1) - cal(z, a - 1, d) + cal(z, a - 1, c - 1);
26 }
27 
28 int main()
29 {
30     ll a, b, c, d;
31     while (cin >> a >> b >> c >> d)
32     {
33         ll res = 0;
34         for (ll z = c; z <= d; z++) res += work(z, a, b, b, c);
35         cout << res << endl;
36     }
37     return 0;
38 }
这篇关于CF1355C Count Triangles的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!