Loading... <a name="gFGCu"></a> ## 排序 <a name="BwJpO"></a> ### 快速排序 模板： ```java public static void quickSort(int[] q, int l, int r) { if (l >= r) return; int x = q[l+r>>1]; //Define positions of two pointers int i = l - 1; int j = r + 1; while (i < j) { do i++; while (q[i] < x); do j--; while (q[j] > x); //do Swap if (i < j) { int temp = q[i]; q[i] = q[j]; q[j] = temp; } } quickSort(q, l, j); quickSort(q, j + 1, r); } } ``` 边界定义： 1. 进行边界分析是为了避免分治时出现被分为0和n的情况，造成无限分治内存超限问题。 2. 若以j为分界点，对于quick_sort(q, l, j), quick_sort(q, j + 1, r)，j有可能取l~r的任何一个值，若j取l，则quick_sort(q, l + 1, r)执行时会产生分割，不会出现0和n的情况；若j取r，则quick_sort(q, l, r)执行时会分割为n，会导致无限分治。本条结论：若在递归分治前保持j = r，那么就会出现无限分治的情况。**所以只要在进入分治前不要让j取到r就可以了。** 3. 那什么时候会取到r呢？初始化完毕时，j的值为r + 1，当执行过一次do j--; while(q[j] > x)后，j变为r，并且恰好在此之后j都不会发生改变，即do j--; while(q[j] > x)只会执行一次，如果保持j = r不变的话，那么i会在此之前一直自增到i = r，此时j = r; i = r不满足i < j循环结束，此时，整个while(i < j) {}循环只进行了1轮，分治，从而导致分治出了0和n两个情况。**本条结论：若要在递归分治前保持j = r，那么while(i < j) {}只能执行一次** 4. 现在把焦点转移到x的取值上，第3点说到，若出现无限分治问题，i会一直自增到i = r，若出现这种情况，那么x的取值一定是q[r]，因为如果x的值不为q[r]，那么一定会在x处存在q[i] == x，而q[i] == x会导致i自增暂时停止，那么就会往下执行，执行do j--;，判断后进入第二轮while(i < j) {}循环，进入第二轮循环会使j自减至少两次，而他的初值为r + 1，也就是说，j的值不会一直保持在j = r上，也就不会导致无限分治。**本条结论：若x的取值不为q[r]，那么while(i < j) {}会至少执行两次，因此在进行递归分治前，j的值是一定小于r的。** 5. l + r >> 1的值一定是小于r的，不会取到r，而l + r + 1 >> 1的值一定是大于l的，不会取到l 所以综合2、3、4、5的结论就得出了若以j为分界点，x取q[l + r >> 1]，此时不会出现无限分治的情况；若以i为分界点，x取q[l + r + 1 >> 1]，此时不会出现无限分治的情况 <a name="g2Ggi"></a> ### 归并排序 模板代码： ```java // 归并排序 private static void merge_sort(int[] arr, int l, int r) { // 递归结束条件 if (l >= r) return; // 以下都为逻辑部分 int mid = l + ((r - l) >> 1); merge_sort(arr, l, mid); merge_sort(arr, mid + 1, r); int[] tmp = new int[r - l + 1]; // 临时数组, 用于临时存储 [l,r]区间内排好序的数据 int i = l, j = mid + 1, k = 0; // 两个指针 // 进行归并 while (i <= mid && j <= r) { if (arr[i] <= arr[j]) tmp[k++] = arr[i++]; else tmp[k++] = arr[j++]; } while (i <= mid) tmp[k++] = arr[i++]; while (j <= r) tmp[k++] = arr[j++]; // 进行赋值 for (i = l, j = 0; i <= r; i++, j++) arr[i] = tmp[j]; } ``` <a name="PI5ue"></a> ## 查找 <a name="Q5DpF"></a> ### 二分查找 两个模板：一个得到左边最后一个， 一个得到右边第一个：<br />**选取标准：根据 check(mid)来判断 r和 l的取值范围。根据取值范围选择 mid是否有 + 1操作**<br />**mid归于左边, r = mid, mid选择 不 +1。mid归于右边, l = mid, mid选择 +1**<br />模板一： ```java // 区间[l, r]被划分成 [l, mid] 和 [mid+1, r]时使用 int bsearch_1(int l, int r) { while (l < r) { int mid = l + r >> 1; if (check[mid]) // check() 判断 mid是否满足性质 r = mid; else l = mid + 1; } return l; } ``` 模板二： ```java // 区间[l, r]被划分成 [l, mid-1] 和 [mid, r]时使用 int bsearch_2(int l, int r) { while (l < r) { int mid = l + r + 1 >> 2; // 注意 if (check[mid]) // check() 判断 mid是否满足性质 l = mid; else r = mid - 1; } return l; } ``` <a name="nbe4F"></a> ### 浮点数二分 ```java double bsearch(double l, double r) { const double eps = 1e-6; // eps 表示精度，取决于题目对精度的要求, 一般比所求精度高 2 while (r - l > eps) { double mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid; } return l; } ``` <a name="nET2t"></a> ## 高精度计算 <a name="bGSDR"></a> ### 高精度加法 ```java import java.text.DecimalFormat; import java.util.Scanner; import java.util.ArrayList; import java.util.List; public class Main{ static final int c=100009; public static void main(String [] args){ Scanner sc=new Scanner(System.in); String a=sc.next(); String b=sc.next(); List<Integer> res=add(a,b); for(int i=res.size()-1;i>=0;i--) System.out.print(res.get(i)); } public static List<Integer> add(String a,String b){ int i=a.length()-1; int j=b.length()-1; List<Integer> temp=new ArrayList<>(); int t=0; for(;i>=0||j>=0;i--,j--){ t+=(i>=0?a.charAt(i)-'0':0)+(j>=0?b.charAt(j)-'0':0); temp.add(t%10); t=t/10; } if(t>0) temp.add(t); return temp; } } ``` <a name="pG5Fd"></a> ### 高精度减法 涉及符号问题。 ```java import java.util.*; public class Main{ static int N=100010; static int[] c=new int[N];//0下标表示个位，这样好进位 public static void main(String[] args){ Scanner sc=new Scanner(System.in); String a=sc.next(); String b=sc.next(); System.out.println(minus(a,b)); } static String minus(String a,String b){ if(a.length() < b.length() || a.length() == b.length() && a.compareTo(b) < 0){ return "-"+minus(b,a); } int k=0,n=a.length(),m=b.length(),t=0; for(int i=n-1,j=m-1;i>=0;i--){ t=a.charAt(i)-'0'-t; if(j>=0){ t-=b.charAt(j--)-'0'; } c[k++]=(t+10)%10; if(t<0){ t=1; }else{ t=0; } } while(k>0 && c[k]==0){//去掉前导0 k--; } StringBuilder sb=new StringBuilder(); for(int i=k;i>=0;i--){ sb.append((char)(c[i]+'0')); } return sb.toString(); } } ``` <a name="VsfOk"></a> ### 高精度乘法 乘法的思路<br /> 数组A[]: 1 2 3 4 5<br /> 数b 25<br /> 模拟过程<br /> b * A[i] 25 * 5 + 4 * 25 + 3 * 25 + 2 * 25 + 1 * 25<br /> 初始化进位t = 0<br /> 计算乘法t += A[i] * b 其中A[i]为数组中的倒数第i个数, b为数, t为进位，同时临时用来存储乘法的结果<br /> 计算结果值 t % 10 <br /> 计算进位值，用于下次计算 t = t / 10 ```java import java.util.Scanner; public class Main{ public static void main(String[] args){ String a; int b; Scanner sc = new Scanner(System.in); a = sc.next(); b = sc.nextInt(); char[] A = new char[a.length()]; for(int i = a.length() - 1; i >= 0; i --) A[a.length() - 1 - i] = a.charAt(i); String s = mul(A, b); System.out.println(s); } public static String mul(char[] A, int b){ int t = 0; StringBuffer sb = new StringBuffer(); for(int i = 0; i < A.length || t != 0; i++){ if(i < A.length) t += (A[i] - '0') * b; sb.append(t % 10); t /= 10; } String s = sb.reverse().toString(); int i = 0; for(; i < A.length - 1; i ++) { if(s.charAt(i) != '0') break; } return s.substring(i, s.length()); } } ``` <a name="GPG5I"></a> ### 高精度除法 除法的思路<br /> 数组A[]: 1 2 6<br /> 数b 25<br /> 模拟过程<br /> 初始化余数r = 0<br /> ((r = 0) * 10 + (A[0] = 1)) / 25 = 0 ... r = 1<br /> ((r = 1) * 10 + (A[1] = 2)) / 25 = 0 ... r = 12<br /> ((r = 12) * 10 + (A[2] = 2)) / 25 = 5 ... r = 1<br /> A遍历完，得到商和余数 初始化余数r = 0<br /> 计算乘法r = r * 10 + A[i] 其中A[i]为数组中的第i个数, b为数, r用来存储当前的结果<br /> 计算结果值 r / 10 <br /> 计算余数，用于下次计算 r = r / 10 ```java import java.util.Scanner; public class Main{ static int r; public static void main(String[] args){ Scanner sc = new Scanner(System.in); String a = sc.next(); int b = sc.nextInt(); char[] A = new char[a.length()]; for(int i = a.length() - 1; i >= 0; i --) A[a.length() - 1 - i] = a.charAt(i); String res = div(A, b); System.out.println(res); System.out.println(r); } public static String div(char[] A, int b){ StringBuffer sb = new StringBuffer(); r = 0; for(int i = A.length - 1; i >= 0; i --){ r = r * 10 + A[i] - '0'; sb.append(r / b); r %= b; } String s = sb.toString(); int i = 0; for(; i < s.length()- 1; i++){ if(s.charAt(i) != '0') break; } return s.substring(i, s.length()); } } ``` <a name="j0nJw"></a> ## 前缀和 **原数组: a[1], a[2], a[3], a[4], a[5], …, a[n]**<br />**前缀和 Si为数组的前 i项和**<br />**前缀和: S[i] = a[1] + a[2] + a[3] + … + a[i]**<br />**注意: 前缀和的下标一定要从 1开始, 避免进行下标的转换：**s[0] = 0 s[1] = a[1] s[2] = a[1] + a[2]<br />作用：快速求出元素组中某段区间的和 <a name="FkEx9"></a> #### 一维前缀和： ```java import java.util.*; public class Main { private static int N = 100010; // 定义数组大小, 防止越界 public static void main(String[] args) { // 初始化输入值 Scanner in = new Scanner(System.in); int n = in.nextInt(); int m = in.nextInt(); int[] arr = new int[N]; // 注意这里是从 1开始的 for (int i = 1; i <= n; i++) arr[i] = in.nextInt(); // s[i]代表 arr的前 i项和 int s[] = new int[N]; s[0] = 0; // 计算出 s[i] for (int i = 1; i <= n; i++) s[i] = s[i - 1] + arr[i]; // 注意运算方式 // 循环输出 while (m-- > 0) { int l = in.nextInt(); int r = in.nextInt(); System.out.println(s[r] - s[l - 1]); // 关键 } } } ``` <a name="XJbLn"></a> #### 二维前缀和 <img src="https://sydblog-1999-1256393142.cos.ap-nanjing.myqcloud.com/blog/2023-04-01-104624.png" alt="image.png" style="zoom:50%;" style=""> <img src="https://sydblog-1999-1256393142.cos.ap-nanjing.myqcloud.com/blog/2023-04-01-104655.png" alt="image.png" style="zoom:50%;" style=""> ```java import java.util.*; public class Main { public static void main(String[] args) { // 输入值进行初始化 Scanner in = new Scanner(System.in); int n = in.nextInt(); int m = in.nextInt(); int q = in.nextInt(); // 初始化 arr int[][] arr = new int[n + 1][m + 1]; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) arr[i][j] = in.nextInt(); // 输出查看 arr // for (int i = 1; i <= n; i++) { // for (int j = 1; j <= m; j++) // System.out.print(arr[i][j] + " "); // } // 求解 s[i][j] int[][] s = new int[n + 1][m + 1]; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) // 计算, 结合图来理解 s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + arr[i][j]; // 循环输出 while (q-- > 0) { // 定位获取区间大小 int x1 = in.nextInt(); int y1 = in.nextInt(); int x2 = in.nextInt(); int y2 = in.nextInt(); // 计算, 结合图来理解 int res = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]; System.out.println(res); } } } ``` <a name="fz9eb"></a> ## 差分算法 **差分定义：差分是求前缀和的逆操作，对于原数组a[n],构造出一个数组b[n],使a[n]为b[n]的前缀和。一般用于快速对整个数组进行操作，比如对将a数组中[l,r]部分的数据全部加上c。使用暴力方法的话，时间复杂至少为O(n)，而使用差分算法可以将时间复杂度降低到O(1)。**<br />**流程：拥有数组b[n]后，想要对a数组中所有的数据加上c,只需要将b[1]+c即可，因为a[i]是b[i]的前缀和，a[i]=b[1]+b[1]+b[3]+……+b[i]。b[1]是所有的a[i]都拥有的子元素,将b[0]+c,那么a[n]中所有的数据都会加上c。如果想将a数组中[l,r]部分的数据全部加上c，只需要将b[l]+c,然后b[r+1]-c即可。差分操作和前缀和一样数组下标都从1开始。b[l]+c后，l后面的数组都会加c。r后面的数据也会被改变，要改回来就得b[r+1]-c。**<br />**如何构造：构造b[n]看起来很难，其实根本就不用刻意去构造它。**<br />**如果将a数组中[l,r]部分的数据全部加上c看作一次插入操作，那么构造的过程可以看作是将a进行了n次插入操作。第一次在[1,1]的范围插入了a[1],第二次在[2,2]范围插入a[2]，第二次在[3,3]范围插入a[3]……，以此类推，进行n次插入后，那么数组a就正好是数组b的前缀和了。** ```java import java.io.BufferedInputStream; import java.util.Scanner; public class Main { static int N = 100010; public static void main(String[] args) { Scanner scanner = new Scanner(new BufferedInputStream(System.in)); int n = scanner.nextInt(); int m = scanner.nextInt(); //a为原数组，b为差分数组 int[] a = new int[N]; int[] b = new int[N]; for (int i = 1; i <= n; i++) { a[i] = scanner.nextInt(); } //进行n次插入，初始化差分数组 for(int i=1;i<=n;i++) { insert(b, i, i, a[i]); } while(m-->0) { int l,r,c; l = scanner.nextInt(); r = scanner.nextInt(); c = scanner.nextInt(); insert(b, l, r, c); } //经过一系列插入操作后，现在答案数组应该是b数组的前缀和，让b数组变成b的前缀和。 //公式 b[i] = b[i-1] + b[i] for(int i=1;i<=n;i++)b[i] +=b[i-1]; for(int i=1;i<=n;i++)System.out.print(b[i]+" "); System.out.println(); scanner.close(); } //插入操作函数 public static void insert(int[] a,int l,int r,int c) { a[l]+=c; a[r+1]-=c; } } ``` 二维形式：  ```java import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; public class Main2 { public static void main(String[] args) throws IOException { //普遍Scanner会超时，所以使用BufferedReader BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out)); String[] str1 = reader.readLine().split(" "); int n = Integer.parseInt(str1[0]); int m = Integer.parseInt(str1[1]); int q = Integer.parseInt(str1[2]); int N = 1010; int[][] a = new int[N][N]; int[][] b = new int[N][N]; // 读入原数组 for (int i = 1; i <= n; i++) { String[] str2 = reader.readLine().split(" "); for (int j = 1; j <= m; j++) { a[i][j] = Integer.parseInt(str2[j-1]); // 初始化差分数组 insert(b, i, j, i, j, a[i][j]); } } while (q-- > 0) { String[] str3 = reader.readLine().split(" "); int x1 = Integer.parseInt(str3[0]); int y1 = Integer.parseInt(str3[1]); int x2 = Integer.parseInt(str3[2]); int y2 = Integer.parseInt(str3[3]); int k = Integer.parseInt(str3[4]); insert(b, x1, y1, x2, y2, k); } // 求b数组的前缀和 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { b[i][j] += b[i][j - 1] + b[i - 1][j] - b[i - 1][j - 1]; //输出 writer.write(b[i][j] + " "); } writer.write("\n"); } //所有write下的内容，会先存在writers中，当启用flush以后，会输出存在其中的内容。如果没有调用flush，则不会将writer中的内容进行输出。 writer.flush(); reader.close(); writer.close(); } // 插入操作函数 private static void insert(int[][] b, int x1, int y1, int x2, int y2, int k) { b[x1][y1] += k; b[x2 + 1][y1] -= k; b[x1][y2 + 1] -= k; b[x2 + 1][y2 + 1] += k; } } ``` <a name="jp5M9"></a> ## 位运算常用操作 **求n的第k位数字: n >> k & 1**<br />**返回n的最后一位1：lowbit(n) = n & -n ** <a name="Wsiur"></a> ## 双指针算法 ```java for (int i = 0, j = 0; i < n; i ++ ) { while (j < i && check(i, j)) j ++ ; // 具体问题的逻辑 } 常见问题分类： (1) 对于一个序列，用两个指针维护一段区间 (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作 ``` <a name="HaDat"></a> ## 离散化(本章最难) **题目描述：**<br />假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。<br />现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c。<br />接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r]之间的所有数的和。<br />**输入：**<br />第一行包含两个整数 n和 m。<br />接下来 n行，每行包含两个整数 x和 c。<br />再接下来 m行，每行包含两个整数 l 和 r。<br />**输出：**<br />共 m行，每行输出一个询问中所求的区间内数字和。<br /> <img src="https://sydblog-1999-1256393142.cos.ap-nanjing.myqcloud.com/blog/2023-04-01-104739.png" alt="image.png" style="zoom:67%;" style=""><br /> <img src="https://sydblog-1999-1256393142.cos.ap-nanjing.myqcloud.com/blog/2023-04-01-104754.png" alt="image.png" style="zoom:67%;" style=""> ```java import java.util.*; public class Main { public static void main (String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); //n次操作 int m = sc.nextInt(); //m次询问 int N = 300010; //因为需要将所有x，l，r存在数组中，这样就是n + 2m <= 300000 int[] a = new int[N]; //从1开始，需要通过x找到离散量，然后+1， int[] s = new int[N]; //前缀和来做，所以需要从1开始记录a List<Integer> alls = new ArrayList<>(); //将所有的使用到的数存在alls中，比如x，l，r //但其中会有先后顺序的差别，以及重复，所以需要排序和去重 List<Pairs> add = new ArrayList<>(); //用来存n次操作 List<Pairs> query = new ArrayList<>(); //用来存m次询问 for (int i = 0; i < n; i++) { int x = sc.nextInt(); int c = sc.nextInt(); add.add(new Pairs(x, c)); alls.add(x); //存入alls中，为后续操作做准备 } for (int i = 0; i < m; i++) { int l = sc.nextInt(); int r = sc.nextInt(); query.add(new Pairs(l, r)); alls.add(l); alls.add(r); } //到此为止，alls中存好了所有会被用到的数轴上的点，可以进行离散化操作 // 1. 排序 2. 去重 Collections.sort(alls); int unique = unique(alls); alls = alls.subList(0, unique); //将去重后的List保存下来，或者此处也可以将unique作为最后一个数，用r作为二分 for (Pairs item:add) { int index = find(item.first, alls); a[index] += item.second; } //求前缀和 for (int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i]; for (Pairs item:query) { int l = find(item.first, alls); int r = find(item.second, alls); System.out.println(s[r] - s[l - 1]); } } //去重 static int unique(List<Integer> list) { int j = 0; for (int i = 0; i < list.size(); i++) { if (i == 0 || list.get(i) != list.get(i - 1)) { list.set(j, list.get(i)); j++; } } return j; } static int find(int x, List<Integer> list) { int l = 0; int r = list.size() - 1; while (l < r) { int mid = l + r >> 1; if (list.get(mid) >= x) { r = mid; } else { l = mid + 1; } } return l + 1; //因为要考虑到前缀和 } } class Pairs { int first; int second; public Pairs(int first, int second) { this.first = first; this.second = second; } } ``` <a name="pIqXY"></a> ## 区间合并 ```java public static int merge(ArrayList<int[]> list){ ArrayList<int[]> res = new ArrayList<>(); list.sort(new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) { return o1[0] - o2[0]; } }); int l = Integer.MIN_VALUE; int r = Integer.MIN_VALUE; for (int[] a : list) { //下一个区间左端点大于老区间右端点 if (a[0] > r){ //找到了新区间，就将老区间添加(不直接加新区间，因为新区间右端点还没确定) if (l != Integer.MIN_VALUE){ res.add(new int[]{l,r}); } l = a[0]; r = a[1]; }else { r = Math.max(r, a[1]); } } //最后一个合并区间,判断条件防止list为空 if (l != Integer.MIN_VALUE){ res.add(new int[]{l,r}); } return res.size(); } ``` 最后修改：2023 年 04 月 01 日 © 允许规范转载 赞 0 如果觉得我的文章对你有用，请随意赞赏