【蓝桥真题练习】蓝桥杯 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 long

int 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;
}