暑期总结 2022.7.18 trie树+堆

一、trie 树

1.二叉树：每一个父节点都有两个子节点，分为：满二叉树、完全二叉树。

2.功能：高效的储存和查找字符串。

    1.储存：大致过程为如果有该节点，则无需拓展，如果没有，则不断向外延伸。

    2.查找：按照字母，一层一层向下寻找，需注意的是树的最后一个字母都要做标记，这样也是为查找做准备。

以下为模板题代码：（最重要的理解每个数组含义）

#include 

using namespace std;

int a[100010][26],cnt[100010],idx;
char x[10],y[1000010];
void insert(char* str)
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int u=str[i]-'a';
        if(!a[p][u]) a[p][u]=++idx;
        p=a[p][u];
    }
    cnt[p]++;
}
int query(char str[])
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int u=str[i]-'a';
        if(!a[p][u]) return 0;
        p=a[p][u];
    }
    return cnt[p];
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i 
3.最大异或对
 
是对trie树的运用，不过在这里每个节点存储的不再是字母，而是0和1,然后查找出每一个数异或后最大值所对应的元素，最后每一个元素进行比较，输出最大的即可。
 
#include
#include
using namespace std;
const int N = 100010,M = 31*N;

int n ;
int a[N];
int son[M][2],idx ;

void insert (int x) {
	int p = 0;
	for(int i = 30; i >= 0; i --) {
		int u = x >> i & 1;
		if(!son[p][u]) son[p][u] = ++ idx;
		p = son[p][u];
	}
}

int search(int x) {
	int p = 0,res = 0;
	for(int i = 30; i >= 0; i --) {
		int u = x >> i & 1;
		if(son[p][!u]) {
			res = res * 2 + 1;
			p = son[p][!u];
		} else {
			p = son[p][u];
			res *=2;
		}
	}
	return res ;
}
int main() {
	cin.tie(0);
	cin >> n;
	idx = 0;
	for(int i = 0;i < n;i ++){
		cin >> a[i];
		insert(a[i]);
	}
	int res = 0;
	for(int i = 0;i < n;i ++ ){
		res =max(res, search(a[i]));
	}
	cout << res << endl;




	return 0;
}
 
二、堆排序
 
1.小根堆：每个点都小于等于其左右子节点。
 
2.堆的存储：用一维数组进行存储，某一点x的左节点存储在2x处，右节点存储在2x+1处。
 
3.作用：删除最小值、删除任意一个数、求最小值、插入任意一个数、修改任意一个数。
 
堆排序代码：
 
#include
#include
using namespace std;
const int N = 100010;
int h[N],siz;
void down(int x){
	int t = x ; 
	if(2 * x <= siz&&h[t] > h[2*x]) t = 2*x ;
	if(2 * x + 1 <= siz&&h[t] > h[2*x+1]) t = 2*x+1 ;
	if(t != x)
	{ 
	    swap(h[x],h[t]) ;
        down(t);
	    
	}
    
}
int main(){
	int n,m;
	cin >> n >> m;
	siz = n;
	for(int i = 1;i <= n;i ++ ) cin >> h[i];
	for(int i = n / 2;i ;i -- ) down(i)	;
	while(m --){
		cout << h[1] <<" ";
		h[1] = h[siz];
		siz--;
		down(1);
		
	}
	
	return 0;
}
 
三、一个模板题，是对dfs的一个复习，就是把全排列中的三个数换成了八个数，是对模板的复习。
 
​ ​
 
 
 
#include 
using namespace std;
int a[10];
bool book[10];
void dfs(int x){
    if(x>8){
        for(int i=1;i<=8;i++) cout <