网站描述在关键字前可以吗,营销网站的设计与实现,wordpress免备案cdn,湖州网站设计公司的别名是目录
题目
解析
代码 这么久了#xff0c;我终于能不看别人代码完整写出来了#xff0c;呜呜呜。虽然过程也是很曲折。
题目 解析
这个题#xff0c;找其中数列的规律#xff0c;1,1,2,1,2,3,1,2,3,4#xff0c;...#xff0c;因此我们把拆分成行列#xff0c;如下…目录
题目
解析
代码 这么久了我终于能不看别人代码完整写出来了呜呜呜。虽然过程也是很曲折。
题目 解析
这个题找其中数列的规律1,1,2,1,2,3,1,2,3,4...因此我们把拆分成行列如下 1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 .... 在这种格式下我们可以发现每行的行数就是这行的最后一个数的值且这行的和等于整个数列的值的个数。例如第3行最后一个值为3第三行的和为6对应从第一行到第三行的值的个数也为6 因此我们求解[l,r] 之间的值我们可以找到 l 和 r 对应的行数假设为 和 我们只需要加上 从 到 每行的值在处理一下 和 行端点的多的或者少的值即可求出。 因此我们可以预处理每行的和用 a[ ] 存储起来以及前 i 行的和用 s[ ] 存储起来 。 对于行数的查找我们可以使用二分因为 第 i 行的和等于整个数列的值的个数因此我们使用二分每次判断 l 与 a[mid] 的大小找到 l 对应的行 以及 r 对应的行 。利用 可以求出行之间的和. 然后再对第 或者 行没计算的值进行处理这里要对 进行处理的原因我写的代码中二分找到是 比如l 在第 i 行但是如果 l 不是该行的最后一个数取 i-1 行即二分返回 i-1所以需要解决 1 的值。 同理。
对于l 。l 不是 的最后一个数即 l 是 行的数。其中l 也不能是 的第一个数 加上 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^12static 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 i1;iN;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_down1行多加了的值if(la[l_down]) sum l_down;else if(l-a[l_down]1) sum - a[(int) (l-a[l_down]-1)];// 如果r对应的不是r_down的最后一个就要加上r_down1行未加上的值否则不用管已经计算了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 (lr){int mid (lr1)/2;if(a[mid]x) l mid;else r mid-1;}return l;}
}
