not thing

 辗转相除法
long long g(long long a,long long b){
	if(a%b==0){
		return b;
	}
	return g(b,a%b);
}

埃氏质数
int a[11111111]
void s(){
	a[1]=1;
	for(int i=2;i*i<=11111111;i++){
		if(a[i]==0){
			for(int j=2*i;j<=11111111;j+=i){
				a[j]=1;
			}
		}
	}
}

队列《queue》
创建队列queue<int >q;
q.push(x);入队
q.pop();出队
q.front();队首
q.back();队尾
q.empty();判空
q.size();长度

前缀和
#include<bits/stdc++.h>//5 3 1 2 3 4 5 1 5 2 3 3 5
using namespace std;
	int n,a[111111],q,w,r,t,b[111111];
int main(){
	cin>>n>>r;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	b[1]=a[1];
	for(int i=2;i<=n;i++){
		b[i]=b[i-1]+a[i];
	}
	for(int i=1;i<=r;i++){
		cin>>q>>w;
		cout<<b[w]-b[q-1]<<endl;
	}
} 

差分
#include<bits/stdc++.h>//5 3 1 2 3 4 5 1 5 2 3 3 5
using namespace std;//6 3 1 2 2 1 2 1 1 3 1 3 5 1 1 6 1
	int n,a[111111],q,w,d,r,t,b[111111];
int main(){
	cin>>n>>r;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		b[i]=a[i]-a[i-1];
	}
	for(int i=1;i<=r;i++){
		cin>>q>>w>>d;
		b[q]+=d;
		b[w+1]-=d;
	}
	for(int i=1;i<=n;i++){
		a[i]=a[i-1]+b[i];
		cout<<a[i]<<" ";
	}
} 



前缀
b[i]=b[i-1]+a[i]//求前缀和数组a[],s[],用i表示某一项 
b[w]-b[q-1]//求[l,r]的和 



差分
b[i]=a[i]-a[i-1]//差分数组的构建 
b[q]+=d;//差分变化 
b[w+1]-=d;//差分变化 
a[i]=a[i-1]+b[i];//差分还原 

文件读取

 int main(){

    freopen("x.in","r",stdin);
    freopen("x.out","r",stdout);

    //代码放着 
     fclose(stdin);
     fclose(stdout);
}

深度搜索
#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,ans,t,sx,sy,fx,fy;
int dx[]={0,1,0,-1}; 
int dy[]={1,0,-1,0};
/////////右下 左上 
int mp[111][111];//地图 
bool vis[111][111];//标记 
bool f=false;
void dfs(int x,int y){//x,y==当前坐标
	vis[x][y]=1;
	if(x==fx&&y==fy){//当前在不在终点 
	f=1;
		return ;
	} 
	for(int i=0;i<4;i++){
		//下一个位置在哪
		int nx=x+dx[i];
		int ny=y+dy[i]; 
		//判断能不能走 
		if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&mp[nx][ny]==0&&vis[nx][ny]==0){
			vis[nx][ny]=1;
			
			dfs(nx,ny);
			vis[nx][ny]=0;
		}
	}
	
}
int main(){
	cin>>n>>m>>sx>>sy>>fx>>fy;
	
	dfs(sx,sy);
	
	
	
	
}





广度优先
#include<bits/stdc++.h>
using namespace std;
char mp[1111][1111];
bool vis[1111][1111];
int dx[]={0,0,1,-1};
int dx[]={1,-1,0,0};
int n,m;
struct node{
	int x,y,step;
	
}; 
void bfs(int x,int y){
	queue<node>q;
	q.push({x,y,0});
	vis[x][y]=1;
	while(!q.empty()){
		node u=q.front();
		q.pop();
		if(u.x==n&&u.y==m) {
			cout<<u.step;
			break;
		}
		for(int i=0;i<4;i++){
			node v;
			v.x=u.x+dx[i];
			v.y=u.y+dy[i];
			if(v.x>=1&&v.x<=n&&v.y>=1&&v.y<=m&&mp[v.x][v.y]=='.'&&!vis[v.x][v.y]){
				v.step=u.step+1;
				vis[v.x[v.y]=1;
			}
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>mp[i][j];
		}
	}
}


前序
 #include<bits/stdc++.h>
using namespace std;
void dfs(string md,string bh){
	if(bh.size()==0)return ;
	cout<<bh.back();//输出根 
	int id=md.find(bh.back());//找到根节点，在中序当中的位置 
	dfs(md.substr(0,id),bh.substr(0,id));//左子树；中序后序都要 
	dfs(md.substr(id+1,md.size()-id-1),bh.substr(id,bh.size()-id-1));//右子树；中序后序都要 
} 
int main(){
	string md,bh;
    cin>>md>>bh;
	dfs(md,bh);
	
}

数据体重载
struct node{
	int x,y;
	friend bool operator<(node a,node b){
		if(a.x==b.x){
		return a.x<b.x;
		}
		return a.y<b.y;
	}//类似在外面写的cmp函数，一样，调用时无需传递cmp
}a[1111];

 bool operator<(node a,node b){
		if(a.x==b.x){
		return a.x<b.x;
		}
		return a.y<b.y;

 类似在外面写的cmp函数，一样，调用时无需传递cmp迪士尼不需要写friend。而且只能用于对应的结构体。

优先队列
priority_queue<int,vector<int> > q1;//默认大优先
 priority_queue<int,vector<int>,less<int> > q2;//大优先 
 priority_queue<int,vector<int>,greater<int> > q3;//小优先
 //上述中int就是指你的存储的数据类型
 //使用方法{跟栈类似}，但是它可以自动排序时间0（logN）
 判空：empty();
 长度；size();
 队首；top();
 弹出；pop();
 入队；push(x); 
 //存储结构体，想办法让结构体也有优先级 
 priority_queue<node>q4; 
 //可以在结构体当中写入重载函数（用的比较多） 

高精度乘低精度
#include<bits/stdc++.h>
using namespace std;
string a;
long long b;

int main(){
	cin>>a,b;
	long long r=0;
		string c;
		for(int i=0;i<a.size();i++){
			r=r*10+(a[i]-'0');
			char k=r/b+'0';
			r=r%b;
			c+=k;
		}
		cout<<c<<end<<r<<endl;
		while(c[0]=='0'&&c.size()>1)c.erase(c.begin());
		cout<<c<<endl<<r<<endl;
} 

高精度乘法
#include<bits/stdc++.h>
using namespace std;
string a,b,c;

void add0(int len){
	reverse(a.begin(),a.end());
	reverse(b.begin(),b.end());
	for(int i=1;i<=len;i++)c+="0";
	
}
void mul(){
	for(int i=0;i<a.size();i++){
		for(int ii=0;ii<b.size();ii++){
			int k=i+ii;
			int num=(a[i]-'0')*(b[ii]-'0')+(c[k]-'0');
			c[k]=num%10+'0';
			c[k+1]+=num/10;
		}
	}
}
int main(){
	cin>>a>>b;
	int clen=a.size()+b.size();
	add0(clen);
	mul();
	reverse(c.begin(),c.end());
	if(c[0]=='0')c.erase(c.begin());
	cout<<c;
	
} 

哈夫曼树的构建方法：找到所有频率当中的最小两个数，构建成子树，将相加的值放回频率，直到树构建完成。
编码长度：简单理解就是路径长度
搜索效率：路径长度称以频率后相加。