算法竞赛模板

本文最后更新于:2020年9月28日 晚上

一、基础

1. 二分

1. 二分查找

具有单调性的一组数据

1. 整数二分查找

//有序的两种属性A,B
while(L < R){	//左边界的右端点
	int mid = L + R + 1 >> 1;
	if(mid A) L = mid;
  else R = mid - 1;
}

while(L < R){	//右边界的左端点
  int mid = L + R >> 1;
  if(mid B) R = mid;
  else L = mid + 1;
}

2. 实数二分查找

//求根
while(L - R > 1e-6){	//精度1e-4(多取两位)
	double mid = (L + R) / 2;
  if() L = mid;
  else R = mid;
}

其他: 三分

单峰图像的函数

2.排序

快速排序

void qs(int l, int r) {
  if (l >= r) return;
  int x = a[l + r >> 1];
  int i = l - 1, j = r + 1;
  while (i < j) {
    while (a[++i] < x);
    while (a[--j] > x);
    if (i < j) swap(a[i], a[j]);
  }
  qs(l, j);
  qs(j + 1, r);
}

归并排序

void ms(int l, int r) {
  if (l >= r) return;
  int mid = l + r >> 1;
  ms(l, mid);
  ms(mid + 1, r);
  int i = l, j = mid + 1, k = l;
  while (i <= mid && j <= r)
    tmp[k++] = a[i] < a[j] ? a[i++] : a[j++];
  while (i <= mid) tmp[k++] = a[i++];
  while (j <= r) tmp[k++] = a[j++];
  for (int i = l; i <= r; ++i) a[i] = tmp[i];
}

堆排序

#include <iostream>
using namespace std;
const int N = 1e5 + 10;

int h[N], cnt, n, m;

void down(int u) {
  int t = u, uu = u << 1;
  if (uu <= cnt && h[uu] < h[t]) t = uu;
  if (uu +1 <= cnt && h[uu + 1] < h[t]) t = uu + 1;
  if (t != u) {
    swap(h[t], h[u]);
    down(t);
  }
}

int main(){
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) scanf("%d", &h[i]);
  cnt = n;
  for (int i = n >> 1; i ; --i) down(i);
  
  while (m--) {
    printf("%d ", h[1]);
    h[1] = h[cnt--];
    down(1);
  }
  return 0;
}

二、数论

1. 素数打表

埃氏筛

//在primes中值为true的是合数 
bool primes[MAXN] = {1, 1, 0};

void eraSieve(int n){
	for(int i = 2; i * i < n; ++i)
		if(!primes[i])							//i为素数
			for(int j = i * i; j <= n; j += i)	//标记i的倍数为合数
				primes[j] = 1;
}

欧拉筛

int primes[MAXN];		//0~N内的素数集合 

void eulerSieve(int n){
	int sum = 0;		//已经找到的素数的数量 
	bool flag[MAXN] = {false};		//标记是否为合数  
	for(int i = 2; i <= n; ++i){
		if(!flag[i])
			primes[sum++] = i;
		for(int j = 0; i * primes[j] <= n; ++j){
			flag[i * primes[j]] = true;		//标记素数的倍数为合数 
			if(i % primes[j] == 0) break;	//primes[j]同时是i和i*primes[j]的最小质因数 
		}
	}
}

2. 欧拉函数

公式法

//欧拉函数公式:euler(x) = x * (1 - 1 / p1)...(1 - 1 / pn)    p为x的质因数 
int Euler(int n){
     int ans = n;  
     for(int i = 2; i * i <= n; ++i){  
         if(n % i == 0){  
             ans = ans / i * (i - 1);//先进行除法是为了防止中间数据的溢出   
             while(n % i == 0) n /= i;  
         }  
     }  
     if(n > 1) ans = ans / n * (n - 1);  
     return ans;  
}

打表法

void Euler(){
	euler[1] = 1;
	for(int i = 2; i < MAXN; ++i)
		euler[i] = i;
	for(int i = 2; i < MAXN; ++i)
		if(euler[i] == i)
			for(int j = i; j < MAXN; j += i)
				euler[j] = euler[j] / i * (i - 1);
}

三、图论

1. 链式前向星

//存储结构 
struct Edge{
	int to;		//边的终点 
	int w;		//边的起点 
	int next;	//同起点的下一条边 
}edge[M]; 		//M为边的最大数,N为点的 
int cnt;		//使用cnt来计数 
int head[N];	//存储点,用来索引每个点下边的分布 

//初始化 
cnt = 0;		//计数0 
memset(head, -1, sizeof(head));	//head为存储点,将head的值设为-1 

//添加边 
void addEdge(int u, int v, int w){	//u v w 分别表示起点 终点 权值 
	edge[cnt].to = v;		//记录终点 
	edge[cnt].w = w;		//记录权值 
	edge[cnt].next = head[u];	//将构造好的边放进对应的head 
	head[u] = cnt++;	//	更新head和cnt 
} 

//遍历以u为起点的每一条边 
for(int i = head[u]; ~i; i = edge[i].next){
	int to = edge[i].to;
	int w = edge[i].w; 
} 

2.最短路

1) Dijkstra

const int INF = 0x3f3f3f3f;	//距离最大值 
const int MAXN = 1010; 		//点数量最大值
int edge[MAXN][MAXN];		//临界矩阵存图
bool vis[MAXN];				//记录该点是否使用
int dis[MAXN];				//记录单元最短距离 
int path[MAXN];				//最短路经过的路径
int cnt;					//记录路径个数 
int t, n; 					//t n 分别表示边数和点数 

void Dijkstra(int s, int e){		//s e分别表示起始结束点 
	//初始化 
	memset(vis, false, sizeof(vis));
	memset(dis, INF, sizeof(dis));
	cnt = 0;
	dis[s] = 0;
	//开始找 
	for(int i = 1; i <= N; ++i){
		//找出dis中距离最小的点 
		int tmp = INF, k = -1;
		for(int j = 1; j <= N; ++j){
			if(!vis[j] && dis[j] < tmp){
				k = j;
				tmp = dis[j];
			}
		}
		vis[k] = true;
		path[cnt++] = k;
		if(k == e) return;
		//更新dis 
		for(int j = 1; j <= N; ++j){
			if(!vis[j]){
				dis[j] = min(dis[k] + edge[k][j], dis[j]); 
			}
		}
	}
} 

四、 串

1. 字典树 Trid

struct trie {
  int nex[100000][26], cnt;
  bool exist[100000];  // 该结点结尾的字符串是否存在

  void insert(char *s, int l) {  // 插入字符串
    int p = 0;
    for (int i = 0; i < l; i++) {
      int c = s[i] - 'a';
      if (!nex[p][c]) nex[p][c] = ++cnt;  // 如果没有,就添加结点
      p = nex[p][c];
    }
    exist[p] = 1;
  }
  bool find(char *s, int l) {  // 查找字符串
    int p = 0;
    for (int i = 0; i < l; i++) {
      int c = s[i] - 'a';
      if (!nex[p][c]) return 0;
      p = nex[p][c];
    }
    return exist[p];
  }
};

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!