图论

Dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool vis[maxn];
long long dis[maxn];
typedef pair<int,int> pii;
priority_queue<int,vector<pii>,greater<pii> > q;
void findn(int a){
	memset(dis,inf,sizeof(dis));
	dis[a]=0;
	q.push(make_pair(0,a));
	while(!q.empty()){
		int s=q.top().second;q.pop();
		if(vis[s]) continue;
		vis[s]=1;
		for(int i=head[s];i;i=edge[i].next){
			int k=edge[i].to;
			if(!vis[k]&&dis[k]>dis[s]+edge[i].w){
				dis[k]=dis[s]+edge[i].w;
				q.push(make_pair(dis[k],k));
			}
		}
	}
}

SPFA

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
bool spfa(int s){
	memset(dist,inf,sizeof(dist));
	dist[s]=0;
	vis[s]=1;
	inq[s]++;
	queue<int> q;
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i = head[u];i;i = edge[i].next){
			int v = edge[i].to;
            //这边是 > 不可写成 >=
			if(dist[v] > dist[u] + edge[i].w){
				dist[v] = dist[u] + edge[i].w;
				if(!vis[v]){
					vis[v] = 1;
					inq[v] ++;
					if(inq[v] > n) return false;
					q.push(v);
				}
			}
		}
	}
	return true;
}

松弛操作不可以将 >> 写成 >=>=

Tarjan

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
int dfn[N], low[N];
int stak[N];
int vis[N];
int num, top, tot;
int color[N];
void Tarjan(int u){
	dfn[u] = low[u] = ++ tot;
	stak[++ top] = u;
	vis[u] = 1;
	for(int i = head[u]; i; i = edge[i].next){
		int v = edge[i].to;
		if(! dfn[v]){
			Tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if(vis[v]) low[u] = min(low[u], low[v]);
	}
	if(dfn[u] == low[u]){
		num ++;
		while(u != stak[top]){
			vis[stak[top]] = 0;
			color[stak[top]] = num;
			colortot[num] ++;
			top --;
		}
		vis[u] = 0;
		color[u] = num;
		colortot[num] ++;
		top --;
	}
}

//读入数据进行 Tarjan 并建立新图
for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v,1);
		x[i]=u,y[i]=v;
	}
	for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
	memset(edge,0,sizeof(edge));
	memset(head,0,sizeof(head));
	cnt=1;
	for(int i=1;i<=m;i++)
		if(color[x[i]]!=color[y[i]]) add(color[x[i]],color[y[i]],1);

注意缩点后建图时点的数量不是 nn 而是 numnum
建图时的点为 coloricolor_i 而非原来的点

LCA

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
int d[N], f[N][LN];
void bfs(){
	queue<int> Q;
	Q.push(S);
	d[S] = 1;
	while(Q.size()){
		int u = Q.front();
		Q.pop();
		for(int i = head[u]; i; i = edge[i].next){
			int v = edge[i].to;
			if(d[v]) continue;
			f[v][0] = u;
			d[v] = d[u] + 1;
			for(int j = 1; j <= t; j ++) f[v][j] = f[f[v][j - 1]][j - 1];
			Q.push(v);
		}
	}
}

int lca(int u, int v){
	if(d[u] < d[v]) swap(u, v);
	for(int i = t; i >= 0; i --)
		if(d[f[u][i]] >= d[v]) u = f[u][i];
	if(u == v) return u;
	for(int i = t; i >= 0; i --)
		if(f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
	return f[u][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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 2e5 + 15;
ll n, m;
ll ans, vis[N];
ll u[N], v[N], d[N];
struct Edge{
	ll to;
	ll next;
}edge[2 * N];

ll head[N], cnt = 1;
void add(ll u, ll v){
	edge[cnt].to = v;
	edge[cnt].next = head[u];
	head[u] = cnt ++;
}
int main(){
	scanf("%lld %lld", &n, &m);
	for(ll i = 1; i <= m; i ++){
		scanf("%lld %lld", &u[i], &v[i]);
		d[u[i]] ++, d[v[i]] ++;
	} 
	for(ll i = 1; i <= m; i ++){
		if(d[u[i]] < d[v[i]]) add(u[i], v[i]);
		if(d[u[i]] > d[v[i]]) add(v[i], u[i]);
		if(d[u[i]] == d[v[i]]){
			if(u[i] > v[i]) swap(u[i], v[i]);
			add(u[i], v[i]);
		}
	}
	for(ll i = 1; i <= n; i ++){
		for(ll j = head[i]; j; j = edge[j].next) vis[edge[j].to] = 1;
		for(ll j = head[i]; j; j = edge[j].next){
			ll v = edge[j].to;
			for(ll k = head[v]; k; k = edge[k].next){
				ll v2 = edge[k].to;
				if(vis[v2]) ans ++;
			}
		}
		for(ll j = head[i]; j; j = edge[j].next) vis[edge[j].to] = 0;
	}
	printf("%lld", ans);
	return 0;
}

动态规划

单调队列优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
memset(f, -0x3f3f3f3f, sizeof(f));
memset(q, 0, sizeof(q));
f[0] = 0;
for(int i = 1; i <= n; i ++){
	while(dist[i] - dist[cur] >= l){
		if(f[cur] != -0x3f3f3f3f){
			while(head <= tail && f[cur] >= f[q[tail]])tail --; 
			q[++ tail] = cur;
		}
			cur ++;
	}
	while(head <= tail && dist[i] - dist[q[head]] > r) head ++;
	if(head <= tail) f[i] = f[q[head]] + val[i];
	else f[i] = -0x3f3f3f3f;
}

数据结构

单调队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+15;
int a[N];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    deque<int> q;
    for(int i=1;i<=n;i++){
	while(!q.empty()&&i-q.front()>=m) q.pop_front();
	while(!q.empty()&&a[q.back()]>a[i]) q.pop_back();
	q.push_back(i);
	if(i>=m) printf("%d ",a[q.front()]);
    }
    return 0;
}

线段树

P3372 【模板】线段树 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
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 15;
int n, m;
int a[N];
struct Tree{
	int l, r;
	int val;
	int num;//记录当前加了多少 
}T[N << 2];
void build(int pos, int l, int r){
	T[pos].l = l, T[pos].r = r;
	if(l == r){
		T[pos].val = a[l];
		return ;
	}
	int mid = (l + r) >> 1;
	build(pos << 1, l, mid);
	build(pos << 1 | 1, mid+1, r);
	T[pos].val = T[pos << 1].val + T[pos << 1 | 1].val;
}
void spread(int pos){
	//懒标记（缓存）下放操作 
	if(T[pos].num){
		T[pos << 1].val += T[pos].num * (T[pos << 1].r - T[pos << 1].l + 1);
		T[pos << 1 | 1].val += T[pos].num * (T[pos << 1 | 1].r - T[pos << 1 | 1].l + 1);
		T[pos << 1].num += T[pos].num;
		T[pos << 1 | 1].num += T[pos].num;
		T[pos].num = 0;
	}
}
void update(int pos, int x, int y, int k){
	if(x <= T[pos].l && y >= T[pos].r){
		T[pos].val += k * (T[pos].r - T[pos].l + 1);
		T[pos].num += k;//数值又加了 k 
		return ;
	}
	spread(pos);
	int mid = (T[pos].r + T[pos].l) >> 1;
	if(x <= mid) update(pos << 1, x, y, k);
	if(y > mid) update(pos << 1 | 1, x, y, k);
	T[pos].val = T[pos << 1].val + T[pos << 1 | 1].val;
}
int query(int pos, int x, int y){
	int res = 0;
	if(x <= T[pos].l && y >= T[pos].r) return T[pos].val; 
	spread(pos);
	int mid = (T[pos].r + T[pos].l) >> 1;
	if(x <= mid) res += query(pos << 1, x, y);
	if(y > mid) res += query(pos << 1 | 1, x, y);
	return res; 
}
int main(){
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
	build(1, 1, n);
	for(int i = 1; i <= m; i ++){
		int c, x, y, k;
		scanf("%d %d %d", &c, &x, &y);
		if(c == 1){
			scanf("%d", &k);
			update(1, x, y, k);
		}
		else printf("%d\n", query(1, x, y));
	}
	return 0;
}

数学

筛法

1
2
3
4
5
6
7
8
9
10
11
int judge[N], prime[N];
int cnt = 1;
void Eluer(){
	for(int i = 2; i <= N; i ++){
		if(!judge[i]) prime[cnt ++] = i;
		for(int j = 1; j <= cnt - 1 && prime[j] * i <= N; j ++){
			judge[prime[j] * i] = 1;
			if(i % prime[j] == 0) break;
		}
	}
}

矩阵乘法

1
2
3
4
5
6
7
8
9
node Matrix_mul(node A,node B){
	node C;
	memset(C.matrix,0,sizeof(C.matrix));
	for(int i=1;i<=3;i++) 
		for(int j=1;j<=3;j++)
			for(int k=1;k<=3;k++)
				C.matrix[i][j]=(C.matrix[i][j]+A.matrix[i][k]*B.matrix[k][j])%mod;
	return C;
}

前缀和

二维前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 15;
int mapn[N][N],f[N][N];
int n, m;
int val(int x1, int y1, int x2, int y2){
	return f[x2][y2] + f[x1 - 1][y1 - 1] - f[x1 - 1][y2] - f[x2][y1 - 1];
}
int main(){
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i ++)
		for(int j = 1; j <= m; j ++) scanf("%d", &mapn[i][j]);
	for(int i = 1; i <= n; i ++)
		for(int j = 1; j <= m; j ++)
			f[i][j] = f[i - 1][j] + f[i][j - 1] + mapn[i][j] - f[i - 1][j - 1];
	while(true){
		int x1, y1, x2, y2;
		scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
		printf("%d", val(x1, y1, x2, y2));
	}
	return 0;
}

异或前缀和

由异或性质可得 (a ^ b) ^ b = a
则区间 [l,r][l,r] 的异或前缀和为 xorpre[r]xorpre[r] ^ xorpre[l−1]xorpre[l - 1]

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 15;
int w[N],xorpre[N];
int n;
int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++){
		scanf("%d", &w[i]);
		xorpre[i] = xorpre[i - 1] ^ w[i];
	}
	return 0;
}

高精度

高精加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
string add(string s1, string s2){
	int a[N], b[N], c[N];
	memset(a, 0, sizeof(a));
	memset(b, 0, sizeof(b));
	memset(c, 0, sizeof(c));
	for(int i = 0; i < s1.size(); i ++) a[s1.size() - i] = s1[i] - 48;
	for(int i = 0; i < s2.size(); i ++) b[s2.size() - i] = s2[i] - 48;
	int lenc = 1, x = 0;
	while(lenc <= s1.size() || lenc <= s2.size()){
		c[lenc] = a[lenc] + b[lenc] + x;
		x = c[lenc] / 10;
		c[lenc] %= 10;
		lenc ++;
	}
	if(x != 0) c[lenc] = x;
	else lenc --;
	string ans;
	for(int i = lenc; i >= 1; i --) ans += (char)(c[i] + 48);
	return ans;
}

高精乘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
string mul(string s1, string s2){
	int a[N], b[N], c[N];
	memset(a, 0, sizeof(a));
	memset(b, 0, sizeof(b));
	memset(c, 0, sizeof(c));
	for(int i = 0; i < s1.size(); i ++) a[s1.size() - i] = s1[i] - 48;
	for(int i = 0; i < s2.size(); i ++) b[s2.size() - i] = s2[i] - 48;
	for(int i = 1; i <= s1.size(); i ++){
		int x = 0;
		for(int j = 1; j <= s2.size(); j ++){
			c[i + j - 1] += a[i] * b[j] + x;
			x = c[i + j - 1] / 10;
			c[i + j - 1] %= 10;
		}
		c[i + s2.size()] = x;
	}
	int lenc = s1.size() + s2.size();
	while(c[lenc] == 0 && lenc > 1) lenc --;
	string ans;
	for(int i = lenc; i >= 1; i --) ans += (char)(c[i] + 48);
	return ans;
}

其它

快读 & 快写

1
2
3
4
5
6
7
8
9
10
11
12
13
inline int read(){
	int x=0,cf=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') cf=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*cf;
}

inline void out(int x){
    if(x<0){putchar('-');x=-x;}
    if(x>=10) out(x/10);
    putchar(x%10+'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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inti int
const int N = 5e5 + 15;
ll tree[N << 2];
ll n, a[N], d[N];

ll lowbit(ll x){
	return x & (-x);
}

void add(ll x, ll k){
	while(x <= n){
		tree[x] += k;
		x += lowbit(x);
	}
}

ll getsum(ll x){
	ll ans = 0;
	while(x != 0){
		ans += tree[x];
		x -= lowbit(x);
	}
	return ans;
}

bool cmp(ll x, ll y){
	if(a[x] == a[y]) return x > y;
	return a[x] > a[y];
}


int main(){
	scanf("%lld", &n);
	for(int i = 1; i <= n; i ++){
		scanf("%lld", &a[i]);
		d[i] = 1LL * i;
	} 
	sort(d + 1, d + 1 + n, cmp);
	ll ans = 0;
	for(int i = 1; i <= n; i ++){
		add(d[i], 1LL);
		ans += getsum(d[i] - 1LL);
	}
	printf("%lld", ans);
	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
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+15;
int a[N],t[N];
long long ans=0;
int n;
void Merge(int l,int r){
    if(l>=r) return;
    int mid=(l+r)/2,k=l;
    Merge(l,mid),Merge(mid+1,r);
    int i=l,j=mid+1;
    while(i<=mid&&j<=r){
	if(a[i]<=a[j]) t[k++]=a[i++];
	else{
	    t[k++]=a[j++];
	    ans+=(mid-i+1); // ans 为逆序对个数
	}
    }
    while(i<=mid) t[k++]=a[i++];
    while(j<=r) t[k++]=a[j++];
    for(int i=l;i<=r;i++) a[i]=t[i];
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    Merge(1,n);
    printf("%lld",ans);
    return 0;
}