及客户和

用户名：45374687

访问量：3340

签　名：

等　　级
排　　名	611
经　　验	4033
参赛次数	8
文章发表	11
年　　龄	19
在职情况	学生
学　　校	江苏某四非
专　　业	计算机科学与技术

　　自我简介：

TA的其他文章

1815: 蓝桥杯2014年第五届真题-排列序数
浏览：130

1433 危险系数较为省空间的解题方法
浏览：107

1643: 蓝桥杯算法训练VIP-最大体积完全背包问题变种
浏览：269

你可能喜欢

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

蓝桥杯第十二届国赛真题-123 二分+公式

　　作者: 及客户和　　　　发表时间：2021-08-23 14:46:14 浏览：1418　|　评论：2　

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

解题思路:
直接暴力枚举求解，无论是时间还是空间上都不允许。但本题涉及到等差数列，因此考虑**等差数列求和公式**求解。
按照如下思路：
1.分别求出l和r对应哪一段（记为pl,pr）；
2.求出分别是那一段的第几个(记为no_l,no_r)；
3.求出pl段从no_l到末尾（即pl）的和+pr段1到no_r的和，记为sum1；
4.求出中间的和，记为sum2；
5.求出sum1+sum2即为答案
注意pl==pr的情况要单独处理。
由于每段开头对应的编号是单调递增的，因此可以采用二分查找降低复杂度。经测试，第1e12对应1414214段，所以假设最大为1414215段即可。
最终实现代码如下：
```cpp
#include <cstdio>
#define long  long long
using namespace std;
inline long calc(long st,long end) {
    long n=end-st+1;
    return ((st+end)*n)/2;
}

inline int part(long i) {
    int p=1;
    int l=1,r=1414215;
    while(l<r) {  //二分查找
    	p=l+(r-l)/2;  //假设第p段
		long st=calc(1,p-1)+1; //计算第p段第一项
		if(st>i) {  //如果i于st，则说明答案在右半段
			r=p;
		}
		else {
			l=p+1;
		}
	}
    return l-1;
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--) {
        long l,r,res=0;
        scanf("%I64d%I64d",&l,&r);
        int par_l=part(l),par_r=part(r);  //计算二者是在哪段
        //printf("%d %d\n",par_l,par_r);
        for(int i=par_l+1; i<par_r; i++) {
            res+=calc(1,i);
        }
        long left=l-calc(1,par_l-1),right=r-calc(1,par_r-1);  //单独处理“左边距”与“右边距”
        if(par_l!=par_r) {
            res+=calc(left,par_l)+calc(1,right);
        }
        else {
        	res+=calc(left,right);
		}
        printf("%I64d\n",res);
    }
    return 0;
}
```
然而以上代码仅能通过70%。可以进一步利用
$$\sum_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}{6}$$
导出公式一次性计算出1~l，1~r-1的和然后再相减。

> 最终导出的公式为
sum=$$\frac{n^3+3n^2+2n}{6}$$

0.0分

9 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

　　评论区

BrianChen

我提交了这个代码，WA 编译错误

2022-03-20 13:21:46

ewketr

如何不用高精度处理这个立方和的求值？

2022-03-01 17:40:31

及客户和

TA的其他文章

你可能喜欢

C二级辅导-温度转换（C++代码）

校门外的树（C++代码）

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

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

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

蓝桥杯第十二届国赛真题-123 二分+公式

评论区

精彩推荐

蓝桥杯历届试题-九宫重排（C++代码）

求圆的面积（C语言代码）

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

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

三角形（C++代码）递归（存在大量重复计算，容易出现时间超限）

母牛的故事（C语言代码）

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

大家好，我是验题君

理财计划（C语言代码）

JAM计数法（C语言代码）

及客户和

TA的其他文章

你可能喜欢

C二级辅导-温度转换 （C++代码）

校门外的树 （C++代码）

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

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

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

蓝桥杯第十二届国赛真题-123 二分+公式

评论区

精彩推荐

蓝桥杯历届试题-九宫重排 （C++代码）

求圆的面积 （C语言代码）

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

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

三角形 （C++代码）递归（存在大量重复计算，容易出现时间超限）

母牛的故事 （C语言代码）

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

大家好，我是验题君

理财计划 （C语言代码）

JAM计数法 （C语言代码）

C二级辅导-温度转换（C++代码）

校门外的树（C++代码）

　　评论区

蓝桥杯历届试题-九宫重排（C++代码）

求圆的面积（C语言代码）

三角形（C++代码）递归（存在大量重复计算，容易出现时间超限）

母牛的故事（C语言代码）

理财计划（C语言代码）

JAM计数法（C语言代码）