这题其实就是求前缀和要找出加起来最大的那一段序列，序列长度为k-1，因为要与实际一致需要特判当k>=n的情况，因为这种情况不需要消耗时间，但是不特判就会输出全部加起来的值 import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner scanner=new Scanner(System.in); int n=scanner.nextInt()-1; int k=scanner.nextInt(...

这是一道二维差分题，经典表现就是题目要求对一个二维矩阵的子矩阵进行多次累加操作，数组大小设置为d[n+2][m+2]，加2是方便后面操作，防止数组越界我们先定义一个差分数组，然后定义差分数组的插入函数，当要修改里面的值时，比如赋初值、后面的加k都会通过这个函数来操作当对x1,y1 至x2,y2这个子矩阵中加k时，我们只需要按照我下面写的操作去操作，可以这样理解，当d[i][j]加k以后要去掉不该加的部分，这个部分包括右边和下面，但是减去两个值后，会导致多减了一份右下角，需要额外加上当输入初值时，我们就把它传进插入函数，此时的左上角坐标和右下角坐标都为i,j最后我们需要还原到原数组，这里就不得不...

直接使用二维前缀和模板来做这里有一点要注意的是，在二维数组中，往下是x增加的方向，往右是y增加的方向，与数学中的不太一样 import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner scanner=new Scanner(System.in); int n=scanner.nextInt(); int m=scanner.nextInt(); int q=scanner.nextInt(); lo...

这个题想让我们求一个二维数组的和，由于数据量大，不好直接遍历求，我们采用二维前缀和也就是把每一行的单独作为一个一维数组，求出这个一维数组对应的前缀和数组，然后扩展到二维数组后面直接通过前缀和的套路去求解即可 import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner scanner=new Scanner(System.in); int n=scanner.nextInt(); int m=sca...

如果是数据量小的话可以直接用for循环，在a与b之间都++，但是数据量大不行我们采用差分数组c[a]++,c[b+1]--;最后统计每一棵数的次数并求最大值 import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner scanner=new Scanner(System.in); int n=scanner.nextInt(); int c[]=new int[1000005]; while(n-...

这个题就是基于前缀和的通过前缀和快速求出这两段序列的和，然后相乘与最小值判断，以此求出最小值 import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner scanner=new Scanner(System.in); int n=scanner.nextInt(); long a[]=new long[n]; long sum[]=new long[n+1]; for (int i = 0; i ...

直接套前面的前缀和模板即可 import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner scanner=new Scanner(System.in); String string=scanner.next(); char c[]=string.toCharArray(); int sum[]=new int[c.length+1]; int q=scanner.nextInt(); for (in...

这一题如果直接用for循环暴力做有一个测试点会 超时建议使用差分数组来做我们需要创建一个数组用来表示原数组每一个元素与其前一个元素之间的关系这个数组的长度得是n+1，这样第l个数就是索引l了当改变l到r范围的数，c[l]+=k，c[r+1]-=k，这里需要注意的是，要判断r+1还在不在数组中，如果不在就不用执行这一步最后我们就得到了最终每相邻两个元素之间的关系我们可以从0开始，累加，输出即可 import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-ge...

这题直接使用for循环累加会超时我们应当使用前缀和数组来做当输入数据的时候，我们就可以把数组预处理好这里的sum数组长度应当为n+1，因为要保留sum[0]为前0个元素，也就是0最后输出sum[r]-sum[l-1]即可 import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner scanner=new Scanner(System.in); int n=scanner.nextInt(); in...

这题就是在考察Ax+By=C，要想有整数解，C一定得是gcd(x,y)的倍数这个知识点搞明白这个就简单了 import java.math.BigInteger; import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub // Ax+By=C，要想有整数解，C一定得是gcd(x,y)的倍数 Scanner scanner=new Scanner(System.in); int t=scanner.nextInt...

要求最大的lcm，根据公式,lcm=a*b/gcd(a,b)那么我们得想办法让a*b尽可能大，因为b=n-a，所以根据一元二次方程最大值为a=n/2时gcd最小为1，只有当a与b除了1以外没有任何公因数时出现所以我们就可以从n/2开始遍历，每一次都求gcd，如果gcd=1，那么就是最大值这里需要注意的是i>=1，而不是i>=2，因为有的值，只有当i==1时，才能取公共值 import java.math.BigInteger; import java.util.Scanner; public class Main { public static void main(String[]...

这题其实就是要我们统计每一次除掉的那个因数所对应的更大的那个因数之和如果n本身就是质数，那么最后只需要加1，而不是加n，因为要保证每次摆下的行数大于1 import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner scanner=new Scanner(System.in); long n=scanner.nextLong(); long t=n; long count=t; for (int i ...

原来还可以使用while直接不停除，把相同因数全部除掉这样除不需要考虑因数是不是质数，因为如果不是质数，会直接被这个数的因数先除掉循环结束以后要判断现在的temp是不是1，如果不是一，那就说明它是质数，那么count++ import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner scanner=new Scanner(System.in); int t=scanner.nextInt(); wh...

这题由于数字太大，只能用BigInteger正好里面自带了gcd然后就可以用一个for循环做出来，不熟悉相关语法的得注意一下BIgInteger的for循环该怎么写还有就是，如果gcd已经等于1了，那么就不用再求了，可以直接退出循环了 import java.math.BigInteger; import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner scanner=new Scanner(Sys...