题目 2618 蓝桥杯2021年第十二届国赛真题-123 满分写法

题目:

思路:

先转换成二维数组

1

1 2

1 2 3

1 2 3 4

…

假设有 n n n 行,那么数组长度 l e n len len 应该等于
l e n = n + n 2 2 len = cfrac{n+n^2}{2} len=2n+n2​
题目给出我们数组长度,逆推公式最大值可找到行数

查找行数函数:

int max_len(int n){
    int l=1,r=n;
    while(l<=r){
        int mid = (l+r)/2;
        if((mid*mid+mid)/2
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    return r+1;
}

给定长度求和分为两块:

S n = S v + S y S_n = S_v+S_y Sn​=Sv​+Sy​
其中 S v S_v Sv​为确定行数减一行总和, y y y 就等于
y = l e n − ( x − 1 ) + ( x − 1 ) 2 2 y=len-cfrac{(x-1)+(x-1)^2}{2} y=len−2(x−1)+(x−1)2​
最后一行就是 1 + 2 + . . . + y 1+2+...+y 1+2+...+y 求和
S y = ( 1 + y ) ∗ y 2 = y + y 2 2 S_y=cfrac{(1+y)*y}{2}=cfrac{y+y^2}{2} Sy​=2(1+y)∗y​=2y+y2​
接下来求 S n S_n Sn​
S n = S n − 1 + S h = S n − 1 + n + n 2 2 S_n=S_{n-1}+S_h=S_{n-1}+cfrac{n+n^2}{2} Sn​=Sn−1​+Sh​=Sn−1​+2n+n2​
S n S_n Sn​等于 S n − 1 S_n-1 Sn​−1加上当前行的和 S h S_h Sh​

所以我们可以预处理 S n S_n Sn​

#include 
using namespace std;
#define ll long long
long long sum[1600010]={0};

ll max_len(ll n){//求行数函数
    ll l=1,r=1414500;// r等于最大行数
    while(l<=r){
        ll mid = (l+r)/2;
        if((mid+mid*mid)/2
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    return r+1;
}

int main(){
    for(long long i=1;i<=1600001;i++){//预处理S_n
        sum[i]=sum[i-1]+(i+i*i)/2;
    }
    
    
    return 0;
}

接下来是求和函数,接收一个整数,为数组的长度

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;//总和
}

最终代码:

#include 
using namespace std;
#define ll long long
long long sum[1600010]={0};

ll max_len(ll n){
    ll l=1,r=1414500;
    while(l<=r){
        ll mid = (l+r)/2;
        if((mid+mid*mid)/2
            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=0;
    S_v=sum[x-1];

    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;
        scanf("%lld %lld",&x,&y);
        printf("%lldn",sum_len(y)- sum_len(x-1));
    }

    return 0;
}

运行结果:

坑点
1.求行数函数的右端点 r 不能等于 n ,会爆longlong,测试用例最大长度为 1e12 ,可以写一个循环把最大行数跑出来,然后让 r 设为最大长度多一点即可