【蓝桥真题练习】蓝桥杯 2021 国赛 A 组 E 题
题目形貌小蓝发现了一个有趣的数列, 这个数列的前几项如下:
1,1,2,1,2,3,1,2,3,4,…1,1,2,1,2,3,1,2,3,4,…
小蓝发现, 这个数列前 11 项是整数 11 , 接下来 22 项是整数 11 至 22 , 接下来 33 项是整数 11 至 33 , 接下来 44 项是整数 11 至 44 , 依次类推。
小蓝想知道, 这个数列中, 一连一段的和是多少。
输入格式
输入的第一行包罗一个整数 TT, 表示询问的个数。
接下来 TT 行, 每行包罗一组询问, 其中第 ii 行包罗两个整数 lil**i 和 rir**i, 表示 询问数列中第 lil**i 个数到第 rir**i 个数的和。
输特别式
输出 TT 行, 每行包罗一个整数表示对应询问的答案。
输入输出样例
输入 #1
3
1 1
1 3
5 8
输出 #1
1
4
8
剖析
起首我们观察这个数列，我们可以把他分解成一个三角形的二维数组
1
1 2
1 2 3
1 2 3 4
1 2 3 4 5
因此我们可以得到以下性质：
第n行的和为: (n + 1) * n / 2（高斯公式）
前n行的和为：n * (n + 1) * (n + 2) / 6
我们可以使用类似于前缀和的方法来解题，既前r个数字和减去前l个数字和。
我们该如何来求数字和呢？如果我们知道他所在的行数以及他所在的列数，那么我们就可以使用上述公式来求解，既：
前n-1行的和 再加上 1到这一列的和
如今的题目转到了如何求行和列，对于行数我们可以罗列行数来进行二分求解
int Find(int x)
{
int l = 0, r = 100000000;
while (l < r)
{
int mid = l + (r - l) / 2;
if ((mid + 1) * mid / 2 >= x)
r =mid;
else
l = mid + 1;
}
return r;
}
同样的道理，我们知道了它的行数以及它一维的位置，可以得出它的列坐标
列坐标 = index - 行 * （行 + 1）/ 2
代码
#include<bits/stdc++.h>using namespace std;#define int long longint l, r, t;int indexl, indexr;int suml, sumr;int Find(int x)
{
int l = 0, r = 100000000;
while (l < r)
{
int mid = l + (r - l) / 2;
if ((mid + 1) * mid / 2 >= x)
r =mid;
else
l = mid + 1;
}
return r;
}
int f(int x)//高斯公式{ return (x + 1) * x / 2;}int sumn(int x){ return x * (x + 1) * (x + 2) / 6;}signed main(){ cin >> t; while (t--) { cin >> l >> r; indexl = l - f(Find(l) - 1); indexr = r - f(Find(r) - 1); suml = sumn(Find(l) - 1) + indexl * (indexl - 1) / 2; sumr = sumn(Find(r) - 1) + indexr * (indexr + 1) / 2; cout << sumr - suml << endl; } return 0;}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]