cf 1355C

1355C
1800的题
题意挺简单的，就是给你四个数a,b,c,d,且这四个数不严格递增，即大于等于，然后这四个数划分为了三个区间即[a,b],[b,c],[c,d]，从这三个区间里取三个数x,y,z,使这三个数能构成一个三角形，即x+y>z,因为x,y,z是不严格递增的所以只要判断这一个条件就行。
比较容易想到的思路是两个for循环，枚举x和y的取值然后从[c,d]中看z可以取多少种,代码的实现如下，具体就不细讲了，比较容易懂

for(int i = a; i <= b; i++){for(int j = b; j <= c; j++){int m = i+j;if(m>c&&m<=d){ans += m-c;}else if(m>d){ans += d-c+1;}}}

那么很显然对于一个1800的题，两个for循环肯定TLE，所以要想办法优化，我们可以设x+y=M,然后枚举M的取值，这样时间复杂度就可以优化到O(n)的程度，然后对M的取值在[c,d]中的z可取的值有多少种即可求出答案，现在的关键点是，如何求出当x+y=M时，x+y有多少种组合方式。
介绍一个思想差分，举个例子，给你一个数组，1 2 3 4，正常数组的存储是直接放进去，但如果是差分数组的话，是以1，1，1，1这样存储的，即a[n]=a[1]+a[2]+…+a[n-1]，这样看好像是更复杂，但对于一些区间类的题目这种方法更为有效。
回到题目中来，如果我要求x+y=M有多少种组合方式时，可以差分的方式，具体实现看代码

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define rep(i, a, n) for(int i = a; i < n; i++)
#define per(i, a, n) for(int i = n-1; i >= a; i--)
#define INF 1ll<<60
const int maxn = 1e6+10;
int sum[maxn];
int main(){int a, b, c, d;scanf("%d%d%d%d", &a, &b, &c, &d);ll ans = 0;rep(i,a,b+1){sum[i+b]++;sum[i+c+1]--;	//这里用了差分的思想，也就是对于[i+b,i+c]这个区间加一}rep(i,a+b,b+c+2){sum[i]+=sum[i-1];	//这里得到的是a+b=M的组合方式有多少种}rep(i,c+1,b+c+2){if(i>d){ans += 1LL*(d-c+1)*sum[i];	}else ans += 1LL*sum[i]*(i-c);}printf("%lld\n", ans);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！