文章目录

• • 1.数的范围（👍二分）
  • 2.数的三次方根（浮点二分）
  • 3.机器人跳跃问题（二分答案）
  • 4.最少刷题数（二分+前缀和）
  • 5.前缀和
  • 6.子矩阵的和
  • 7.四平方和
  • 8.分巧克力（二分）
  • 9.激光炸弹（二维前缀和）
  • 10.K倍区间（前缀和+同余优化）

1.数的范围（👍二分）

💡方法一：开两个数组分别记录第一个出现的位置和最后一次出现的位置，O(n)就可以处理出来。

public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = (int) (1e5+ 10);static int n = 0,q = 0,ans = 0;static int[] a = new int[N];static int[] pre = new int[N];static int[] back = new int[N];public static void main(String[] args) throws Exception{String nq[] = br.readLine().split(" ");n = Integer.parseInt(nq[0]);q = Integer.parseInt(nq[1]);String[] aa = br.readLine().split(" ");for(int i = 1; i <= n; i++) {a[i] = Integer.parseInt(aa[i - 1]);}Arrays.fill(pre, -1);Arrays.fill(back, -1);for (int i = 1; i <= n; i ++) {if (pre[a[i]] == -1) {pre[a[i]] =  i - 1;}}for (int i = n; i >= 1; i --) {if (back[a[i]] == -1) {back[a[i]] =  i - 1;}}for(int i = 1; i <= q; i++) {int k = Integer.parseInt(br.readLine());System.out.println(pre[k] + " " + back[k]);}}
}

💡方法二：找第一个大于等于k的位置和第一个小于等于k的位置

public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = (int) (1e5+ 10);static int n = 0,q = 0,ans = 0;static int[] a = new int[N];public static void main(String[] args) throws Exception{String nq[] = br.readLine().split(" ");n = Integer.parseInt(nq[0]);q = Integer.parseInt(nq[1]);String[] aa = br.readLine().split(" ");for(int i = 1; i <= n; i++) {a[i] = Integer.parseInt(aa[i - 1]);}for(int i = 1; i <= q; i++) {int k = Integer.parseInt(br.readLine());int l = find_minn(k);int r = find_maxn(k);System.out.println(l + " " + r);}}//找第一个大于等于k的位置private static int find_maxn(int k) {int l = 1,r = n;int res = -1;while (l <= r) {int mid = (l + r) >> 1;if(a[mid] <= k) {res = mid;l = mid + 1;}else {r = mid - 1;}}	return res==-1||a[res]!=k?-1:res-1;}//找第一个小于等于k的位置private static int find_minn(int k) {int l = 1,r = n;int res = -1;while (l <= r) {int mid = (l + r) >> 1;if(a[mid] >= k) {res = mid;r = mid - 1;}else {l = mid + 1;}}return res==-1||a[res]!=k?-1:res-1;}
}

💡方法三：找第一个大于k的位置和最后一个小于k的位置（此方法不推荐，需要判断的情况太多了）

public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = (int) (1e5+ 10);static int n = 0,q = 0,ans = 0;static int[] a = new int[N];public static void main(String[] args) throws Exception{String nq[] = br.readLine().split(" ");n = Integer.parseInt(nq[0]);q = Integer.parseInt(nq[1]);String[] aa = br.readLine().split(" ");for(int i = 1; i <= n; i++) {a[i] = Integer.parseInt(aa[i - 1]);}for(int i = 1; i <= q; i++) {int k = Integer.parseInt(br.readLine());int l = find_minn(k);int r = find_maxn(k);System.out.println(l + " " + r);}}
//	找第一个大于k的位置private static int find_maxn(int k) {int l = 1,r = n;int res = -1;while (l <= r) {int mid = (l + r) >> 1;if(a[mid] > k) {res = mid;r = mid - 1;}else {l = mid + 1;}}	if (a[n] == k) {return n - 1;}return ( (res == -1 && a[n] != k) || (res != -1 && a[res-1] != k) ) ? -1 : res-1-1;}
//	找最后一个小于k的位置private static int find_minn(int k) {int l = 1,r = n;int res = -1;while (l <= r) {int mid = (l + r) >> 1;if(a[mid] < k) {res = mid;l = mid + 1;}else {r = mid - 1;}}if (a[1] == k) {return 1 - 1;}//如果没找到小于k的位置，代表都大于等于k这时候只需要判断第一个是否等于k,或者找到了最后一个小于k的位置，只需要判断他后面是否等于k，因为下标从0开始，所以返回的时候需要-1return ( (res == -1 && a[1] != k) || (res != -1 && a[res+1] != k) ) ? -1 : res;}}

2.数的三次方根（浮点二分）

思路：和整数二分差不多，只不过浮点二分需要注意精度问题，逼近步长需要比较小，（根据经验值，一般设置的精度与题目要求的保留的小数位有关，❗1e-(保留的小数位+2)）

public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static double n = 0;public static void main(String[] args) throws Exception{n = Double.parseDouble(br.readLine());System.out.printf("%.6f",search(n));}private static double search(double n) {double l = -1000, r = 1000;double res = -1;while(r - l >= 1e-8) {double mid = (l + r) / (double)2;if(mid * mid * mid >= n) {r = mid;}else {l = mid;}}return l;}
}

法二：

public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static double n = 0;public static void main(String[] args) throws Exception{n = Double.parseDouble(br.readLine());System.out.printf("%.6f",search(n));}private static double search(double n) {double l = -1000, r = 1000;while(r - l >= 1e-8) {double mid = (l + r) / (double)2;if(mid * mid * mid >= n) {r = mid;}else {l = mid;}}return l;}
}

3.机器人跳跃问题（二分答案）

思路：🔺🔺🔺一般求解最大值，最小值问题，二分使用的条件是：答案具有单调性
二分答案就是对所有可能的答案区间进行折半查找，不断缩小范围，最后得到确定的答案。check()函数一般与二分答案配合使用，check()的时候，我们是在已知答案的情况下去验证此答案是否可行，是假设我们已经知道答案，去验证答案是否正确，以此缩放范围。

此题很明显具有单调性，即能量值越大越好，当能量值大的时候满足答案，但是能量值小的时候不一定满足，但是能量值小的时候满足，能量值大的时候一定满足，具有单调性，我们对能量值进行二分，求满足条件的最小的能量值即可。
需要注意的是在check函数中，当答案大于1e5的时候，肯定是所有可行的，直接返回true即可，❗❗❗否则一直累加1e5可能会溢出

public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = (int) (1e5 + 10);static int[] h = new int[N];static int n = 0, m = 0,q;public static void main(String[] args) throws Exception{n = Integer.parseInt(br.readLine());String[] hh = br.readLine().split(" ");for(int i = 1; i <= n; i++) {h[i] = Integer.parseInt(hh[i - 1]);}int l = 0, r = (int) 1e5;int res = -1;while(l <= r) {int mid = (l + r) >> 1;if(check(mid)) {r = mid - 1;res =mid;}else {l = mid + 1;}}System.out.println(res);}private static boolean check(int mid) {int ans = mid;for(int i = 0; i < n; i++) {if(h[i + 1] > ans) {ans = ans - (h[i + 1] - ans);}else {ans = ans + (ans - h[i + 1]);}if(ans < 0) {return false;}if(ans >= 1e5) return true;}return true;}
}

4.最少刷题数（二分+前缀和）

思路：此题和上面那个题基本类似，只是需要用前缀和预处理一下，本题同样满足单调性，刷题数越多肯定是越好。

5.前缀和

典型的前缀和模板

public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = (int) (1e5 + 10);static int[] a= new int[N];static int[] sum= new int[N];static int n = 0, m = 0;public static void main(String[] args) throws Exception{String[] nm = br.readLine().split(" ");n = Integer.parseInt(nm[0]);m = Integer.parseInt(nm[1]);String[] aa = br.readLine().split(" ");for(int i = 1; i <= n; i++) {a[i] = Integer.parseInt(aa[i - 1]);}for(int i = 1; i <= n; i++) {sum[i] = sum[i - 1] + a[i];}for(int i = 1; i <= m; i++) {String[] lr = br.readLine().split(" ");int l = Integer.parseInt(lr[0]);int r = Integer.parseInt(lr[1]);System.out.println(sum[r] - sum[l - 1]);}}
}

6.子矩阵的和

典型二位前缀和

public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = (int) (1e3 + 10);static int[][] a= new int[N][N];static long[][] sum= new long[N][N];static int n = 0, m = 0,q;public static void main(String[] args) throws Exception{String[] nmq = br.readLine().split(" ");n = Integer.parseInt(nmq[0]);m = Integer.parseInt(nmq[1]);q = Integer.parseInt(nmq[2]);for(int i = 1; i <= n; i++) {String[] aa = br.readLine().split(" ");for(int j = 1; j <= m; j++) {a[i][j] = Integer.parseInt(aa[j - 1]);}}for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {sum[i][j] = sum[i -1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + (long)a[i][j];}}for(int i = 1; i <= q; i++) {String[] xy = br.readLine().split(" ");int x1 = Integer.parseInt(xy[0]);int y1 = Integer.parseInt(xy[1]);int x2 = Integer.parseInt(xy[2]);int y2 = Integer.parseInt(xy[3]);long ans = sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1];System.out.println(ans);}}
}

7.四平方和

法1：暴力枚举（时间复杂度：O(n3)显然过不了）

public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = (int) (1e5 + 10);static int[] h = new int[N];static int n = 0, m = 0,q;public static void main(String[] args) throws Exception{n = Integer.parseInt(br.readLine());int num = (int) (Math.sqrt(n) + 1);for(int a = 0; a <= num; a++) {for(int b = a; b <= num; b++) {for(int c = b; c <= num; c++) {int d = n - (a*a + b*b + c*c);if (d >= 0 &&(int)Math.sqrt(d)*(int)Math.sqrt(d) == d) {System.out.println(a + " " + b + " " + c + " " + (int)Math.sqrt(d));return;}}}}}
}

法2：

#include 
using namespace std;
int n,x;
int a[5100000];
int tot;
bool exist(int p) {int l = 1, r= tot, res = -1;while (l <= r) {int mid = l + r >> 1;if (a[mid] <= p) {res = mid;l = mid + 1;} else {r = mid - 1;}}return (res == -1 || a[res] != p) ? false : true;
}void solve(int p) {for (int i = 0; i <= x; i ++) {for (int j = i; j <= x; j ++) {if (i * i + j * j == p) {cout << i << ' ' << j ;return ;}}}
}int main()
{cin >> n;x = sqrt(n);for (int i = 0; i <= x; i ++) {for (int j = i; j <= x; j ++) {a[++tot] = i*i+j*j;}}sort(a + 1, a + 1 + tot);for (int i = 0; i <= x; i ++) {for (int j = i; j <= x; j ++) {if (exist(n-i*i-j*j)) {cout << i << ' ' << j << ' ';solve(n-i*i-j*j);return 0;}}}}

8.分巧克力（二分）

💡💡💡思路：
显然此题可以采用二分求解，二分蛋糕的边长x，如果x是可行解，则所有< x 是都是可行解；如果x 不是可行解，则所有>x的肯定都是不行的，符合使用二分的条件。
时间复杂度：(nlogn)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = (int) (1e5 + 10);static int[] h = new int[N];static int[] w = new int[N];static int n = 0, m = 0,k = 0;public static void main(String[] args) throws Exception{String []nk = br.readLine().split(" ");n = Integer.parseInt(nk[0]);k = Integer.parseInt(nk[1]);for(int i = 1; i <= n; i++) {String[] hw = br.readLine().split(" ");h[i] = Integer.parseInt(hw[0]);w[i] = Integer.parseInt(hw[1]);}int l = 1, r = (int) 1e5, res = -1;while(l <= r) {int mid = (l + r) >> 1;if(check(mid)) {res = mid;l = mid + 1;}else {r = mid - 1;}}System.out.println(res);}private static boolean check(int x) {int num = 0;for(int i = 1; i <= n; i++) {num = num + (w[i] / x) * (h[i] / x);}if(num >= k) {return true;}else {return false;}}
}

9.激光炸弹（二维前缀和）

思路：典型的二维前缀和模板题，需要注意的是，本题下标是从0开始的，为了处理方便，我们通常可以将所有下标都加1，此时比较好处理。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = (int) (1e5 + 10);static long[][] sum = new long[5010][5010];static int[][] a = new int[5010][5010];static int n = 0, m = 0,r = 0;public static void main(String[] args) throws Exception{String[] nr = br.readLine().split(" ");n = Integer.parseInt(nr[0]);r = Integer.parseInt(nr[1]);for(int i = 1; i <= n; i++) {String[] xyw = br.readLine().split(" ");int x = Integer.parseInt(xyw[0]);int y = Integer.parseInt(xyw[1]);int w = Integer.parseInt(xyw[2]);a[++x][++y] += w;}for(int i = 1; i <= 5001; i++) {for(int j = 1; j <= 5001; j++) {sum[i][j] = sum[i - 1][j] +sum[i][j - 1] - sum[i - 1][j - 1] + (long)a[i][j];}}long maxn = 0;for(int i = 1; i <= 5001; i++) {for(int j = 1; j <= 5001; j++) {long tol = sum[i][j] - sum[Math.max(i - r,0)][j] - sum[i][Math.max(j - r,0)] + sum[Math.max(i - r,0)][Math.max(j - r,0)];maxn = Math.max(maxn,tol);}}System.out.println(maxn);}
}

10.K倍区间（前缀和+同余优化）

方法1：直接求出前缀和，两层for循环枚举分割点的位置（很显然会TLE）

public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = (int) (1e5 + 10);static long[] sum = new long[N];static long[] a = new long[N];static int n = 0, m = 0,k = 0,ans = 0;public static void main(String[] args) throws Exception{String[] nk = br.readLine().split(" ");n = Integer.parseInt(nk[0]);k = Integer.parseInt(nk[1]);for(int i = 1; i <= n; i++) {a[i] = Long.parseLong(br.readLine());}for(int i = 1; i <= n; i++) {sum[i] = sum[i - 1] + a[i];}for(int i = 1; i <= n; i++) {for(int j = i; j <= n; j++) {if((sum[j] - sum[i - 1])%k == 0) {ans++;}}}out.println(ans);out.flush();}
}

💡💡💡正解:前缀和+数学同余优化

很显然肯定是要用前缀和数组，(s[r]-s[l-1])%k=0.可以转换位s[r]%k=s[l-1]%k
我们使用cnt[i]数组记录对k取模为i的前缀和个数
从前往后遍历，每次记录取模之后的数，看看前面存在几个与其取模之后数字一样的前缀和，然后讲cnt[s[i]%k]++
需要注意的是，cnt[0]需要特殊处理一下，为1，因为一个数也可以构成k倍区间，比如一个数取模为0，那么他自己本身便是一种情况。

AC代码：

public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = (int) (1e5 + 10);static long[] sum = new long[N];static long[] a = new long[N];static long[] cnt = new long[N];static int n = 0, m = 0,k = 0;static long ans = 0; //注意数据范围public static void main(String[] args) throws Exception{String[] nk = br.readLine().split(" ");n = Integer.parseInt(nk[0]);k = Integer.parseInt(nk[1]);for(int i = 1; i <= n; i++) {a[i] = Long.parseLong(br.readLine());}for(int i = 1; i <= n; i++) {sum[i] = sum[i - 1] + a[i];}cnt[0] = 1;for(int i = 1; i <= n; i++) {ans += cnt[(int) (sum[i]%k)];cnt[(int) (sum[i]%k)]++;}System.out.println(ans);}
}