网站开发 会员模块,网站建设标题,宁波网络推广,广州做响应式网站多少钱目录
字典树模板
1、插入操作
2、查询操作
143. 最大异或对 - trie 二进制
3485. 最大异或和 - 前缀和Trie滑动窗口 字典树模板
活动 - AcWing 字典树#xff1a;高效存储和查找字符串集合的数据结构 son[节点1地址][值]节点2地址 —— 节点1的子节点为节点2cnt[节点地…目录
字典树模板
1、插入操作
2、查询操作
143. 最大异或对 - trie 二进制
3485. 最大异或和 - 前缀和Trie滑动窗口 字典树模板
活动 - AcWing 字典树高效存储和查找字符串集合的数据结构 son[节点1地址][值]节点2地址 —— 节点1的子节点为节点2cnt[节点地址] —— 记录以该节点地址为结尾的字符串个数1、插入操作 static void insert(String s)
{int p0;for(char x:s.toCharArray()){int ux-a;if(son[p][u]0) son[p][u]idx; //如果节点不存在 创建节点pson[p][u]; //走到p的子节点}cnt[p]; //把这一串字符插入后 记录以最后此节点为标记的字符串数
} 2、查询操作 static int query(String s)
{int p0;for(char x:s.toCharArray()){int ux-a;if(son[p][u]0) return 0; //有一个节点不存在说明没有这个字符串pson[p][u];}return cnt[p];
} /**道阻且长行则将至*author:Roye_ack
*/
import java.util.*;
import java.io.*;
import java.math.*;class Main
{static int N100010;static int[] cntnew int[N];static int[][] sonnew int[N][26]; //son[节点1][值]节点2 节点1的子节点是节点2static int idx0;static void insert(String s){int p0;for(char x:s.toCharArray()){int ux-a;if(son[p][u]0) son[p][u]idx; //如果节点不存在 创建节点pson[p][u]; //走到p的子节点}cnt[p]; //把这一串字符插入后 记录以最后此节点为标记的字符串数}static int query(String s){int p0;for(char x:s.toCharArray()){int ux-a;if(son[p][u]0) return 0; //有一个节点不存在说明没有这个字符串pson[p][u];}return cnt[p];}public static void main(String[] args) throws IOException{PrintWriter wtnew PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));int nrd.nextInt();while(n--0){String[] srd.nextLine().split( );if(s[0].equals(I)) insert(s[1]);else wt.println(query(s[1]));}wt.flush();}static class rd{static BufferedReader bfnew BufferedReader(new InputStreamReader(System.in));static StringTokenizer tknew StringTokenizer();static String nextLine() throws IOException{return bf.readLine();}static String next() throws IOException{while(!tk.hasMoreTokens()) tknew 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 dnew BigInteger(rd.nextLine());return d;}}
} 143. 最大异或对 - trie 二进制
活动 - AcWing 题目 在给定的N个整数 A1A2.......AN中选出两个进行xor异或运算得到的结果最大是多少? 思路 将每个数以二进制方式存入 Trie 树 每一次检索我们都走与当前 ai 这一位相反的位置走也就是让异或值最大 如果没有相反位置的路可以走的话那么就走相同位置的路 /**道阻且长行则将至*author:Roye_ack
*/
import java.util.*;
import java.io.*;
import java.math.*;class Main
{static int N100010,M31*N;static int[] anew int[N];static int[][] sonnew int[M][2]; //son[节点1][值]节点2 节点1的子节点是节点2static int idx0;static void insert(int x){int p0;for(int i30;i0;i--) //最大31位0~30位{int uxi1;if(son[p][u]0) son[p][u]idx;pson[p][u];}}static int find(int x){int p0,res0;for(int i30;i0;i--){int uxi1;if(son[p][u^1]!0) //如果当前层有对应不同的数走不同的分支{pson[p][u^1];resres*21; //该位异或后为1将其左移i位加到res中}else {pson[p][u];resres*20;}}return res;}public static void main(String[] args) throws IOException{PrintWriter wtnew PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));int nrd.nextInt();for(int i0;in;i){a[i]rd.nextInt();insert(a[i]);}int res0;for(int i0;in;i) resMath.max(res,find(a[i]));wt.print(res);wt.flush();}static class rd{static BufferedReader bfnew BufferedReader(new InputStreamReader(System.in));static StringTokenizer tknew StringTokenizer();static String nextLine() throws IOException{return bf.readLine();}static String next() throws IOException{while(!tk.hasMoreTokens()) tknew 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 dnew BigInteger(rd.nextLine());return d;}}
} 3485. 最大异或和 - 前缀和Trie滑动窗口
3485. 最大异或和 - AcWing题库 题目 思路 本题要求异或和的最大值 求某一段区间的异或和可以求前缀异或和也就是S[r]^S[l-1]因为a^x^xa 因此题目就转化为求异或前缀和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 N3100010;static int[] snew int[N],cntnew int[N]; //cnt记录数的出现次数static int[][] trnew int[N][2]; //son[节点1][值]节点2 节点1的子节点是节点2static int idx0;static void insert(int x,int num){int p0;for(int i30;i0;i--){int uxi1;if(tr[p][u]0) tr[p][u]idx;ptr[p][u];cnt[p]num;}}static int find(int x){int p0,res0;for(int i30;i0;i--){int uxi1;if(cnt[tr[p][u^1]]!0){ptr[p][u^1];resres*21;}else{ptr[p][u];res*2;}}return res;}public static void main(String[] args) throws IOException{PrintWriter wtnew PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));int nrd.nextInt(),mrd.nextInt();for(int i1;in;i){int xrd.nextInt();s[i]s[i-1]^x;}int res0;insert(s[0],1); //刚开始插入s0for(int i1;in;i) //枚举右端点{if(im) insert(s[i-m-1],-1); //删掉不在区间内的左端点(合法区间是[i-m,i])resMath.max(res,find(s[i]));insert(s[i],1);}wt.print(res);wt.flush();}static class rd{static BufferedReader bfnew BufferedReader(new InputStreamReader(System.in));static StringTokenizer tknew StringTokenizer();static String nextLine() throws IOException{return bf.readLine();}static String next() throws IOException{while(!tk.hasMoreTokens()) tknew 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 dnew BigInteger(rd.nextLine());return d;}}
}
