hh198

用户名：hh198

访问量：1787

签　名：

等　　级
排　　名	2140
经　　验	2432
参赛次数	1
文章发表	4
年　　龄	0
在职情况	学生
学　　校	山师
专　　业

　　自我简介：

TA的其他文章

蓝桥杯2016年第七届真题-碱基（动态规划+map的使用）
浏览：459

（公式+upper_bound())(100%正确）
浏览：551

蓝桥杯2020年第十一届省赛真题-作物杂交
浏览：613

你可能喜欢

（公式+upper_bound())(100%正确）

　　作者: hh198　　　　发表时间：2022-03-31 15:57:11 浏览：551　|　评论：1　

原题链接：蓝桥杯2021年第十二届国赛真题-123

[题目链接](https://www.dotcpp.com/oj/problem2618.html)

这题的主要难度在于求数据规模太大，暴力求解前缀和肯定是会超时的，但是可以明显看出最终问题是需要求解出公式的，所以接下来我们来看如何求解公式
当一个数列{an}最大数为N时,那它后面的数肯定都小于N，个数为n-N，后面的数可以用公式n*(n+1)/2求解，将n-N带入其中即可
所以数列就被分为了两部分，后一部分以求得，我们再来看前半部分形式为：
1
12
123
1234
12345
123456
123....
........
123.......(n-1)
123.......(n-1)n
前半部分可以看作这些所有数相加就可以看作：
1*n+2*(n-1)+3*(n-2)+.....(n-1)*2+n*1
将（n-1)*2看作(n-1)*(n-(n-2))
将n*1看作n*(n-(n-1))

则上述公式化简为：
n*(1+2+...n)-(1*2+2*3+.....+(n-1)*n)
数学基础好的同学就会知道后半部分其实是有这样的公式的
1×2＋2×3＋3×4＋4×5＋…＋n(n＋1)=n(n+1)(n+2)/3

所以最后的公式为n*n*(n+1)/2-(n-1)*n*(n+1)/3

当然不知道也没有关系，还有另一种方法可以算它，我们将n*(n+1)拆成n*n+n
就变成了1*1+2*2+.....(n-1)*(n-1)+1+2+...+(n-1)
而平方数的前n项和公式为：
1*1+2*2+.....+n*n=n*(n+1)*(2n+1)/6
最后化简答案是一样的

再最后说说自己的思路，先打表，打n*(n+1)/2的表，这个不仅能用来算后面半部分的值，还是二分查找在何处分割两部分的依据，打表大小为sqrt(2e12)<2e6

正确代码：
```
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <sstream>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const ll mod=1000000007;
const ll N=2e6+7;
const ll M=2e6;
const double pai=3.14159265358979;
const int maxn2=1e9;
int t;
ll a[N],l,r;
ll getsum2(ll n)
{
    return n*n*(n+1)/2-(n-1)*n*(n+1)/3;
}
ll getsum(ll n)
{
    int i=upper_bound(a+1, a+M+1, n)-a;
    i--;//记得要减1
    return getsum2(i)+a[n-a[i]];
}
int main()
{
    for(int i=1;i<=M;++i)a[i]=a[i-1]+i;
    scanf("%d",&t);
    while (t--) {
        scanf("%lld %lld",&l,&r);
        printf("%lld\n",getsum(r)-getsum(l-1));
    }
    return 0;
}

```

有收获的同学可以点赞支持一下，您的鼓励将是我创作的最大动力！

0.0分

10 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

hh198

真是抱歉输入的时候格式转换出了问题，最后很大乘号“*”没有显示，不过不影响观看，感谢支持

2022-03-31 16:00:39

hh198

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

简单的a+b （C语言代码）

字符串输入输出函数（Java代码）

C二级辅导-计负均正（C++代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

（公式+upper_bound())(100%正确）

评论区

精彩推荐

点我有惊喜！你懂得！

点我有惊喜！你懂得！

简单的a+b （C语言代码）

C语言考试练习题_排列（C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

演讲大赛评分（C语言代码）

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

GC的苦恼（C语言代码）

hh198

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

简单的a+b （C语言代码）

字符串输入输出函数 （Java代码）

C二级辅导-计负均正 （C++代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

（公式+upper_bound())(100%正确）

评论区

精彩推荐

点我有惊喜！你懂得！

点我有惊喜！你懂得！

简单的a+b （C语言代码）

C语言考试练习题_排列 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

演讲大赛评分 （C语言代码）

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

GC的苦恼 （C语言代码）

字符串输入输出函数（Java代码）

C二级辅导-计负均正（C++代码）

　　评论区

C语言考试练习题_排列（C语言代码）

演讲大赛评分（C语言代码）

GC的苦恼（C语言代码）