2022 暑 模板归纳

目录

1. 手写栈

2. 队列

3. 广度优先级搜索

4. 并查集

5. 哈希

一.手写栈

栈 的函数 s.push(x) s.pop() s.top() s.size() s.empty()

//  手写栈
int x,p=0;
int s[10000005];

void push(int x){
    s[++p] = x;
    return;
}
void pop(){
    p--;
    return;
}
int top(){
    return s[p];
}
int size(){
    return p;
}
bool empty(){
    if(p)return false;
    return true;
}
void clean(){
    p=0;
    return;
}

二.队列

队列 的函数 q.front() q.back() q.push(x) q.pop() q.empty() q.size()

示例题目 ：P1996

//p1996

queue<int> q;
int n,m,num=1;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){q.push(i);}
	while(!q.empty()){
		if(num==m){
			cout<<q.front()<<" ";
			q.pop();
			num=1;
		}
		else{
			q.push(q.front());
			q.pop();
			num++;
		}
	}
	return 0;
}

三.广度优先级搜索

示例题目 ：P1443

#include<bits/stdc++.h>
#include<queue>
#include<stack>
using namespace std;
int dx[8] = {-2,-1,1,2,2,1,-1,-2};//偏移量数组 
int dy[8] = {1,2,2,1,-1,-2,-2,-1};
int n,m,sx,sy,a[405][405];
struct pos{int x,y;}p,nxt;
queue<pos> q;
int main(){
	cin>>n>>m>>sx>>sy;
	for(int i=1;i<=n;i++)
	    for(int j=1;j<=m;j++)
	        a[i][j] = -1;//将地图初始化 
	a[sx][sy] = 0;//设置起点 
	p.x=sx , p.y=sy;//包装起点 成 结构体 方便入队 
	q.push(p); 
	while(!q.empty()){
		p = q.front();//备份当前状态 
		q.pop();//删除当前状态 
		for(int i=0;i<8;i++){//枚举下一次状态 
			int px = p.x+dx[i] , py = p.y+dy[i];
			if(px>=1 && px<=n && py>=1 && py<=m && a[px][py] == -1){
				nxt.x = px , nxt.y = py;//将可行的点坐标包装 成 结构体 
				q.push(nxt); 
				a[px][py] = a[p.x][p.y]+1;//下一次的步数 = 上一次步数+1 
			}
		}
	}
	for(int i=1;i<=n;i++){//输出 
		for(int j=1;j<=m;j++)
			cout<<a[i][j]<<" ";
		cout<<endl;
	}
	return 0;
} 

四.并查集

#include<bits/stdc++.h>
using namespace std;
int a[5005],n,m,k,a1,a2,sum;
int findx(int x){
	if(a[x]==x)return x;
	return a[x] = findx(a[x]); //优化后并查集 
}
void merge(int x,int y){
	int x1=findx(x),y1 = findx(y);//先找到他们的组长 
	if(x1==y1)return;//如果本来就有关系，那么放弃操作 
	a[x1] = y1;
}
int main(){
	while(1){
		cin>>n;
		if(n==0)return 0;
		cin>>m;
		for(int i=1;i<=n;i++)a[i]=i;
		while(m--){
			cin>>a1>>a2;
			merge(a1,a2);
		}
		for(int i=1;i<=n;i++)
		  if(a[i]==i)sum++;
		cout<<sum-1<<endl;
		sum=0;
	}
	
}

五.哈希

//哈希 示例代码 
#include<bits/stdc++.h>
#include<vector>
using namespace std;
#define mod 100007
#define k 128
vector<string> v[mod+2];
int n,x,ans;
string str;
void insert(string str){
	int hash = 1;
	for(int i=0;i<str.length();i++){
		hash = (hash * k + str[i] ) % mod;
	}
	for(int i=0;i<v[hash].size();i++){
		if(v[hash][i] == str)return;
	}
	v[hash].push_back(str);
	ans++;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>str;
		insert(str);
	}
	cout<<ans;
	return 0;
}