及客户和

用户名：45374687

访问量：3665

签　名：

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

　　自我简介：

TA的其他文章

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

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

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

你可能喜欢

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

　　作者: 及客户和　　　　发表时间：2021-08-23 14:46:14 浏览：1505　|　评论：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语言程序设计教程（第三版）课后习题7.1 （C语言代码）

Hello, world! （Java代码）

矩形面积交（C语言代码）

简单编码（C++代码）

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

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

评论区

精彩推荐

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

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

矩阵加法（C语言代码）

1035 题解

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

【计算直线的交点数】（C语言代码）

C语言训练-列出最简真分数序列* （C语言代码）

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

明明的随机数（C语言代码）

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

及客户和

TA的其他文章

你可能喜欢

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

Hello, world! （Java代码）

矩形面积交 （C语言代码）

简单编码 （C++代码）

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

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

评论区

精彩推荐

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

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

矩阵加法 （C语言代码）

1035 题解

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

【计算直线的交点数】 （C语言代码）

C语言训练-列出最简真分数序列* （C语言代码）

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

明明的随机数 （C语言代码）

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

矩形面积交（C语言代码）

简单编码（C++代码）

　　评论区

矩阵加法（C语言代码）

【计算直线的交点数】（C语言代码）

明明的随机数（C语言代码）

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