欧拉筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int N=1e8+10;
int primes[N],cnt; // 存放质数
bool st[N];		// 当前数是否被筛过
int minp[N];// 保存最小质因子
int get_primes(int n){
    for(int i=2;i<=n;i++){
        if(!st[i]){	// 若i没有被筛去，此时i一定是质数
            minp[i]=i;	// i的最小质因子是i
            primes[cnt++]=i;	// 将i保存在primes数组里面
        }
        for(int j=0;i*primes[j]<=n && j<=cnt;j++){
            int t=primes[j]*i; // 得到质数的倍数
            st[t]=true;
            minp[t]=primes[j];
            if(i%primes[j]==0) break;
        }
    }
}

埃氏筛

1
2
3
4
5
6
7
8
9
10
void prime(int n){
    for(int i=2;i<=n;i++) is_prime[i]=1;
    for(int i=2;i<=n;i++){
        if(is_prime[i]){
            for(int j=2;i*j<=n;j++){
				is_prime[i*j]=0;
            }
        }
    }
}

运算符重载

1
2
3
4
5
6
bool operator < (const PP p1) const {
    return (a>p1.a||( p1.a==a && p1.b<=b))? false:true;
}
bool operator >( const PP p1) const{
    return (a>p1.a||( p1.a==a && p1.b<=b))? true:false;
}

二分查找

1
2
3
4
5
6
7
8
9
10
11
int l=1,r=len,pos=0;
while(l<r){
    int mid=(l+r)>>1;
    if(d[mid]<nums[i]){
        pos=mid;
        l=mid+1;
    }else{
        r=mid-1;
    }
    d[pos+1]=nums[i];
}

树状数组

一般用来区间查询和单点修改

1
2
3
4
5
6
7
8
9
10
11
12
13
int add_dandian(int x,int k){
    for(int i=x;i<=n;i+=lowbit(i)){
        t[i]+=k;
    }
}

int ask(int x){
    int sum=0;
    for(int i=x;i>0;i-=lowbit(x)){
        sum+=t[i];
    }
    return sum;
}

Floyd算法

1
2
3
4
5
6
for(int k=1;k<=n;k++){
    for(int x=1;x<=n;x++){
        for(int y=1;y<=n;y++)
            f[x][y]=min(f[x][y],f[x][k]+f[k][y]);
    }
}

Dijkstra算法

暴力解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct edge{
    int v,w
};
vector<edge>e[maxn];
int dis[maxn],vis[maxn];

void dijkstra(int n,int s){
    memset(dis,63,sizeof(dis));
    dis[s]=0;
    for(int i=1;i<=n;i++){
        int u=0,mind=0x3f3f3f3f;
        for(int j=1;j<=n;j++){
            if(!vis[j] && dis[j]<mind) u=j,mind=dis[j];
        } // 先找到距离原点最近的那个点
        vis[u]=true;
        for(auto ed:e[u]){
            int v=ed.v,w=ed.w;
            if(dis[v]>dis[u]+w) dis[v]=dis[u]+w;
        }// 由于新加入了一个点，更新其他点到原点的距离。
    }
}

优先队列解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
struct edge{
    int v,w;
};
struct node{
    node();
    node(int _dis=0,int _u=0):u(_u),dis(_dis){}
    int dis,u;

    bool operator > (const struct node& a) const{
        return dis>a.dis;
    }
}
vector<edge>e[maxn];
int vis[maxn],dis[maxn];

priority_queue<node,vector<node>,greater<node> >q;
void dijkstra(int n,int s){
    memset(dis,63,sizeof(dis));
    dis[s]=0;
    q.push({0,s});
    while(!q.empty()){
        int u=q.top().u;
        q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(auto ed:e[u]){
            int v=ed.v,w=ed.w;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                q.push({dis[v],v});
            }
        }
    }

}

树的直径

dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<iostream>
#include <vector>
#include <stdio.h>
#include<cstdlib>
#include<cstring>
#include <utility>
using namespace std;
const int N=10000+10;

int n,c,d[N];
vector<int> E[N];
vector< pair<int,int> >EE[N];
void dfs(int u,int fa){
    for(int v:E[u]){
        if(v==fa) continue;
        d[v]=d[u]+1;
        if(d[v]>d[c]) c=v;
        dfs(v,u);
    }
}
void dfs2(int u,int fa){
    for(pair<int,int> ed :EE[u]){
        if(ed.first==fa) continue;
        d[ed.first]=d[u]+d[ed.second];
        if(d[ed.first]>d[c]){
            c=ed.first;
        }
        dfs(ed.first,u);
    }
}
int main(){
    memset(d,0,sizeof(d));
    cin>>n;
    for(int i=1;i<=n;i++){
        int u,v;
        cin>>u>>v;
        E[u].push_back(v);
        E[v].push_back(u);
    }
    dfs(1,0);
    memset(d,0,sizeof(d));
    d[c]=0;
    dfs(c,0);
    cout<<d[c]<<endl;
    return 0;
}

dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<stdio.h>
#include <string>
#include<utility>
#include<vector>
#include<algorithm>
using namespace std;

const int N=1000+4;

int n,d=0;
int d1[N],d2[N];
vector<int>E[N];

void dfs(int u,int fa){
    d1[u]=d2[u]=0;
    for(int v: E[u]){
        if(v==fa) continue;
        dfs(v,u);
        int t=d1[v]+1;
        if(t>d1[u]){
            d2[u]=d1[u],d1[u]=t;
        }else if(t>d2[u]){
            d2[u]=t;
        }
    }
    d=std::max(d,d1[u]+d2[u]);
}
int main(){
    pair<int,int> a=make_pair(1,2);
    
    cin>>n;
    while(n--){
        int u,v;
        cin>>u>>v;
        E[u].push_back(v),E[v].push_back(u);
    }
    dfs(1,0);
    cout<<d;
    return 0;
}

8皇后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<iostream>
using namespace std;
const int N=20;
int n;
int path[N];
char g[N][N];
bool col[N],dg[N],udg[N],row[N];
void dfs(int u){
    if(u==n){
        for(int i=0;i<n;i++) puts(g[i]);
        puts("");
        return ;
    }
    for(int i=0;i<n;i++){
        if(!col[i]&& !dg[u+i]&&!udg[-u+i+n]){
            g[u][i]='Q';
            col[i]=dg[u+i]=udg[n-u+i]=true;
            dfs(u+1);
            col[i]=dg[u+i]=udg[n-u+i]=false;
            g[u][i]='.';
        }
    }
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            g[i][j]='.';
    dfs(0);
    return 0;
}

void dfs2(int x,int y,int s){
    if(y==n) y=0,x++;
    if(x==n){
        if(s==n){
            for(int i=0;i<n;i++) puts(g[i]);
            puts("");
        }
        return ;
    }

    dfs2(x,y+1,s);
    if(!row[x]&&!col[y]&&!dg[x+y] && !udg[x-y+n]){
        g[x][y]='Q';
        row[x]=col[y]=dg[x+y]=udg[x-y+n]=true;
        dfs2(x,y+1,s+1);
        row[x]=col[y]=dg[x+y]=udg[x-y+n]=true;
        g[x][y]='.';
    }
}

kmp算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// p[1,j]=p[i-j+1,i]
// next[i]=j


#include <iostream>

using namespace std;

const int N=1e5+10,M=1e6+10;

int n,m;
char p[N],s[M];

int next1[N];//next[i] 表示使字串 s[0…i] 中前缀 s[0…k] 等于后缀 s[i-k…i] 的最大的 k。

int main(){
    cin>> n ;
    cin>>(p+1);
    cin>>m;
    cin>>(s+1);

    // 求next
    for(int i=2,j=0;i<=n;i++){
        while(j&&p[i]!=p[j+1]) j=next1[j];
        if (p[i]==p[j+1]) j++;
        next1[i]=j;
    }

    for(int i=1,j=0;i<=m;i++){
        while(j && s[i]!=p[j+1]) j=next1[j];
        if(s[i]==p[j+1]) j++;
        if(j==n) {
            // 匹配成功
            j=next1[j];
        }
    }
}

// p=ababababab
// next[1]=0 从0开始
// next[2]=0
// next[3]=1
// 后缀和前缀相等

快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
long long int quik_power(int base, int power, int p)
{
	long long int result = 1;   
	while (power > 0)           
	{
		if (power & 1)         							
			result = result * base % p;   
			//根据公式每个项都取余数后在再做累乘
		base = base * base % p ;   
			//根据公式每个项都取余数后在再做平方操作      						
		power >>= 1;         						
	}
			//根据公式在最后的的结果上再来一次取余数
	return result % p;       
}

读入一行拆开

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<cstring>
#include<iostream>
#include<stdio.h>
#include <sstream>
using namespace std;

int main(){
    string s;
    string tmp;
    getline(cin,s);
    stringstream ss(s);
    while(getline(ss,tmp,' ')){
        cout<<tmp<<endl;

    }
    return 0;
}
// 1 2 3 4
// 1
// 2
// 3
// 4

线段树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=1e5+10;
int a[maxn+2];
struct tree{
    int l,r;
    long long val,add;
}t[4*maxn+2];

void build(int p,int l,int r){
    t[p].l=l;
    t[p].r=r;
    if(l==r){
        t[p].val=a[l];
        return;
    }

    int mid=l+r>>1;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    t[p].val=t[p*2].val+t[p*2+1].val;
}

void spread(int p){
    if(t[p].add){
        t[p*2].val+=t[p].add*(t[p*2].r-t[p*2].l+1);
        t[p*2+1].val+=t[p].add*(t[p*2+1].r-t[p*2+1].l+1);
        t[p*2].add+=t[p].add;
        t[p*2+1].add+=t[p].add;
        t[p].add=0;

    }
}


void change(int p,int x,int y,int z){
    if(x<=t[p].l && y>=t[p].r){
        t[p].val+=(long long)z*(t[p].r-t[p].l+1);
        t[p].add+=z;
        return;
    }

    spread(p);
    int mid=t[p].l+t[p].r>>1;
    if(x<=mid)change(p*2,x,y,z);
    if(y>mid) change(p*2+1,x,y,z);
    t[p].val=t[p*2].val+t[p*2+1].val;
}

long long ask(int p,int x,int y){
    if(x<=t[p].l && y>=t[p].r){
        return t[p].val;
    }
    spread(p);
    int mid=t[p].l+t[p].r>>1;
    long long ans;
    if(x<=mid) ans+=ask(p*2,x,y);
    if(y>mid) ans+=ask(p*2+1,x,y);
    return ans;
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);
    int q,x,y,z;
    for(int i=1;i<=m;i++){
        scanf("%d",&q);
        if(q==1){
            cin>>x>>y>>z;
            change(1,x,y,z);
        }else{
            cin>>x>>y;
            cout<<ask(1,x,y)<<endl;
        }
    }
    return 0;
}

二进制优化

1
2
3
4
5
6
7
8
9
for(int i=1;i<=c;i=i<<1){
    // 存下来i
    c=c-i;
}
if(c){
    // 存下来
}
7=1+2+4
8=1+2+4+1

最大流

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
const int N = 1000 + 10;
const int M = 10000 + 10;
const int inf = 0x3f3f3f3f;
int n, m, s, t, tot = 1;
int vis[N], pre[N], head[M<<1];
struct Edge
{
	int to, next, cap, flow;
}e[M<<1];
void add(int a, int b, int c)
{
	e[++tot].cap = c; e[tot].flow = 0; e[tot].to = b; e[tot].next = head[a]; head[a] = tot;
	e[++tot].cap = 0; e[tot].flow = 0; e[tot].to = a; e[tot].next = head[b]; head[b] = tot; 
}
bool bfs(int s, int t)
{
	memset(pre, -1, sizeof pre);
	memset(vis, 0, sizeof vis);
	queue<int> q;
	vis[s] = 1; 
	q.push(s);
	while(!q.empty())
	{
		int u = q.front();
		q.pop();
		for(int i = head[u]; ~i; i = e[i].next)
		{
			int v = e[i].to;
			if(!vis[v] && e[i].cap > e[i].flow)
			{
				vis[v] = 1;
				pre[v] = i;
				q.push(v);
				if(v == t) return 1;
			}
		}
	}
	return 0;
}
int EK(int s, int t)
{
	int maxflow = 0;
	while(bfs(s, t))
	{
		int d = inf;
		int v = t;
		while(v != s)
		{
			int i = pre[v];
			d = min(d, e[i].cap - e[i].flow);
			v = e[i^1].to;
		}
		maxflow += d;
		v = t;
		while(v != s)
		{
			int i = pre[v];
			e[i].flow += d;
			e[i^1].flow -= d;
			v = e[i^1].to;
		}
	}
	return maxflow;
}
int main()
{
	memset(head, -1, sizeof head);
	cin>>n>>m>>s>>t;
	while(m--)
	{
		int a, b, c; cin>>a>>b>>c;
		add(a, b, c);
	}
	cout<<EK(s, t);
	return 0;
}

多层图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
const int maxn=20000*11+5;
const int maxm=50000*11+5;
long long dis[maxn];
int vis[maxn];
int n,m,k,s,t;
struct edge{
    int to;
    int w;
    edge(){};
    edge(int _to,int _w):to(_to),w(_w){};
};
vector<struct edge>e[maxm];
struct node{
    node(){};
    node(long long _dis,int _u):v(_u),dis(_dis){};
    int v;
    long long dis;
    bool operator > (const struct node a)const{
        return dis>a.dis;
    }
};
priority_queue<struct node,vector<node>,greater<struct node> >pq;
void dijsktra(int s){
    //cout<<endl;
    dis[s]=0;
    pq.push({0,s});
    //vis[s]=1;
    while(!pq.empty()){
        
        int u=pq.top().v;
        //cout<<u<<endl;
        pq.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(auto ed:e[u]){
            int v=ed.to;
            if(dis[v]>dis[u]+ed.w){
                dis[v]=dis[u]+ed.w;
                pq.push({dis[v],v});
            }
        }
    }
}
void add_edge(int s,int to,int w){
    struct edge tmp(to,w);
    e[s].push_back(tmp);
}
int main(){
    cin>>n>>m>>k>>s>>t;
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    for(int i=1;i<=m;i++){
        int t1,t2,w;
        cin>>t1>>t2>>w;
        add_edge(t1,t2,w);
        add_edge(t2,t1,w);
        for(int i=1;i<=k;i++){
            add_edge(t1+(i-1)*n,t2+(i)*n,0);
            add_edge(t2+(i-1)*n,t1+(i)*n,0);
            add_edge(t1+(i)*n,t2+(i)*n,w);
            add_edge(t2+(i)*n,t1+(i)*n,w);
        }
    }
    for(int i=1;i<=k;i++) add_edge(t+(i-1)*n,t+i*n,0);
    dijsktra(s);
    cout<<dis[t+n*k]<<endl;
    return 0;
}

ref:

  1. 线性筛法(欧拉筛) C++ 模板_线性筛模板-CSDN博客
  2. https://oi-wiki.org/graph/shortest-path/#floyd-%E7%AE%97%E6%B3%95
  3. 快速幂算法 超详细教程-CSDN博客