20230325刷题总结（内含trie树模版）

博主： admin
发布时间：2023 年 03 月 25 日
695 次浏览
4 条评论
4901字数
分类：每日算法

# 20230325刷题总结（内含trie数模版）

由于报名参加蓝桥杯，后续内容均以专题出现，刷的题目偏系统一些。

省流（重要题目）：前缀和、子矩阵的和、差分、差分矩阵（模板题），增减序列，最大异或和、最大异或对（强烈推荐）

## 前缀和

知识摘要（主要我的理解）：前缀和通常指前缀和数组，记录的是数组开始到其中某一个元素中间元素的和，类似于高中学习的数列求和S，有了这个S可以方便一些操作（某一段子数组和-哈希表）， 不管怎么说前缀和大前提连续元素，即某一片段或者某一区域，子数组子区域可能和前缀和有关，或者前缀和方式优化，但出现子序列等的话大概率不会用到前缀和。

一维和二维前缀和求和方式如图（较简陋），难点在于下标可能会经常搞错，我理解是希望多少个元素对应下标就是多少：

### 前缀和

思路：一维前缀和模板题

```java
import java.util.*;
import java.io.*;

public class Main{
 public static void main(String[] args){
 Scanner sc = new Scanner(System.in);
 String str = sc.nextLine();
 String[] sa = str.split(" ");
 int N = Integer.parseInt(sa[0]);
 int M = Integer.parseInt(sa[1]);
 int[] arr = new int[N];
 long[] sum = new long[N + 1];
 str = sc.nextLine();
 sa = str.split(" ");
 for(int i = 0; i < N; i++){
 arr[i] = Integer.parseInt(sa[i]);
 sum[i + 1] = sum[i] + arr[i];
 }
 while(M-- > 0){
 int l = sc.nextInt();
 int r = sc.nextInt();
 System.out.println(sum[r] - sum[l - 1]);
 }
 }
}
```

### 子矩阵的和

```java
import java.util.*;
import java.io.*;

public class Main{
 public static void main(String[] args){
 Scanner sc = new Scanner(System.in);
 int n = sc.nextInt();
 int m = sc.nextInt();
 int q = sc.nextInt();
 int[][] arr = new int[n][m];
 long[][] sum = new long[n + 1][m + 1];
 for(int i = 0; i < n; i++){
 // String s = sc.nextLine();
 // String[] sa = s.split(" ");
 for(int j = 0; j < m; j++){
 arr[i][j] = sc.nextInt();
 sum[i + 1][j + 1] = sum[i][j + 1] + sum[i + 1][j] - sum[i][j] + arr[i][j];
 }
 }
 while(q-- > 0){
 int x1 = sc.nextInt();
 int x2 = sc.nextInt();
 int y1 = sc.nextInt();
 int y2 = sc.nextInt();
 System.out.println(sum[y1][y2] + sum[x1 - 1][x2 - 1] - sum[x1 - 1][y2] - sum[y1][x2 - 1]);
 }
 }
}

```

### 截断数组

思路：前缀和应用，想象数组n个元素，会有n-1个空格（不含两边），随机从里面抽取两个有(n-1)*(n-2)/2种选法，在此基础加限定条件只有该元素为结尾前缀和是数组和1/3才可以。判断和为0情况。

```java
import java.util.*;
import java.io.*;

public class Main{
 public static void main(String[] args){
 Scanner sc = new Scanner(System.in);
 String s = sc.nextLine();
 String[] sA = s.split(" ");
 int N = Integer.parseInt(s);
 if(N <= 2){
 System.out.println(0);
 return;
 }
 int[] arr = new int[N];
 int[] sum = new int[N + 1];
 s = sc.nextLine();
 sA = s.split(" ");
 for(int i = 0; i < N; i++){
 arr[i] = Integer.parseInt(sA[i]);
 sum[i + 1] = sum[i] + arr[i];
 }
 if(sum[N] % 3 != 0){
 System.out.println(0);
 return;
 }
 int t = sum[N] / 3;
 int x = 0;
 if(t == 0){
 for(int i = 1; i <= N; i++){
 if(sum[i] == 0){
 x++;
 }
 }
 System.out.println((long)(x - 1) * (x - 2) / 2);
 return;
 }
 x = 0;
 int res = 0;
 for(int i = 1; i < N; i++){
 if(sum[i] == t){
 x++;
 }
 if(sum[i] == 2 * t){
 res += x;
 }
 }
 System.out.println(res);
 }
}
```

### K倍区间

思路：思路和上述类似。

```java
import java.util.*;
import java.io.*;

public class Main{
 public static void main(String[] args){
 Scanner sc= new Scanner(System.in);
 int n = sc.nextInt();
 int k = sc.nextInt();
 int sum = 0;
 Map<Integer, Integer> map = new HashMap<>();
 map.put(0, 1);
 // int t = 1;
 long res = 0;
 while(n-- > 0){
 sum += sc.nextInt();
 sum = sum % k;
 res += map.getOrDefault(sum, 0);
 map.put(sum, map.getOrDefault(sum, 0) + 1);
 // if(sum % k == 0) t++;
 }
 System.out.println(res);
 }
 
}
```

## 差分

差分我的理解，和前缀和略微反过来的感觉，前缀和求取过程记录子数组和的关系，差分定义则是元素与元素之间的差。

作用：对差分数组某一元素加1，则表示对后面原数组所有元素加1.

### 差分

```JAVA
import java.util.*;
import java.io.*;

public class Main{
 public static void main(String[] args){
 Scanner sc = new Scanner(System.in);
 int n = sc.nextInt();
 int m = sc.nextInt();
 int[] arr = new int[n + 1];
 int[] add = new int[n + 1];
 int t = 1;
 while(t <= n){
 arr[t] = sc.nextInt();
 t++;
 }
 while(m-- > 0){
 int l = sc.nextInt();
 int r = sc.nextInt();
 int v = sc.nextInt();
 add[l] += v;
 if(r + 1 <= n) add[r + 1] -= v;
 }
 int[] sum = new int[n + 1];
 for(int i = 1; i <= n; i++){
 // System.out.print(arr[i] + " ");
 sum[i] = sum[i - 1] + add[i];
 System.out.print(arr[i] + sum[i] + " ");
 }
 
 }
}
```

### 差分矩阵

思路：二维差分

```java
import java.util.*;
import java.io.*;

public class Main{
 public static void main(String[] args){
 Scanner sc = new Scanner(System.in);
 int n = sc.nextInt();
 int m = sc.nextInt();
 int q = sc.nextInt();
 int[][] arr = new int[n + 1][m + 1];
 int[][] add = new int[n + 1][m + 1];
 for(int i = 1; i <= n; i++){
 for(int j = 1; j <= m; j++){
 arr[i][j] = sc.nextInt();
 }
 }
 while(q-- > 0){
 int x1 = sc.nextInt();
 int x2 = sc.nextInt();
 int y1 = sc.nextInt();
 int y2 = sc.nextInt();
 int v = sc.nextInt();
 add[x1][x2] += v;
 if(y1 + 1 <= n && y2 + 1 <= m)add[y1 + 1][y2 + 1] += v;
 if(y2 + 1 <= m)add[x1][y2 + 1] -=v;
 if(y1 + 1 <= n)add[y1 + 1][x2] -= v;
 }
 int[][] sum = new int[n + 1][m + 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] + add[i][j];
 System.out.print(sum[i][j] + arr[i][j] + " ");
 }
 System.out.println("");
 }
 }
}
```

### 改变数组的元素

思路：额外定义差分数组。

```java
import java.util.*;
import java.io.*;

public class Main{
 public static void main(String[] args){
 Scanner sc = new Scanner(System.in);
 int m = sc.nextInt();
 
 while(m-- > 0){
 int n = sc.nextInt();
 // List<Integer> l = new ArrayList<>();
 int[] arr = new int[n];
 int t = 0;
 while(t < n){
 int x = sc.nextInt();
 if(x == 0){
 t++;
 continue;
 }
 if(x >= t + 1) arr[0] += 1;
 else arr[t + 1 - x] += 1;
 if(t + 1 < n) arr[t + 1] = -1;
 t++;
 }
 int[] sum = new int[n + 1];
 for(int i = 1; i <= n; i++){
 sum[i] = sum[i - 1] + arr[i-1];
 if(sum[i] > 0) System.out.print(1 + " ");
 else System.out.print(0 + " ");
 }
 System.out.println();
 }
 }
}
```

### 增减序列

思路：差分应用题。很多差分题目是我们在题目条件下不断构建差分数组，最后将其前缀和加到原数组上。本题和大多数差分题目很不同。思路上从差分数组定义出发，即差分数组记录连续元素之间的差，那么所有差都为0则表示原数组都相同。前面说差分数组元素加1代表后面区间全部加1，差分数组减1代表后面区间全部减1，翻译过来就是每次可以挑选两个差分数组元素一个加1一个减一，这样的话将差分数组正数负数和取绝对值小的作为必须操作数。剩下的可以选择差分数组开头和结尾进行加减。种类的话不同种类出现原因在于剩下元素和开头结尾操作产生。

```java
import java.util.*;
import java.io.*;

public class Main{
 public static void main(String[] args){
 Scanner sc = new Scanner(System.in);
 int n = sc.nextInt();
 int[] arr = new int[n];
 int[] diff = new int[n];
 int i = 0;
 while(i < n) arr[i++] = sc.nextInt();
 diff[0] = arr[0];
 for(int j = 1; j < n; j++) diff[j] = arr[j] - arr[j - 1];
 long pos = 0;
 long neg = 0;
 for(int j = 1; j < n; j++){
 if(diff[j] > 0) pos += diff[j];
 else neg -= diff[j];
 }
 System.out.println(Math.min(pos, neg) + Math.abs(pos - neg));
 System.out.println(Math.abs(pos - neg) + 1);
 }
}
```

## Trie树

### Trie字符串统计(Trie树模板)

```java
import java.util.*;
import java.io.*;

public class Main{
    static int N = 100000;
    static int[][] son = new int[N][26];;
    static int index = 0;
    static int[] cnt = new int[N];;

static void insert(String s){
 int p = 0;
 for(int i = 0; i < s.length(); i++){
 int u = s.charAt(i) - 'a';
 if(son[p][u] == 0) son[p][u] = ++index;
 p = son[p][u];
 }
 cnt[p]++;
 }

static int query(String s){
 int p = 0;
 for(int i = 0; i < s.length(); i++){
 int u = s.charAt(i) - 'a';
 if(son[p][u] == 0) return 0;
 p = son[p][u];
 }
 return cnt[p];
 }

public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        // init();
        while(m-- > 0){
            String opt = sc.next();
            String s = sc.next();
            if(opt.equals("I")){
               insert(s); 
            }else if(opt.equals("Q")){
                System.out.println(query(s));
            }
        }
    }
}

```

### 最大异或对

思路：好题目！！常规的暴力肯定难以解决。需要借助trie树，数有二进制表示即将模板字母换位0/1可以存储一个数。之后就是怎么找最大异或对了，怎么样异或结果最大？和它异或的数每一位都不同，即查询trie树每次选择和当前数不同的，这样遍历出来的值和当前数异或结果最大。

```java
import java.util.*;
import java.io.*;

public class Main{
 static int N = 3100000;
 static int[][] son = new int[N][2];
 static int index = 0;
 static int[] cnt = new int[N];
 
 static void insert(int x){
 int p = 0;
 for(int i = 31; i >= 0; i--){
 int u = x >> i & 1;
 if(son[p][u] == 0){
 son[p][u] = ++index;
 }
 p = son[p][u];
 }
 cnt[p]++;
 }
 
 static int query(int x){
 int p = 0;
 int ret = 0;
 for(int i = 31; i >= 0; i--){
 int u = x >> i & 1;
 int uo = u;
 if(u == 0) u = 1;
 else u = 0;
 if(son[p][u] != 0){
 p = son[p][u];
 ret = ret * 2 + u;
 }else{
 p = son[p][uo];
 ret = ret * 2 + uo;
 }
 }
 return x ^ ret;
 
 }
 
 public static void main(String[] args){
 Scanner sc = new Scanner(System.in);
 int n = sc.nextInt();
 int res = 0;
 for(int i = 0; i < n; i++){
 int x = sc.nextInt();
 insert(x);
 res = Math.max(res, query(x));
 }
 System.out.println(res);
 }
}
```

### 最大异或和

思路：和上述不同，这个不是任意两个元素而是一个连续的子数组，借助前缀和思想，求前缀异或，这样目标也变成了找前缀异或数组里两个异或结果最大的值，不过两个值间隔不许超过M。

```java
import java.util.*;
import java.io.*;

public class Main{
 static int N = 3100010;
 static int[][] son = new int[N][2];
 static int[] cnt = new int[N];
 static int index = 0;
 
 static void insert(int x, int o){
 int p = 0;
 for(int i = 31; i >= 0; i--){
 int u = x >> i & 1;
 if(son[p][u] == 0) son[p][u] = ++index;
 
 p = son[p][u];
 cnt[p] += o;
 }
 
 }
 
 static int query(int x){
 int p = 0;
 int res = 0;
 for(int i = 31; i >= 0; i--){
 int u = x >> i & 1;
 int up = 0;
 if(u == 0) up = 1;
 if(cnt[son[p][up]] == 0){
 res = res * 2 + u;
 p = son[p][u];
 }else{
 res = res * 2 + up;
 p = son[p][up];
 }
 }
 return x ^ res;
 }
 
 public static void main(String[] args){
 Scanner sc = new Scanner(System.in);
 int n = sc.nextInt();
 int m = sc.nextInt();
 int res = 0;
 int[] arr = new int[n];
 int[] sum = new int[n + 1];
 for(int i = 0; i < n; i++){
 arr[i] = sc.nextInt();
 sum[i + 1] = sum[i] ^ arr[i];
 }
 insert(0, 1);
 for(int i = 1; i <= n; i++){
 if(i > m) insert(sum[i - m - 1], -1);
 res = Math.max(res, query(sum[i]));
 insert(sum[i], 1);
 }
 System.out.println(res);
 
 }
}
```

```

最后修改：2023 年 03 月 26 日

如果觉得我的文章对你有用，请随意赞赏

4 条评论

知名1825
March 27th, 2023 at 11:10 pm

表评论1825

回复
mmk
March 26th, 2023 at 10:22 am

太深了OωO，还没学到那儿

回复
东东粉丝团团长
March 25th, 2023 at 10:57 pm

大佬，您好。我也报名了蓝桥杯，但我是菜狗，也一直没怎么准备。看了您这期笔记，好多东西我都没听说过，感觉您的知识储备以及准备工作都比我多得多，感到佩服|´・ω・)ノ

回复
admin
March 25th, 2023 at 10:56 pm

感谢大家踩踩

回复

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

mmk
可以的
知名2617
表评论2617
知名1825
表评论1825
mmk
太深了OωO，还没学到那儿
东东粉丝团团长
大佬，您好。我也报名了蓝桥杯，但我是菜狗，也一直没怎么准备。看...

20230325刷题总结（内含trie树模版）

admin • 2023 年 03 月 25 日

# 20230325刷题总结（内含trie数模版）

由于报名参加蓝桥杯，后续内容均以专题出现，刷的题目偏系统一些。

省流（重要题目）：前缀和、子矩阵的和、差分、差分矩阵（模板题），增减序列，最大异或和、最大异或对（强烈推荐）

## 前缀和

一维和二维前缀和求和方式如图（较简陋），难点在于下标可能会经常搞错，我理解是希望多少个元素对应下标就是多少：

### 前缀和

思路：一维前缀和模板题

```java
import java.util.*;
import java.io.*;

### 子矩阵的和

```java
import java.util.*;
import java.io.*;

```

### 截断数组

```java
import java.util.*;
import java.io.*;

### K倍区间

思路：思路和上述类似。

```java
import java.util.*;
import java.io.*;

## 差分

差分我的理解，和前缀和略微反过来的感觉，前缀和求取过程记录子数组和的关系，差分定义则是元素与元素之间的差。

作用：对差分数组某一元素加1，则表示对后面原数组所有元素加1.

### 差分

```JAVA
import java.util.*;
import java.io.*;

### 差分矩阵

思路：二维差分

```java
import java.util.*;
import java.io.*;

public class Main{
 public static void main(String[] args){
 Scanner sc = new Scanner(System.in);
 int n = sc.nextInt();
 int m = sc.nextInt();
 int q = sc.nextInt();
 int[][] arr = new int[n + 1][m + 1];
 int[][] add = new int[n + 1][m + 1];
 for(int i = 1; i <= n; i++){
 for(int j = 1; j <= m; j++){
 arr[i][j] = sc.nextInt();
 }
 }
 while(q-- > 0){
 int x1 = sc.nextInt();
 int x2 = sc.nextInt();
 int y1 = sc.nextInt();
 int y2 = sc.nextInt();
 int v = sc.nextInt();
 add[x1][x2] += v;
 if(y1 + 1 <= n && y2 + 1 <= m)add[y1 + 1][y2 + 1] += v;
 if(y2 + 1 <= m)add[x1][y2 + 1] -=v;
 if(y1 + 1 <= n)add[y1 + 1][x2] -= v;
 }
 int[][] sum = new int[n + 1][m + 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] + add[i][j];
 System.out.print(sum[i][j] + arr[i][j] + " ");
 }
 System.out.println("");
 }
 }
}
```

### 改变数组的元素

思路：额外定义差分数组。

```java
import java.util.*;
import java.io.*;

### 增减序列

```java
import java.util.*;
import java.io.*;

## Trie树

### Trie字符串统计(Trie树模板)

```java
import java.util.*;
import java.io.*;

public class Main{
    static int N = 100000;
    static int[][] son = new int[N][26];;
    static int index = 0;
    static int[] cnt = new int[N];;

```

### 最大异或对

```java
import java.util.*;
import java.io.*;

### 最大异或和

```java
import java.util.*;
import java.io.*;

```

20230325刷题总结（内含trie树模版）

4 条评论

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

20230325刷题总结（内含trie树模版）

20230315刷题总结（内含kmp模板）

2022-7-26:Future Transformer for Long-term Action Anticipation论文阅读

JVM虚拟机-自动内存管理

LeetCode动态规划相关题目总结

类加载机制

虚拟机字节码执行引擎

前后端编译和优化

20230315刷题总结（内含kmp模板）

虚拟机和Java多线程

20230325刷题总结（内含trie树模版）

4 条评论

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

20230325刷题总结（内含trie树模版）

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款