[蓝桥杯 2021 国 ABC] 123(java)——前缀和,思维

admin2024-05-15  0

目录

题目

解析

代码


这么久了,我终于能不看别人代码完整写出来了,呜呜呜。虽然过程也是很曲折。

题目

[蓝桥杯 2021 国 ABC] 123(java)——前缀和,思维,第1张

解析

这个题,找其中数列的规律,1,1,2,1,2,3,1,2,3,4,...,因此我们把拆分成行列,如下

        在这种格式下,我们可以发现每行的行数就是这行的最后一个数的值,且这行的和等于整个数列的值的个数。(例如:第3行最后一个值为3,第三行的和为6,对应从第一行到第三行的值的个数,也为6)

        因此,我们求解[l,r] 之间的值,我们可以找到 l 和 r 对应的行数,假设为 [蓝桥杯 2021 国 ABC] 123(java)——前缀和,思维,l\_{row},第2张[蓝桥杯 2021 国 ABC] 123(java)——前缀和,思维,r\_{row},第3张 ,我们只需要加上 从 [蓝桥杯 2021 国 ABC] 123(java)——前缀和,思维,l\_{row},第2张[蓝桥杯 2021 国 ABC] 123(java)——前缀和,思维,r\_{row},第3张 每行的值,在处理一下  [蓝桥杯 2021 国 ABC] 123(java)——前缀和,思维,l\_{row},第2张[蓝桥杯 2021 国 ABC] 123(java)——前缀和,思维,r\_{row},第3张 行端点的多的或者少的值,即可求出。

        因此,我们可以预处理每行的和,用 a[ ] 存储起来,以及前 i 行的和,用 s[ ] 存储起来

        对于行数的查找,我们可以使用二分,因为 第 i 行的和等于整个数列的值的个数,因此我们使用二分,每次判断 l 与 a[mid] 的大小,找到 l 对应的行 [蓝桥杯 2021 国 ABC] 123(java)——前缀和,思维,l\_{row},第2张 以及 r 对应的行 [蓝桥杯 2021 国 ABC] 123(java)——前缀和,思维,r\_{row},第3张利用 [蓝桥杯 2021 国 ABC] 123(java)——前缀和,思维,s[r\_row]-s[l\_row],第10张 可以求出行之间的和.

        然后再对第 [蓝桥杯 2021 国 ABC] 123(java)——前缀和,思维,l\_{row},第2张 或者 [蓝桥杯 2021 国 ABC] 123(java)——前缀和,思维,l\_{row}+1,第12张 行没计算的值进行处理(这里要对 [蓝桥杯 2021 国 ABC] 123(java)——前缀和,思维,l\_{row}+1,第12张 进行处理的原因,我写的代码中二分找到是 ,比如,l 在第 i 行,但是如果 l 不是该行的最后一个数,取 i-1 行,即二分返回 i-1,所以需要解决 [蓝桥杯 2021 国 ABC] 123(java)——前缀和,思维,l\_{row},第2张+1 的值)。[蓝桥杯 2021 国 ABC] 123(java)——前缀和,思维,r\_{row},第3张 同理。

对于l:

  • [蓝桥杯 2021 国 ABC] 123(java)——前缀和,思维,l != a[l\_row],第16张[蓝桥杯 2021 国 ABC] 123(java)——前缀和,思维,sum+=a[l-a[l\_row]-1],第17张。l 不是  [蓝桥杯 2021 国 ABC] 123(java)——前缀和,思维,l\_{row},第2张 的最后一个数,即 l 是 [蓝桥杯 2021 国 ABC] 123(java)——前缀和,思维,l\_{row}+1,第12张 行的数。(其中,l 也不能是 [蓝桥杯 2021 国 ABC] 123(java)——前缀和,思维,l\_{row}+1,第12张 的第一个数)
  • [蓝桥杯 2021 国 ABC] 123(java)——前缀和,思维,l == a[l\_row],第21张[蓝桥杯 2021 国 ABC] 123(java)——前缀和,思维,sum += l\_row,第22张 ,加上 l 位置上的值。

r同理 

      (这部分自己动手画一下即可理解)

代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class P8762 {
    static int N = 1500000; //因为l,r的范围是10^12,当行数为1500000,数列总的个数可以超过10^12
    static int t;
    static long[] a = new long[N]; // 存储每行的和
    static long[] s = new long[N]; // 存储前i行的和
    public static void main(String[] args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        t = Integer.parseInt(in.readLine());
        // 预处理 a[] 和 s[]
        for(int i=1;i<N;i++){
            a[i] += a[i-1]+i;
            s[i] += s[i-1]+a[i];
        }

        while (t-->0){
            String[] str = in.readLine().split(" ");
            long l = Long.parseLong(str[0]);
            long r = Long.parseLong(str[1]);
            // 找l和r对应的行
            int l_down = find(l);
            int r_down = find(r);
            // 利用s[] 计算两个行之间的值
            long sum = s[r_down] - s[l_down];
            // 如果l对应的是l_down行的最后一个,直接加上位于l位置的值,否则,就要减l_down+1行多加了的值
            if(l==a[l_down]) sum += l_down;
            else if(l-a[l_down]>1) sum -= a[(int) (l-a[l_down]-1)];
            // 如果r对应的不是r_down的最后一个,就要加上r_down+1行未加上的值;否则,不用管,已经计算了
            if(r!=a[r_down]) sum += a[(int) (r-a[r_down])];
            System.out.println(sum);
        }
    }
    // 二分找对应的行
    public static int find(long x){
        int l = 1,r = N;
        while (l<r){
            int mid = (l+r+1)/2;
            if(a[mid]<=x) l = mid;
            else r = mid-1;
        }
        return l;
    }
}
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!