只因础算法总结

中分二分

二分查找模板

#include<bits/stdc++.h>
#define maxn 1000000+10
#define f_u(a,b) for(register int i=a;i<=b;++i)
#define f_d(a,b) for(register int i=a;i>=b;--i)
#define F_u(a,b) for(register int j=a;j<=b;++j)
#define F_d(a,b) for(register int j=a;j>=b;--j)
using namespace std;
inline int read(){register char c=getchar();register int x=0,s=1; while(c<'0'||c>'9'){if(c=='-')s=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}return x*s;}
inline void write(int x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');}
int n,m,a[maxn];
int zhong_fen(int k){
	register int l=1,r=n,mid;
	while(l<r){
		mid=(l+r)/2;
		if(a[mid]>=k){
			r=mid;
		}
		else{
			l=mid+1;
		}
	}
	if(a[l]!=k) return -1;
	return l;
}
int main(){
//	ios_base::sync_with_stdio(false);
	n=read(),m=read();
	f_u(1,n) a[i]=read();
	f_u(1,m){
		register int tmp=read();
		cout<<zhong_fen(tmp)<<' ';
	} 
	cout<<endl;
	return 0;
}

贪心

快速幂

主要就是靠$a^k =a^a p $的这个定理

排序类

归并排序

算法思想：使用多次分解来使多个子问题有序，再合并多个有序子序列

用处：多用于求逆序对

实现：

#include<bits/stdc++.h>
#define maxn 100000+10
using namespace std;
long long b[maxn],n,ans=0;
void merge_sort(int l,int r){
	if(l>=r) return;
	int mid=(l+r)>>1;
	merge_sort(l,mid);
	merge_sort(mid+1,r);
	int i=l,j=mid+1,k=l,tmp[maxn];
	while(i<=mid&&j<=r)
		if(b[i]<=b[j])tmp[k++]=b[i++];
		else tmp[k++]=b[j++],ans+=mid-i+1;
	while(i<=mid)tmp[k++]=b[i++];
	while(j<=r)tmp[k++]=b[j++];
	for(i=l;i<=r;i++)b[i]=tmp[i];
}
int main(){
	ios_base::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>b[i];
	merge_sort(1,n);
	for(int i=1;i<=n;i++) cout<<b[i]<<' ';
	cout<<endl<<ans<<endl;
	return 0;
} 

答案第一行为排序好的数，第二行为逆序对个数

树与图

树

树是一种连通图，且每一个节点都只有一个前驱

存储方法：

1. 用一维数组存储每个节点的前驱

2. 用二维数组存储后继

3. 用结构体存储前驱和后继

4. 用其他奇奇怪怪的方法

图

图是由带（或不带）边权的边连接多个节点的结构

最小生成树：去掉一些边，使图由n-1条边链接成一个联通的新图

方法：排序，遍历，判断是否为同集，并查集

最短路：从一个点到另一个点的通过边权最小的路径

方法：

1. floyd:三层循环枚举中转点，起点，终点O(n³)

2. dijkstra: