回顾：：做过的TRIE树题_acm trie树题目

作者：AllinToyou | 2024-06-16 18:24:07

踩

acm trie树题目

【THUSC2015】异或问题 (Standard IO)
Time Limits: 2000 ms Memory Limits: 262144 KB Detailed Limits

Description

给定长度为n的数列X={x1,x2,...,xn}和长度为m的数列Y={y1,y2,...,ym}，令矩阵A中第i行第j列的值Aij=xi xor yj，每次询问给定矩形区域i∈[u,d],j∈[l,r]，找出第k大的Aij。

Input

第一行包含两个正整数n,m，分别表示两个数列的长度第二行包含n个非负整数xi；
第三行包含m个非负整数yj；
第四行包含一个正整数p，表示询问次数；
随后p行，每行均包含5个正整数，用来描述一次询问，每行包含五个正整数u,d,l,r,k，含义如题意所述。

Output

共p行，每行包含一个非负整数，表示此次询问的答案。

Sample Input

3 3
1 2 4
7 6 5
3
1 2 1 2 2
1 2 1 3 4
2 3 2 3 4

Sample Output

6
5
1

Data Constraint

对于100%的数据，0<=Xi,Yj<2^31,
1<=u<=d<=n<=1000,
1<=l<=r<=m<=300000,
1<=k<=(d-u+1)*(r-l+1),
1<=p<=500
其中，部分测试数据有如下特征（互不包含）：
对于5%的数据，满足1<=m<=1000, 1<=p<=10, k=1;
对于15%的数据，满足1<=m<=3000, 1<=p<=200;
对于20%的数据，满足p=1;
对于30%的数据，满足k=1;

对于其余30%的数据，没有其他特征。

可持久化trie

可以发现n较小，m较大，考虑对m这一维建可持久化trie树。

对于每一个询问，线性地扫n那一维，记录每一二进制位的0、1总个数。

再高位向低位枚举，在trie树上跳。做法和可持久化线段树上找k大值相似。


#include
   
   
    
    
#include
    
    
     
     
#include
     
     
      
      
 
using namespace std ;
 
#define N 1010
#define M 300010
#define mx 30
 
int n,m,p,A[N],B[M],rot[N],T,pos[2][N],ans[N],a[2] ;
 
struct node {
	int l , r , si ;
}tr[5458385*2] ;
 
void Update( int po ) {
	int l = tr[po].l , r = tr[po].r ;
	tr[po].si = tr[l].si + tr[r].si ;
}
 
void Ins( int va , int &po , int dep ) {
	tr[++T] = tr[po] ;
	po =  T ;
	if( dep<0 ) {
		tr[po].si++ ;
		return ;
	}
	if( ( ( 1 << dep  ) & va ) ) Ins( va , tr[po].r , dep-1 ) ;
		else Ins( va , tr[po].l , dep-1 ) ;
	Update( po ) ;
}
 
int Ask( int pos , bool h ) {
	if( h ) return tr[ tr[pos].l ].si ;
	 	else return tr[ tr[pos].r ].si ;
}
 
void Nexjump( bool bit , int &pos , bool h  ) {
	int q = bit ^ h ;
	pos = q ? tr[pos].r : tr[pos].l ;
}	
 
int main() {
	scanf("%d%d",&n,&m ) ;
	for( int i=1 ; i<=n ; i++ ) scanf("%d",&A[i] ) ;
	for( int i=1 ; i<=m ; i++ ) {
		scanf("%d",&B[i] ) ;
		Ins( B[i] , rot[i]=rot[i-1] , mx ) ;
	}
	scanf("%d",&p ) ;
	while( p-- ) {
		int u , d , l , r , k ;
		scanf("%d%d%d%d%d",&u,&d,&l,&r,&k ) ;// Va( r ) - Va( l-1 ) 
		for( int i=1 ; i<=n ; i++ ) {
			pos[0][i] = rot[l-1] ;
			pos[1][i] = rot[r] ;
		}
		for( int i=mx ; i>=0 ; i-- ) { // Asking position of i 's  if xor==1 Value 
			a[0] = a[1] = 0 ;
			for( int j=u ; j<=d ; j++ ) {
				bool h = ( ( A[j] >> i ) & 1 ) ;
				a[0] += Ask( pos[0][j],h ) ;
				a[1] += Ask( pos[1][j],h ) ;
			}
			if( a[1] - a[0] >= k ) ans[i] = 1 ;
				else ans[i] = 0 , k-=a[1]-a[0] ;
			for( int j=u ; j<=d ; j++ ) {
				bool h = ( ( A[j] >> i ) & 1 ) ;
				Nexjump( ans[i] , pos[0][j] , h  ) , Nexjump( ans[i] , pos[1][j] , h ) ;
			}
		}
		int ret = 0 ;
		for( int i=0 ; i<=mx ; i++ ) ret += ans[i] * ( 1 << i ) ;
		printf("%d\n",ret ) ;
	}
}

【WinterCamp 2013】单词查找 (Standard IO)
Time Limits: 2000 ms Memory Limits: 65536 KB Detailed Limits
Goto ProblemSet
Description
两个单词的最长公共前缀是从第一个字符开始的最长的相同字符串，例如“identity”和“idealistic”的最长公共前缀为“ide”。

一个数据库里有N个单词，在数据库中查找单词W采用的算法是非常原始的，把数据库里的单词逐个跟W比较，两个单词逐个字符比较直到找到一个不同的字符或某个单词所有字符全部比较结束（此时可以断定两个单词相同或某一个单词比另一个要长），当找到W时，算法结束。

分析上述算法，查找W需要的步数等于字符比较次数，把W与每个比较的单词的最长公共前缀的长度加起来的和就是答案。

编程计算查找Q个单词，每个单词所需的比较次数。

Input
第一行包含一个整数N(1<=N<=30000)，表示数据库中单词的个数。

接下来N行按顺序描述数据库中的单词，不会出现相同的单词。

接下来包含一个整数Q(1<=Q<=30000)，表示需要查找的单词数量。

接下来Q行，每行描述需要查找的单词。

所有的单词都是由不超过30个英文小写字母组成的字符串。

Output

每行输出一个整数，表示每个单词查找过程中的比较次数。

Sample Input

8
majmunica
majmun
majka
malina
malinska
malo
maleni
malesnica
3
krampus
malnar
majmun

Sample Output

8
29
14

Hint

样例2中查找单词“krampus”的比较次数为8，因为要跟数据库中每个单词的第一个字符比较一次。

而查找单词“malnar”的时候，我们需要，前3个单词都需要3次比较，接下来的5个单词每个都需要4次比较，这样一共29次。

查找单词“majmun”一共需要14次，对于数据库中第一个单词“majmunica”，我们有6次成功的比较，还需一步判断出“majmunica”比“majmun”要长，对于第二个单词“majmun”，我们同样有6次成功的比较，还需一步判断出两个单词是完全相同的，所以整个比较结束，一共花了14次。

可持久化trie是会爆空间的，除非用二进制压位。

考虑字符串哈希+普普通通的trie

对于询问的字符串C，若它出现过，即存在s[i]=C，i若有多个取值，取最小值，答案必然为从字符串1至i的比较次数。考虑在插入i这个字符串时记录它此时的答案存起来，在询问时用。匹配用哈希。

对于未出现过的，直接在trie上跳，即为答案。


#include
   
   
    
    
#include
    
    
     
     
#include
     
     
      
      
#include
      
      
#include
       
       
         using namespace std ; #define N 30010 #define psb( x ) push_back( x ) #define iter vector< forvect >::iterator int n , Q , i , j , k , st[N][2] , mo[2] = { 44449 , 10000007 } , cur[2] , T ; char s[40] ; typedef pair< int , int > P ; map< P , int > z ; struct forvect { int letter , nex ; }; struct node { int va ; vector< forvect > v ; }tr[N*30] ; int tmp ; void ins( int n ) { int po = 1 ; for( int i=0 ; i

 
 
 
 
 Description
 一棵树，n节点（N<=100000 ）， 每条边都有一个字符串 。
 询问一个三元组（ int u , int  v , string  s ) ， 求u 到 v 前缀为s的字符串有多少个 。
 ( Q <= 100000 ) 字符串长度小于10
 samin
 samout( 懒得写了。 )
 
 
 
 
 Obviously , using Persistence trie trees. Consider recording a trie tree from root  to every node X . because |s|<=10 , executable .
 for queries ,  ans = ask( u ) + ask( v ) - 2 * lca( u , v )  ;
 
 
  
  
  
#include
    
    
     
     
#include
     
     
      
      
#include
      
      
       
       
 
using namespace std ;
 
#define N 100010
 
int  n,m,i,j,k,Q,T,g[N] ;
 
typedef char str[12] ;
 
str s ;
 
struct ecc {
	int y,l ;
	str s ;
}f[N*2] ;
 
struct trie {
	int z , son[26] ;
}tr[N*10] ;
 
int tot,rot[N] ;
 
void ins( int a , int b  , str s ) {
	f[++T].y = b , f[T].l = g[a] , g[a] = T ;
	for( int i=0 ; i
       
       
        
        de[b] ) swap( a,b ) ;
	for( sub = de[b] - de[a] , j=0 ; sub ; sub/=2 , j++ ) 
		if( sub % 2 ) b = l[j][b] ;
	if( a==b ) return a ;
	for( i=1 ; i>=0 ; ) 
		for( i=30 ; i>=0 ; i-- ) if( l[i][a]!=l[i][b] ) {
			a = l[i][a] , b = l[i][b] ;
			break ;
		}
	return fa[a] ;
}
 
int FIND_TRIE( int x , str s ) {
	int len = strlen( s ) , i ;
	x = rot[x] ;
	for( i=0 ; i

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/AllinToyou/article/detail/727753

回顾：：做过的TRIE树题_acm trie树 题目

回顾：：做过的TRIE树题_acm trie树题目