P8762 [蓝桥杯 2021 国 ABC] 123题解
__Shine__
·
·
题解
题目传送门
本题思路
本题要生成一个数列，例如：1,1,2,1,2,3,1,2,3,4,…，所以我们把这个数列看成一个二维数组：
那么我们假设这个二维数组有 n 行，那么数列长度 len 则为：
len = \cfrac{n+n^2}{2}
题目给出我们数组长度,逆推公式最大值可找到行数。
查找行数函数:
int max_len(int n){
int l=1,r=n;
while(l<=r){//二分查找
int mid = (l+r)/2;
if((mid*mid+mid)/2<n){
l=mid+1;
}else{
r=mid-1;
}
}
return r+1;
}
给定长度求和分为两块：
S_n = S_v + S_y
其中 S_v 为确定行数减一行总和，y 就等于 len-\cfrac{(x-1)+(x-1)^2}{2}。
最后一行就是 1+2+...+y 求和。
S_y=\cfrac{(1+y) \times y}{2}=\cfrac{y+y^2}{2}
接下来求 S_n。
S_n=S_{n-1}+S_h=S_{n-1}+\cfrac{n+n^2}{2}
预处理代码：
```cpp
for(long long i=1;i<=1600001;i++)//预处理S_n
sum[i]=sum[i-1]+(i+i*i)/2;
```
接下来是求和函数，参数为数组的长度：
```cpp
ll sum_len(ll len){
ll x=max_len(len);//最大行数
ll y=len-(x-1+(x-1)*(x-1))/2;//最后一行的长度
ll S_y=(y+y*y)/2;//最后一行的和
ll S_v=sum[x-1];//前面n行的和
return S_y+S_v;//总和
}
```
最终代码如下：
```cpp
#include <bits/stdc++.h>
using namespace std;
#define ll long long
long long sum[1600010]={0};
int max_len(int n){
int l=1,r=n;
while(l<=r){//二分查找
int mid = (l+r)/2;
if((mid*mid+mid)/2<n){
l=mid+1;
}else{
r=mid-1;
}
}
return r+1;
}
ll sum_len(ll len){
ll x=max_len(len);//最大行数
ll y=len-(x-1+(x-1)*(x-1))/2;//最后一行的长度
ll S_y=(y+y*y)/2;//最后一行的和
ll S_v=sum[x-1];//前面n行的和
return S_y+S_v;//总和
}
int main(){
//预处理S_n前n行和
for(long long i=1;i<=1600001;i++)
sum[i]=sum[i-1]+(i+i*i)/2;
int N;
scanf("%d",&N);
while(N--){
ll x,y;
cin>>x>>y;
cout<<sum_len(y)- sum_len(x-1)<<endl
}
return 0;
}
```