算法模板

xiaoxiao2021-02-28  6

武林秘籍

头文件

#include<set> #include<cmath> #include<cstring> #include<map> #include<algorithm> #include<map> #include<sstream> #include<iostream> #include<functional> const int inf = 0x3f3f3f3f; #define inf 0x3f3f3f3f

素数筛选

//埃氏筛法 int prime[MAXNUM]; //第i个素数 bool isPrime[MAXNUM + 1]; //isPrime[i]为true表示i为素数 //返回n以内的素数个数 int sieve(int n){ int p = 0; fill(isPrime, isPrime + n + 1, true); isPrime[0] = isPrime[1] = false; for(int i = 2; i <= n; i++){ if(isPrime[i]){ prime[p++] = i; for(int j = 2*i; j <= n; j += i) isPrime[j] = false; } } return p; }

快速幂

typedef long long ll; ll modPow(ll x, ll n, ll mod){ ll res = 1; while(n > 0){ if(n & 1) res = res*x%mod; // 判断是否为奇数,若是则true x = x*x%mod; n >>= 1; } return res; }

GCD

//辗转相除法 int GCD(int a, int b){ return b == 0 ? a : GCD(b, a % b); }

全排列

bool visit[MAXNUM]; int perm[MAXNUM]; void permutation(int pos, int n){ if(pos == n){ /* 这里对perm[]操作 */ return ; } for(int i = 0; i < n; i++){ if(visit[i] == false){ visit[i] = true; permutation(pos + 1, n); visit[i] = false; } } } //在c++的标准库中已经集成了next_permutation() do{ /* 这里是对perm[]的操作 */ } while(next_permutation(perm, perm + n));

二分查找

// left为最开始元素, right是末尾元素的下一个数,x是要找的数 int bsearch(int *A, int left, int right, int x){ int m; while (left < right){ m = left + (right - left) / 2; if (A[m] >= x) right = m; else left = m + 1; // 如果要替换为 upper_bound, 改为:if (A[m] <= v) x = m+1; else y = m; } return left; } /* 最后left == right 如果没有找到135577找6,返回7 如果找有多少的x,可以用lower_bound查找一遍,upper_bound查找一遍,下标相减 C++自带的lower_bound(a,a+n,x)返回数组中最后一个x的下一个数的地址 upper_bound(a,a+n,x)返回数组中第一个x的地址 如果a+n内没有找到x或x的下一个地址,返回a+n的地址 lower_bound(a,a+n,x)-upper_bound(a,a+n,x)返回数组中x的个数 */

并查集

int findFather(int x){ return x == father[x] ? x : findFather(x); // if(x == father[x]) // return x; // else{ //压缩路径 // father[x] = findFather(x); // return father[x]; } } int merge(int v, int u){ v = findFather(v); u = findFather(u); if(u != v){ father[u] = v; return 1; } return 0; }

Dijkstra(单源最短路径)

#include<iostream> #include<algorithm> using namespace std; const int inf = 0x3f3f3f3f; int e[510][510], dis[510]; bool visit[510]; int n, m; int main(){ fill(e[0], e[0] + 510*510, inf); fill(dis, dis + 510, inf); scanf("%d%d", &n, &m); int a, b, c; for(int i = 0; i < m; i++){ scanf("%d%d%d", &a, &b, &c); e[a][b] = e[b][a] = c; } dis[1] = 0; for(int i = 0; i < n; i++){ int u = -1, minn = inf; for(int j = 1; j <= n; j++) if(visit[j] == false && dis[j] < minn){ minn = dis[j]; u = j; } if(u == -1) break; visit[u] = true; for(int v = 1; v <= n; v++) if(visit[v] == false && e[u][v] != inf){ if(dis[v] > dis[u] + e[u][v]) dis[v] = dis[u] + e[u][v]; } } for(int i = 2; i <= n; i++) printf("%d%c", dis[i], i == n ? '\n' : ' '); return 0; }

SPFA(单源最短路径解决负权)

写法一

#include<iostream> #include<algorithm> #include<queue> using namespace std; const int inf = 0x3f3f3f3f; int dis[510], head[510]; bool visit[510]; int n, m, cnt; struct node{ int u, v, w; int next; }e[510]; void add(int u, int v, int w){ e[cnt].u = u; e[cnt].v = v; e[cnt].w = w; e[cnt].next = head[u]; head[u] = cnt++; } int main(){ fill(dis, dis + 510, inf); fill(head, head + 510, -1); scanf("%d%d", &n, &m); int u, v, w; for(int i = 0; i < m; i++){ scanf("%d%d%d", &u, &v, &w); add(u, v, w); } dis[1] = 0; visit[1] = true; queue<int> q; q.push(1); while(!q.empty()){ u = q.front(); q.pop(); visit[u] = false; for(int i = head[u]; i != -1; i = e[i].next){ v = e[i].v; w = e[i].w; if(dis[v] > dis[u] + w){ dis[v] = dis[u] + w; if(visit[v] == false) visit[v] = true, q.push(v); } } } for(int i = 2; i <= n; i++) printf("%d%c", dis[i], i == n ? '\n' : ' '); }

写法二

#include<iostream> #include<map> #include<queue> #include<vector> #include<algorithm> using namespace std; const int inf = 0x3f3f3f3f; vector<pair<int, int> > e[510]; queue<int> q; int dis[510]; bool visit[510]; int main(){ int n, m; fill(dis, dis + 510, inf); scanf("%d%d", &n, &m); int u, v, w; for(int i = 0; i < m; i++){ scanf("%d%d%d", &u, &v, &w); e[u].push_back(make_pair(v, w)); } visit[1] = true; dis[1] = 0; q.push(1); while(!q.empty()){ u = q.front(); q.pop(); visit[u] = false; for(int i = 0; i < e[u].size(); i++){ v = e[u][i].first; w = e[u][i].second; if(dis[u] + w < dis[v]){ dis[v] = dis[u] + w; if(visit[v] == false) visit[v] = false, q.push(v); } } } for(int i = 2; i <= n; i++) printf("%d%c", dis[i], i == n ? '\n' : ' '); return 0; }

Floyed

#include<iostream> #include<algorithm> using namespace std; const int inf = 0x3f3f3f3f; int e[510][510]; int n, m; int main(){ fill(e[0], e[0] + 510*510, inf); scanf("%d%d", &n, &m); int u, v, w; for(int i = 0; i < m; i++){ scanf("%d%d%d", &u, &v, &w); e[u][v] = e[v][u] = w; } for(int k = 1; k <= n; k++) for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(e[i][j] > e[i][k] + e[k][j]) e[i][j] = e[i][k] + e[k][j]; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) printf("%d%c", e[i][j], j == n ? '\n' : ' '); return 0; }

Prim(最小生成树)

#include<iostream> #include<algorithm> using namespace std; struct node{ int u, v, w; bool friend operator < (const node &a, const node &b){ return a.w < b.w; } }e[510]; int n, m; int father[510]; int findFather(int x){ return x == father[x] ? x : father[x] = findFather(father[x]); } int merge(int x, int y){ x = findFather(x); y = findFather(y); if(x != y){ father[x] = y; return 1; } return 0; } int main(){ scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) father[i] = i; for(int i = 0; i < m; i++) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w); sort(e, e + m); int sum = 0, cnt = 0; for(int i = 0; i < m; i++){ if(merge(e[i].u, e[i].v)){ cnt++; sum += e[i].w; } if(cnt == n - 1) break; } printf("%d\n", sum); return 0; }

kruskal(最小生成树)

#include<iostream> #include<algorithm> using namespace std; const int inf = 0x3f3f3f3f; int e[510][510], dis[510]; bool visit[510]; int main(){ int n ,m; scanf("%d%d", &n, &m); int a, b, c; fill(dis, dis + 510, inf); fill(e[0], e[0] + 510*510, inf); for(int i = 0; i < m; i++){ scanf("%d%d%d", &a, &b, &c); e[a][b] = e[b][a] = c; } dis[1] = 0; int sum = 0; for(int i = 0; i < n; i++){ int u = -1, minn = inf; for(int j = 1; j <= n; j++){ if(visit[j] == false && dis[j] < minn){ minn = dis[j]; u = j; } } if(u == -1) break; sum += minn; visit[u] = true; for(int v = 1; v <= n; v++) if(visit[v] == false && dis[v] > e[u][v]){ dis[v] = e[u][v]; } } printf("%d\n", sum); return 0; }

线段树(区间和,修改区间,区间最大最小)

#include<iostream> #include<algorithm> using namespace std; struct node{ int l, r, max, sum; int mild(){ return (l + r)>>1; } }T[510]; int n, m; void up(int root){ T[root].sum = T[root<<1].sum + T[root<<1|1].sum; T[root].max = max(T[root<<1].max, T[root<<1|1].max); } void build(int l, int r, int root){ T[root].l = l, T[root].r = r; if(l == r){ int temp; scanf("%d", &temp); T[root].max = T[root].sum = temp; } int mild = T[root].mild(); build(l, mild, root<<1); build(mild + 1, r, root<<1|1); up(root); } void update(int root, int pos, int num){ if(T[root].l == T[root].r && T[root].r == pos){ T[root].max = T[root].sum = num; return; } int mild = T[root].mild(); if(pos <= mild) update(root<<1, pos, num); else update(root<<1|1, pos, num); up(root); } int getSum(int l, int r, int root){ if(l == T[root].l && r == T[root].r) return T[root].sum; int mild = T[root].mild(); if(r <= mild) return getSum(l, r, root<<1); else if(l > mild) return getSum(l, r, root<<1|1); else return getSum(l, mild, root<<1) + getSum(mild + 1, r, root<<1|1); } int getMax(int l, int r, int root){ if(l == T[root].l && r == T[root].r) return T[root].max; int mild = T[root].mild(); if(r <= mild) return getMax(l, r, root<<1); else if(l > mild) return getSum(l, r, root<<1|1); else return max(getMax(l, mild, root<<1), getMax(mild + 1, r, root<<1|1)) } int main(){ scanf("%d%d", &n, &m); build(1, n, 1); while(m--){ int x, y, p; scanf("%d%d%d", &p, &x, &y); if(p == 1) update(x, 1, y); else if(p == 2) printf("%d\n", getSum(x,y,1)); else printf("%d\n", getMax(x,y,1)); } return 0; }

主席树(区间第K大问题)

#include<iostream> #include<vector> #include<algorithm> using namespace std; const int N = 1e5 + 7; int root[N], a[N], cnt, x, y, k, n, m; struct node{ int l, r, sum; }T[40*N]; vector<int> v; int getid(int x){ return lower_bound(v.begin(), v.end(), x) - v.begin() + 1; } void update(int l, int r, int &x, int y, int pos){ T[++cnt] = T[y], T[cnt].sum++, x = cnt; if(l == r) return; int mild = (l + r)>>1; if(pos <= mild) update(l, mild, T[x].l, T[y].l, pos); else update(mild + 1, r, T[x].r, T[y].r, pos); } int query(int l, int r, int x, int y, int k){ if(l == r) return l; int sum = T[T[y].l].sum - T[T[x].l].sum; int mild = (l + r)>>1; if(k <= sum) return query(l, mild, T[x].l, T[y].l, k); else return query(mild + 1, r, T[x].r, T[y].r, k - sum) } int main(){ scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) scanf("%d", &a[i]), v.push_back(a[i]); sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end()); for(int i = 1; i <= n; i++) update(1, n, root[i], root[i - 1], getid(a[i])); for(int i = 0; i < m; i++){ scanf("%d%d%d", &x, &y, &k); printf("%d\n", v[query(1, n, root[x - 1], root[y], k) - 1]); } return 0; }

树状数组(区间第K大问题)

//HDU 5249 http://acm.hdu.edu.cn/showproblem.php?pid=5249 //数据过大需要采用离散化。 #include<iostream> #include<vector> #include<algorithm> #include<cstring> #include<queue> using namespace std; const int N = 1e5 + 10; #define lowbit(x) (x & -x) int c[N], a[N]; char str[N][10]; vector<int> v; int n, m; int getid(int x){ return lower_bound(v.begin(), v.end(), x) - v.begin() + 1; } void update(int x, int val){ for(int i = x; i <= n; i += lowbit(i)) c[i] += val; } int getsum(int x){ int sum = 0; for(int i = x; i >= 1; i -= lowbit(i)) sum += c[i]; return sum; } int solve(int x){ int left = 1, right = n, mid; int k = x / 2 + 1; while(left < right) { mid = (left + right) / 2; if(getsum(mid) >= k) right = mid; else left = mid + 1; } return left; } int main(){ int T = 1, x; while(~scanf("%d", &m)){ queue<int> q; memset(c, 0, sizeof(c)), v.clear(); for(int i = 1; i <= m; ++i){ scanf("%s", str[i]); if(str[i][0] == 'i'){ scanf("%d", &a[i]); v.push_back(a[i]); } } sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end()); n = v.size(); printf("Case #%d:\n",T++); for(int i = 1; i <= m; ++i){ if(str[i][0] == 'i'){ x = getid(a[i]); update(x, 1); q.push(x); }else if(str[i][0] == 'o'){ x = q.front(); update(x, -1); q.pop(); }else{ printf("%d\n", v[solve(q.size()) - 1]); } } } return 0; }

树状数组(区间和)

#include<iostream> using namespace std; int tree[510]; int n; int lowbit(int x){ return x & (-x); } void update(int x, int num){ while(x <= n){ tree[x] += num; x = lowbit(x); } } int getSum(int x){ int sum = 0; while(x > 0){ sum += tree[x]; x -= lowbit(x); } return sum; } int main(){ scanf("%d", &n); int temp; for(int i = 1; i <= n; i++){ scanf("%d", &temp); update(i, temp); } return 0; }

凸包

#include<iostream> #include<algorithm> #include<cmath> #include<vector> #define N 105 using namespace std; struct node{ int x, y; bool friend operator < (const node &a, const node &b){ if(a.y == b.y) return a.x < b.x; return a.y < b.y; } }point[N]; double calcurateDis(node a, node b){ return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y)); } bool judge(node a, node b, node c){ return (a.x - c.x)*(b.y - c.y) >= (b.x - c.x)*(a.y - c.y); } double solve(int n){ vector<node> tempPoint(n*2); sort(point, point + n); if(n ==