2021第十二届蓝桥杯国赛-F123

2021-07-03 · 117次阅读 · 原创 · 数据结构与算法

#蓝桥杯 #题解 #数学 #前缀和

题面

【问题描述】

小蓝发现了一个有趣的数列，这个数列的前几项如下：

1, 1, 2, 1, 2, 3, 1, 2, 3, 4, …

小蓝发现，这个数列前 1 项是整数 1，接下来 2 项是整数 1 至 2，接下来 3 项是整数 1 至 3，接下来 4 项是整数 1 至 4，依次类推。

小蓝想知道，这个数列中，连续一段的和是多少。

【输入格式】

输入的第一行包含一个整数 $T$ ，表示询问的个数。

接下来 $T$ 行，每行包含一组询问，其中第 $i4 行包含两个整数 $l_i$ 和 $r_i$ ，表示询问数列中第 $l_i$ 个数到第 $r_i$ 个数的和。

【输出格式】

输出 $T$ 行，每行包含一个整数表示对应询问的答案。

【样例输入】

【样例输出】

1
4
8

【评测用例规模与约定】

对于 10% 的评测用例， $1 ≤ T ≤ 30, 1 ≤ l_i ≤ r_i ≤ 100$ 。

对于 20% 的评测用例， $1 ≤ T ≤ 100, 1 ≤ l_i ≤ r_i ≤ 1000$ 。

对于 40% 的评测用例， $1 ≤ T ≤ 1000, 1 ≤ l_i ≤ r_i ≤ 10^6$ 。

对于 70% 的评测用例， $1 ≤ T ≤ 10000, 1 ≤ l_i ≤ r_i ≤ 10^9$ 。

对于 80% 的评测用例， $1 ≤ T ≤ 1000, 1 ≤ l_i ≤ r_i ≤ 10^{12}$ 。

对于 90% 的评测用例， $1 ≤ T ≤ 10000, 1 ≤ l_i ≤ r_i ≤ 10^{12}$ 。

对于所有评测用例， $1 ≤ T ≤ 100000, 1 ≤ l_i ≤ r_i ≤ 10^{12}$ 。

思路

借助前缀和的思想。首先对序列进行分组（第一组： $1-1$ ，第二组： $1-2$ ，第三组： $1-3$ ，…，第 $n$ 组： $1-n$ ）求和，保存前缀和（记为分组前缀和），存入 sum[i] （表示前 $i$ 个分组中的数的总和）。

对于一个位置 $x$ ，其前缀和由两部分组成，一部分为其所在的分组的前一个分组的 分组前缀和，另一部分是所在分组的第一项到该位置的数的和。

那么对于本问题中的每个询问，只要找到r位置的前缀和，再减去 $l - 1$ 位置的前缀和，即为该次询问的答案。具体实现过程见下面代码。

代码

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 2e6 + 10;
LL sum[N];    //保存分组前缀和
int T;
LL l, r;

//求前 1 - x 的和
inline LL S(LL x) {
    return x * (x + 1) / 2;
}

//二分查找在 最多前多少个完整分组的元素个数 < x 的个数，
int get(LL x) {
    int l = 0, r = N;
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (S(mid) < x) l = mid;
        else r = mid - 1;
    }
    return l;
}

int main() {
    for (int i = 1; i <= N - 10; i++) sum[i] = sum[i - 1] + S(i);   //计算分组前缀和
    cin >> T;
    while (T--) {
        scanf("%lld%lld", &l, &r);
        l--;
        int x = get(l), y = get(r);     //找到 l 和 r 位置对应的最多前缀分组个数的分组数量 x 和 y
        LL lv = sum[x] + S(l - S(x));
        LL rv = sum[y] + S(r - S(y));
        printf("%lld\n", rv - lv);
    }
    return 0;
}

标题：	2021第十二届蓝桥杯国赛-F123
链接：	https://www.fightingok.cn/detail/101
更新：	2022-10-22 21:47:46
版权：	本文采用 CC BY-NC-SA 3.0 CN 协议进行许可