头像

Cyan

四川成都

深度强化学习炼丹师

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

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

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

题面

【问题描述】

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

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

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

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

【输入格式】

输入的第一行包含一个整数 TT,表示询问的个数。

接下来 TT 行,每行包含一组询问,其中第 $i4 行包含两个整数 lil_irir_i,表示询问数列中第 lil_i 个数到第 rir_i 个数的和。

【输出格式】

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

【样例输入】

3
1 1
1 3
5 8

【样例输出】

1
4
8

【评测用例规模与约定】

对于 10% 的评测用例,1T30,1liri1001 ≤ T ≤ 30, 1 ≤ l_i ≤ r_i ≤ 100

对于 20% 的评测用例,1T100,1liri10001 ≤ T ≤ 100, 1 ≤ l_i ≤ r_i ≤ 1000

对于 40% 的评测用例,1T1000,1liri1061 ≤ T ≤ 1000, 1 ≤ l_i ≤ r_i ≤ 10^6

对于 70% 的评测用例,1T10000,1liri1091 ≤ T ≤ 10000, 1 ≤ l_i ≤ r_i ≤ 10^9

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

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

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

思路

借助前缀和的思想。首先对序列进行分组(第一组:111-1,第二组:121-2, 第三组:131-3,…,第 nn 组:1n1-n)求和,保存前缀和(记为分组前缀和),存入 sum[i] (表示前 ii 个分组中的数的总和)。

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

那么对于本问题中的每个询问,只要找到r位置的前缀和,再减去 l1l - 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 协议进行许可