【蓝桥杯集训10】Tire树 字典树 最大异或对专题（3 / 3）

目录

字典树模板

1、插入操作

2、查询操作

143. 最大异或对 - trie + 二进制

3485. 最大异或和 - 前缀和+Trie+滑动窗口

---

字典树模板

活动 - AcWing

字典树：高效存储和查找字符串集合的数据结构

• son[节点1地址][值]=节点2地址 —— 节点1的子节点为节点2
• cnt[节点地址] —— 记录以该节点地址为结尾的字符串个数

1、插入操作

static void insert(String s)
{int p=0;for(char x:s.toCharArray()){int u=x-'a';if(son[p][u]==0) son[p][u]=++idx; //如果节点不存在 创建节点p=son[p][u]; //走到p的子节点}cnt[p]++; //把这一串字符插入后 记录以最后此节点为标记的字符串数
}

2、查询操作

static int query(String s)
{int p=0;for(char x:s.toCharArray()){int u=x-'a';if(son[p][u]==0) return 0; //有一个节点不存在，说明没有这个字符串p=son[p][u];}return cnt[p];
}

/**道阻且长，行则将至*author:Roye_ack
*/
import java.util.*;
import java.io.*;
import java.math.*;class Main
{static int N=100010;static int[] cnt=new int[N];static int[][] son=new int[N][26]; //son[节点1][值]=节点2  节点1的子节点是节点2static int idx=0;static void insert(String s){int p=0;for(char x:s.toCharArray()){int u=x-'a';if(son[p][u]==0) son[p][u]=++idx; //如果节点不存在 创建节点p=son[p][u]; //走到p的子节点}cnt[p]++; //把这一串字符插入后 记录以最后此节点为标记的字符串数}static int query(String s){int p=0;for(char x:s.toCharArray()){int u=x-'a';if(son[p][u]==0) return 0; //有一个节点不存在，说明没有这个字符串p=son[p][u];}return cnt[p];}public static void main(String[] args) throws IOException{PrintWriter wt=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));int n=rd.nextInt();while(n-->0){String[] s=rd.nextLine().split(" ");if(s[0].equals("I")) insert(s[1]);else wt.println(query(s[1]));}wt.flush();}static class rd{static BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));static StringTokenizer tk=new StringTokenizer("");static String nextLine() throws IOException{return bf.readLine();}static String next() throws IOException{while(!tk.hasMoreTokens()) tk=new StringTokenizer(bf.readLine());return tk.nextToken();}static int nextInt() throws IOException{return Integer.parseInt(next());}static double nextDouble() throws IOException{return Double.parseDouble(next());}static long nextLong() throws IOException{return Long.parseLong(next());}static BigInteger nextBig() throws IOException{BigInteger d=new BigInteger(rd.nextLine());return d;}}
}

143. 最大异或对 - trie + 二进制

活动 - AcWing

题目：

在给定的N个整数 A1，A2.......AN中选出两个进行xor（异或）运算，得到的结果最大是多少?

思路：

将每个数以二进制方式存入 Trie 树

每一次检索，我们都走与当前 ai 这一位相反的位置走，也就是让异或值最大

如果没有相反位置的路可以走的话，那么就走相同位置的路

/**道阻且长，行则将至*author:Roye_ack
*/
import java.util.*;
import java.io.*;
import java.math.*;class Main
{static int N=100010,M=31*N;static int[] a=new int[N];static int[][] son=new int[M][2]; //son[节点1][值]=节点2  节点1的子节点是节点2static int idx=0;static void insert(int x){int p=0;for(int i=30;i>=0;i--) //最大31位，0~30位{int u=x>>i&1;if(son[p][u]==0) son[p][u]=++idx;p=son[p][u];}}static int find(int x){int p=0,res=0;for(int i=30;i>=0;i--){int u=x>>i&1;if(son[p][u^1]!=0) //如果当前层有对应不同的数，走不同的分支{p=son[p][u^1];res=res*2+1; //该位异或后为1，将其左移i位加到res中}else {p=son[p][u];res=res*2+0;}}return res;}public static void main(String[] args) throws IOException{PrintWriter wt=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));int n=rd.nextInt();for(int i=0;i<n;i++){a[i]=rd.nextInt();insert(a[i]);}int res=0;for(int i=0;i<n;i++) res=Math.max(res,find(a[i]));wt.print(res);wt.flush();}static class rd{static BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));static StringTokenizer tk=new StringTokenizer("");static String nextLine() throws IOException{return bf.readLine();}static String next() throws IOException{while(!tk.hasMoreTokens()) tk=new StringTokenizer(bf.readLine());return tk.nextToken();}static int nextInt() throws IOException{return Integer.parseInt(next());}static double nextDouble() throws IOException{return Double.parseDouble(next());}static long nextLong() throws IOException{return Long.parseLong(next());}static BigInteger nextBig() throws IOException{BigInteger d=new BigInteger(rd.nextLine());return d;}}
}

 

3485. 最大异或和 - 前缀和+Trie+滑动窗口

3485. 最大异或和 - AcWing题库

题目：

思路：

本题要求异或和的最大值

求某一段区间的异或和可以求前缀异或和，也就是S[r]^S[l-1]，因为a^x^x=a

因此题目就转化为求异或前缀和S[1]~S[N]中选一个最大的异或对

维护一个长度不超过m的滑动窗口，把窗口外的数从字典树删除，删除操作只要让cnt--就可以

长度不超过m的连续子数组，我们可以枚举右端点s[i]，在合法区间内求最大的另一异或数

最大异或对模板

• 想要异或结果最大，则每一位都要尽量不同，这样异或结果每一位1的个数才会最多
• 将每个数字的二进制数（01串），从高位到低位存到trie中
• 对于每一位ai，都尽量往跟他相反的方向走（比如ai为0则走1分支，1则走0分支），如果实在没有相反的分支，则顺着走

/**道阻且长，行则将至*author:Roye_ack
*/
import java.util.*;
import java.io.*;
import java.math.*;class Main
{static int N=3100010;static int[] s=new int[N],cnt=new int[N]; //cnt记录数的出现次数static int[][] tr=new int[N][2]; //son[节点1][值]=节点2  节点1的子节点是节点2static int idx=0;static void insert(int x,int num){int p=0;for(int i=30;i>=0;i--){int u=x>>i&1;if(tr[p][u]==0) tr[p][u]=++idx;p=tr[p][u];cnt[p]+=num;}}static int find(int x){int p=0,res=0;for(int i=30;i>=0;i--){int u=x>>i&1;if(cnt[tr[p][u^1]]!=0){p=tr[p][u^1];res=res*2+1;}else{p=tr[p][u];res*=2;}}return res;}public static void main(String[] args) throws IOException{PrintWriter wt=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));int n=rd.nextInt(),m=rd.nextInt();for(int i=1;i<=n;i++){int x=rd.nextInt();s[i]=s[i-1]^x;}int res=0;insert(s[0],1); //刚开始插入s0for(int i=1;i<=n;i++) //枚举右端点{if(i>m) insert(s[i-m-1],-1); //删掉不在区间内的左端点(合法区间是[i-m,i])res=Math.max(res,find(s[i]));insert(s[i],1);}wt.print(res);wt.flush();}static class rd{static BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));static StringTokenizer tk=new StringTokenizer("");static String nextLine() throws IOException{return bf.readLine();}static String next() throws IOException{while(!tk.hasMoreTokens()) tk=new StringTokenizer(bf.readLine());return tk.nextToken();}static int nextInt() throws IOException{return Integer.parseInt(next());}static double nextDouble() throws IOException{return Double.parseDouble(next());}static long nextLong() throws IOException{return Long.parseLong(next());}static BigInteger nextBig() throws IOException{BigInteger d=new BigInteger(rd.nextLine());return d;}}
}