2X岁，是学生です

0%

发表于 分类于
本文字数： 2.3k 阅读时长 ≈ 2 分钟

二分图

本文时间复杂度中: $n$ 为节点数， $m$ 为边数。

二分图

点集 $V$ 可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻。

当且仅当图中不含奇数环（环当中边的数量为奇数）时，才有可能是二分图。

染色法 $O(n + m)$

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
#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e5 + 10, M = 2e5 + 10;
int h[N], e[M], ne[M], idx = 1;
int n, m;
int colors[N];

void myadd(int u, int v)
{
    e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}

bool dfs(int u, int c)
{
    colors[u] = c;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int v = e[i];
        if (!colors[v])//先判断是否上过色，没上过色先用dfs上色
        {
            if (!dfs(v, 3 - c))//“3进制”
                return false;
        }
        else if (colors[u] == colors[v])//已上过色，直接比较颜色，这里还能处理掉自环
            return false;
    }
    return true;
}

int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d%d", &n, &m);
    while (m--)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        myadd(u, v), myadd(v, u);
    }
    memset(colors, 0, sizeof(colors));
    bool flag = true;
    for (int i = 1; i <= n; ++i)//遍历，防止有不连通的点染不上色
    {
        if (!colors[i])
        {
            if (!dfs(i, 1))
            {
                flag = false;
                break;
            }
        }
    }
    if (flag)
        puts("Yes");
    else
        puts("No");
    return 0;
}

匈牙利算法 最坏 $O(m \times n)$，一般远小于 $O(m \times n)$

用于计算二分图的最大匹配。

二分图的匹配：给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。
二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。

有点类似于月老牵线。。。换匹配的时候当然要选择原谅她啊！

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
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 510, M = 1e5 + 10;
int h[N], e[M], ne[M], idx = 1;
bool st[N];//为什么每次都要先置为flase呢？
//因为后来的点如果可以，就一定要抢走先匹配上的点的匹配，先匹配上的点就要重新找匹配，
//但是原来的匹配点已经被后来的占用了，为了防止这两个点互相抢当前匹配，就需要记录该状态
int mymatch[N];//记录右边与左边哪个点对应

void myadd(int u, int v)
{
    e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}

bool myfind(int u)//判断当前左边集合中的点能否找到一个右边集合中还可用的配对
{
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int v = e[i];
        if (!st[v])//本轮中v点还未被匹配
        {
            st[v] = true;
            //要么这个匹配点没被用过；或者被用过，但是当前点抢占后，原来的点能找到新匹配
            if (!mymatch[v] || myfind(mymatch[v]))
            {
                mymatch[v] = u;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    int n1, n2, m;
    scanf("%d%d%d", &n1, &n2, &m);
    memset(h, -1, sizeof(h));
    while (m--)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        myadd(u, v);
    }
    int res = 0;
    memset(mymatch, 0, sizeof(mymatch));
    for (int i = 1; i <= n1; ++i)
    {
        memset(st, false, sizeof(st));//用于左边点集中一个点所有出边只被访问一次
        if (myfind(i)) ++res;
    }
    printf("%d", res);
    return 0;
}

发表于 分类于
本文字数： 2k 阅读时长 ≈ 2 分钟

最小生成树

alt

本文时间复杂度中: $n$ 为节点数， $m$ 为边数。

朴素版Prim $O(n^2)$

思路：

类似于 $Dijkstra$，从任意一点开始，先更新该点的dist，再以该点为中继，更新其余点到已确定距离的集合的距离；之后的循环都是找到离当前已经确定了距离的集合最近的点，并以重复下一次循环。

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 <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 510, M = 1e5 + 10;
int myg[N][N], dist[N];
int n, m;
bool st[N];

int prim()
{
	int res = 0;//记录最小生成树的路径长度
	memset(dist, 0x3f, sizeof(dist));
	memset(st, 0, sizeof(st));
	for (int i = 0; i < n; ++i)//从0开始比较方便，1开始也不是不可以,注意要循环n次，相当于每个节点一条边，初始点边权为0
	{
		int t = -1;
		for (int j = 1; j <= n; ++j)
			if (!st[j] && (t == -1 || dist[t] > dist[j]))//类似dijkstra
				t = j;
		if (i && dist[t] == 0x3f3f3f3f)
			return 0x3f3f3f3f;
		if (i)//i为0时为第一个点，到集合的距离为零，因此不用运算
			res += dist[t];
		for (int j = 1; j <= n; ++j)
			dist[j] = min(dist[j], myg[t][j]);//更新区别于dijkstra，更新的是到集合的距离，而且可以看出被更新的只会是与t相连的
		st[t] = true;
	}
	return res;
}

int main()
{
	scanf("%d%d", &n, &m);
	memset(myg, 0x3f, sizeof(myg));
	while (m--)
	{
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		myg[u][v] = myg[v][u] = min(myg[u][v], w);
	}
	int res = prim();
	if (res == 0x3f3f3f3f)
		puts("impossible");
	else
		printf("%d", res);
	return 0;
}

Kruskal $O(mlogm)$

思路：

使用了并查集。首先排序，按边权从小到大排序，再用并查集，即如果不属于同一集合，则加入集合。而且该算法没有必要用临界表或邻接矩阵来存，直接用结构体存起终点和权值就可以。

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 <cstdio>
#include <algorithm>
using namespace std;

int n, m;
const int N = 1e5 + 10,M = 2e5 + 10;
int p[N];
struct edge
{
    int l, r, w;
    bool operator < (const edge &W)
    {
        return w < W.w;
    }
}e[M];

int find(int x)
{
    if(x != p[x])
        p[x] = find(p[x]);
    return p[x];
}

int main()
{
    scanf("%d%d", &n, &m);
    int u, v, w;
    for(int i = 1; i <= m; ++i)
    {
        scanf("%d%d%d", &u, &v, &w);
        e[i] = {u, v, w};
    }
    sort(e + 1, e + m + 1);
    for(int i = 1; i <= n; ++i)
        p[i] = i;
    int res = 0, cnt = 0, l, r;
    for(int i = 1; i <= m; ++i)
    {
        l = e[i].l, r = e[i].r, w = e[i].w;
        l = find(l), r = find(r);
        if(l != r)
            res += w, p[l] = r, ++cnt;
    }
    if(cnt < n - 1)
        puts("impossible");
    else
        printf("%d", res);
    return 0;
}

发表于 更新于 分类于
本文字数： 5.6k 阅读时长 ≈ 5 分钟

最短路算法

alt

本文时间复杂度中: $n$ 为节点数， $m$ 为边数。

朴素版Dijkstra $O(n^2)$

思路：

从源点开始，先更新与源点间的距离；再找到一个与源点距离最近的点，用这个点作为中继，比较剩余点经该点中继再到源点的距离是否比原来近，近则更新，否则不变，再在剩余的点中查找与源点最近的点，开始下一次循环。

上代码！

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 510, M = 1e5 + 10;
int h[N], e[M], ne[M], w[M], idx = 1;
int dist[N];
int n, m;
bool st[N];

void add(int x, int y, int z)
{
    e[idx] = y, w[idx] = z, ne[idx] = h[x], h[x] = idx++;
}

int dijkstra()
{
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    for(int i = 1; i < n; ++i)//只用循环 n - 1 次（n 个点 n - 1 条边）
    {
        int t = -1;
        for(int j = 1; j <= n; ++j)
            if(!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        for(int j = h[t]; j != -1; j = ne[j])
        {
            int k = e[j];
            dist[k] = min(dist[k], dist[t] + w[j]);
        }
        st[t] = true;
    }
    if(dist[n] == 0x3f3f3f3f) return -1;//不连通无法更新
    return dist[n];
}

int main()
{
    int x, y, z;
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof(h));//注意初始化
    for(int i = 1; i <= m; ++i)
    {
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
    }
    printf("%d", dijkstra());
    return 0;
}

堆优化版Dijkstra $O(mlogn)$

朴素版 Dijkstra 算法的性能瓶颈在于每次都要在 st 数组中标记为 false 的点中查找dist最小的点；因此可以考虑使用堆来优化。

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

typedef pair<int, int> PII;
const int N = 2e5;
int h[N], e[N], ne[N], w[N], idx = 1;
int dist[N];
int n, m;
bool st[N];

void add(int x, int y, int z)
{
    e[idx] = y, w[idx] = z, ne[idx] = h[x], h[x] = idx++;
}

int dijkstra()
{
    memset(dist, 0x3f, sizeof(dist));
    priority_queue<PII, vector<PII>, greater<PII>> myheap;//创建小根堆
    dist[1] = 0;
    myheap.push({0, 1});//first存dist，second存节点编号
    while(myheap.size())
    {
        PII temp = myheap.top();
        myheap.pop();
        int curdist = temp.first, curpos = temp.second;
        if(st[curpos]) continue;//可能存在冗余备份，遇到冗余即抛弃
        st[curpos] = true;
        for(int i = h[curpos]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > curdist + w[i])
            {
                dist[j] = curdist + w[i];
                myheap.push({dist[j], j});
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    int x, y, z;
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof(h));//注意初始化
    for(int i = 1; i <= m; ++i)
    {
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
    }
    printf("%d", dijkstra());
    return 0;
}

由于 Dijkstra 算法只能处理边权为非负数的情况，因此有了下面可以处理负权边的算法。

虽然有负权边，但是不可以有负权回路。

Bellman-Ford算法 $O(m \times n)$ (有边数限制的最短路算法)

给定一个 $n$ 个点 $m$ 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出从 $1$ 号点到 $n$ 号点的最多经过 $k$ 条边的最短距离，如果无法从 $1$ 号点走到 $n$ 号点，输出impossible。

注意：图中可能 存在负权回路。

思路：

$Bellman-Ford$ 算法外层循环循环指定次数 $k$ 次，每次循环都便利所有的边，再利用三角不等式 $dist[epos] \ge dist[spos] + weight$比较并更新 dist。
该算法需要注意防止串联，因此每次循环都要先备份 dist。

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
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 510, K = 510, M = 1e4 + 10;
int dist[N], backup[N];
int n, m, k;
struct  
{
	int l, r, w;
}e[M];

void bellman_ford()
{
	memset(dist, 0x3f, sizeof(dist));
	dist[1] = 0;
	for (int i = 1; i <= k; i++)
	{
		memcpy(backup, dist, sizeof(dist));//备份，防止串联
		for (int j = 1; j <= m; j++)
			if (dist[e[j].r] > backup[e[j].l] + e[j].w)
				dist[e[j].r] = backup[e[j].l] + e[j].w;
	}
}

int main()
{
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= m; i++)
	{
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		e[i] = { x,y,z };
	}
	bellman_ford();
	if (dist[n] > 0x3f3f3f3f / 2)
		puts("impossible");
	else
		printf("%d", dist[n]);
	return 0;
}

SPFA算法 一般 $O(m)$，最坏 $O(m \times n)$ (可用于判断是否存在负环)

该算法属于 $Bellman-Ford$ 算法的优化，使用 $BFS$，队列中只放入被更新过后 dist 变小的点编号。

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
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 1e5 + 10, M = 2e5 + 10;
int h[N], e[M], ne[M], w[M], idx = 1;
int dist[N], myq[N];
bool st[N];//这里st数组的含义不同，表示当前点是否在队列中
int n, m;

void myadd(int x, int y, int z)
{
    e[idx] = y, w[idx] = z, ne[idx] = h[x], h[x] = idx++;
}

int spfa()
{
    int l = 0, r = 1;
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0, myq[l] = 1, st[1] = true;
    while(l != r)
    {
        int t = myq[l++];
        if(l == N) l = 0;
        st[t] = false;
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if(!st[j])//不在队列中则放入队列
                {
                    myq[r++] = j, st[j] =true;
                    if(r == N) r = 0;
                }
            }
        }
    }
    return dist[n];
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for(int i = 0; i < m; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        myadd(x, y, z);
    }
    int res = spfa();
    if(res == 0x3f3f3f3f) puts("impossible");
    else printf("%d", dist[n]);
    return 0;
}

若用于判断负环存在性

因为负环存在时，一定不存在最短路，程序会死循环。因此记录一下各个点被访问到的序号，一出现某点被访问到的序号大于总点数，表明存在负环，返回退出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//部分代码
    dist[1] = 0, cnt[1] = 1;
...
    if(dist[e[i]] > dist[t] + w[i])
    {            
        dist[e[i]] = dist[t] + w[i];
        cnt[e[i]] = cnt[t] + 1;
        if(cnt[e[i]] > n)//存在负环
            return true;
        if(!st[e[i]])
        {
            myq.push(e[i]);
            st[e[i]] = true;
        }
    }

Floyd算法 $O(n^3)$ 多源汇最短路

基于动态规划。状态转移方程：

代码非常简单，但是只能处理非负权边。

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
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 210, INF = 1e9;
int myg[N][N];
int n, m, k;

void floyd()
{
    for(int k = 1; k <= n; ++k)
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j)
                myg[i][j] = min(myg[i][j], myg[i][k] + myg[k][j]);
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
        {
            if(i == j)
                myg[i][j] = 0;
            else
                myg[i][j] = INF;
        }
    for(int i = 1; i <= m; ++i)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        myg[x][y] = min(myg[x][y], z);
    }
    floyd();
    while(k--)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        if(myg[x][y] > INF / 2)
            puts("impossible");
        else
            printf("%d\n", myg[x][y]);
    }
    return 0;
}

发表于 分类于
本文字数： 2k 阅读时长 ≈ 2 分钟

拓扑排序

有向无环图称为拓扑图；拓扑图一定存在至少一个入度为零的点。

简单例题

给定一个 n 个点 m 条边的有向图，点的编号是 1 到 n，图中可能存在重边和自环。

请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 -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
#include <cstdio>
#include <cstring>
using namespace std;

int n, m;
const int N = 1e5 + 10, M = 1e5 + 10;
int h[N], e[M], ne[M], idx = 1;
bool mystate[N];
int myq[N], dist[N];

void myadd(int a, int b)
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int bfs()
{
	int l = 0, r = -1;
	for (int i = 1; i <= n; i++)
	{
		if (!dist[i])
			myq[++r] = i;//先把入度为0的点全部放入队列
	}
	while (l <= r)
	{
		int cur_pos = myq[l++];
		for (int i = h[cur_pos]; i != -1; i = ne[i])
		{
			int j = e[i];
			dist[j]--;
			if (!dist[j])
				myq[++r] = j;
		}
	}
	return r + 1;
}

int main()
{
	memset(h, -1, sizeof(h));
	memset(mystate, 0, sizeof(mystate));
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		myadd(a, b);
		dist[b]++;//点的入度进行记录
	}
	if (bfs() != n)
		printf("%d", -1);
	else
		for (int i = 1; i <= n; i++)
			printf("%d ", i);
	return 0;
}

另一系列题

LeetCode207.课程表

LeetCode210.课程表II

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
class Solution {
public:
    vector<int> res, e, ne, h, cnt;
    int idx, m;
    void myadd(int x, int y)
    {
        e[idx] = y, ne[idx] = h[x], h[x] = idx++;
    }
    bool topsort()
    {
        queue<int> myq;
        for(int i = 0; i < cnt.size(); ++i)
            if(!cnt[i]) res.push_back(i), myq.push(i);
        while(myq.size())
        {
            int t = myq.front();
            myq.pop();
            for(int i = h[t]; i != -1; i = ne[i])
            {
                --cnt[e[i]];
                if(!cnt[e[i]]) res.push_back(e[i]), myq.push(e[i]);
            }
        }
        return res.size() == cnt.size();
    }
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        if(!numCourses || !prerequisites.size())
        {
            while(numCourses--) res.push_back(numCourses);
            return res;
        }
        idx = 1, m = prerequisites.size();
        e = ne = vector<int>(m + 1), h = vector<int>(numCourses, -1), cnt = vector<int>(numCourses, 0);
        for(int i = 0; i < m; ++i)
        {
            myadd(prerequisites[i][1], prerequisites[i][0]);
            ++cnt[prerequisites[i][0]];
        }
        if(topsort()) return res;
        return {};
    }
};

发表于 分类于
本文字数： 819 阅读时长 ≈ 1 分钟

哈希

STL 中的哈希

STL 中的哈希表可以使用 unordered_map 和 unordered_set 。

哈希函数

  1. 一般数值直接取模就可以(一般模一个质数，并且该质数离2的整次幂尽量远)；
  2. 如果有冲突，则需要处理解决，因此有了哈希表的不同存储方式。

哈希存储结构

开放寻址法以及拉链法用于处理冲突。

开放寻址法

根据哈希函数值查找存储位置，若存储位置已被占用，则向后查询第一个可用位置并放入。

拉链法

哈希函数值相同的数将会存储在哈希值对应处的链表上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//插入操作(写法类似邻接表)
void insert(int x)
{
    int k = (x % mod + mod) % mod;//避免负数
    e[idx] = x, ne[idx] = h[k], h[k] = idx++;
}

//查询操作
bool find(int x)
{
    int k = (x % mod + mod) % mod;//避免负数
    for(int i = h[k]; i != -1; i = ne[i])
        if(e[i] == x) return true;
    return false;
}

字符串哈希

字符串前缀哈希法。

$H[i]$ 表示字符串中前 $i$ 个字符的哈希值；约定 $H[0] = 0$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int p = 131;//经验值
//预处理
for(int i = 1; i <= n; ++i)
{
    H[i] = H[i - 1] * p + str[i];
    P[i] = P[i - 1] * p;//find函数中有用
}

//find函数
int find(int l, int r)
{
    return H[r] - H[l - 1] * P[r - l + 1];//H[l - 1] * P[r - l + 1]的目的是去除1~l - 1这一段的哈希值，因为i从小到大，所以要乘以P[r - l + 1]
}

//判断两区间中的子串是否一致
find(l1, r1) == find(l2, r2);

这个方法可以用来判断字符串中某两个区间是否是相同的。

发表于 分类于
本文字数： 1.1k 阅读时长 ≈ 1 分钟

堆排序

STL 中的堆

如果要使用 $stl$ 中的堆（优先队列）：

1
2
3
4
5
6
7
8
#include <queue>
typedef pair<int, int> PII;

int main()
{
    priority_queue<int, vector<int>, greater<int>> myheap1;
    priority_queue<PII, vector<PII>, greater<PII>> myheap2;
}

其中：默认是大根堆，使用 greater<int> 创建的是小根堆。使用 pair 类型时，一般 first 放需有比较意义的数值，second 一般放标记号（比如堆优化版的 $Dijkstra$）。

目前比较有印象的，可以用到堆的题目有：前 K 小个数、堆优化Dijkstra，动态中位数（对顶堆）…

手写堆

堆是一个完全二叉树。小根堆约定父节点小于其左右子节点（如果有的话）。

$down$ 操作：
需要明确一点：在 heap[N] 数组中存储完全二叉树，约定根节点编号为 $idx = 1$；对于编号为 $idx$ 的点，其左儿子编号为 $2 \times idx$，右儿子编号为 $2 \times idx + 1$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
//down操作(小根堆)
void down(int idx)
{
    int t = idx;
    //在三个节点中找最小值
    if(idx * 2 <= n && heap[t] > heap[idx * 2]) t = idx * 2;
    if(idx * 2 + 1 <= n && heap[t] > heap[idx * 2 + 1]) t = idx * 2 + 1;
    if(idx != t)//根节点不是最小值才有必要交换
    {
        swap(heap[idx], heap[t]);
        down(t);//当前交换完不一定就是最终结果，需要递归处理
    }
}

另外，一般堆的建立操作时间复杂度是 $O(nlogn)$，但是有技巧让建堆操作的时间复杂度为 $O(n)$ 。

1
2
3
4
5
//时间复杂度为O(n)的建堆方法
for(int i = 1; i <= n; ++i)
    scanf("%d", &heap[i]);
for(int i = n / 2; i >= 1; --i)
    mydown(i);

堆顶元素删除操纵。采用先将堆中最后一个元素覆盖掉堆顶元素，再删除堆中最后一个元素的方法。

1
heap[1] = heap[size--], down(1);

手写堆的难度到这里都还算正常，后面的几项操作实在是XX，有种 $A$ 映射到 $B$，$B$ 再映射到 $C$ 的感觉。

发表于 分类于
本文字数： 724 阅读时长 ≈ 1 分钟

并查集重要的是路径压缩。并查集的题感觉都不简单。。。

因为往往还要维护额外信息，难度就上去了。。。

对于 $parent[N]$ 数组，初始化时全部指向自己。

1
2
for(int i = 1; i <= n; ++i)
    parent[i] = i;

带有路径压缩的 $find(val)$ 函数

1
2
3
4
5
6
int find(int val)
{
    if(val != parent[val])
        parent[val] = find(parent[val]);
    return parent[val];//返回所在集合的“祖宗节点”
}

合并两个集合的操作

合并操作首先应该判断两元素是否已经同属一个集合；之后在考虑将其中一个集合接到另一个集合中去。

1
2
3
4
5
if(order[0] == 'M')//如果为合并操作
{
    if(find(a) == find(b)) continue;
    parent[find(a)] = find(b);//把集合a的祖先节点接在集合b的祖宗节点下
}

并查集的经典应用：最长连续序列(LeetCode128.最长连续序列)

这题我真没想到是并查集，看了标签才知道可以用并查集解决。

主要思路是：

    1. 判断当前 $val$ 是否出现过，出现过则直接 $continue$ ，否则进入后续判断；
    1. 因为没有出现过，当前 $val$ 按照并查集的初始化方式，自己一个值构成一集合，且集合中元素只有自己一个；
    1. 查询 $val - 1$ 是否出现过，若出现过，则合并 $val - 1$ 和 $val$ 两个所在的集合；
    1. $ val + 1 $ 同理。
    1. 利用 $find()$ 函数查询 $val$ 的父节点及其所在集合的大小，结果即为含有当前 $val$ 的最长连续序列的长度。

还有一道食物链的题目，要求并查集同时维护一个到祖宗节点的距离。

发表于 分类于
本文字数： 1.1k 阅读时长 ≈ 1 分钟

Trie树支持插入和查询操作

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
#include <cstdio>
using namespace std;

const int N = 1e5 + 10;
int sons[N][26], idx, times[N];

void insert(char str[])
{
    int p = 0, c;
    for(int i = 0; str[i]; ++i)
    {
        c = str[i] - 'a';
        if(!sons[p][c]) sons[p][c] = ++idx;
        p = sons[p][c];
    }
    ++times[p];
}

int query(char str[])
{
    int p = 0, c;
    for(int i = 0; str[i]; ++i)
    {
        c = str[i] - 'a';
        if(!sons[p][c]) return 0;
        p = sons[p][c];
    }
    return times[p];
}

int main()
{
    int n;
    scanf("%d", &n);
    while(n--)
    {
        char order[2], strs[N];
        scanf("%s%s", &order, &strs);
        if(order[0] == 'I')
            insert(strs);
        else if(order[0] == 'Q')
            printf("%d\n", query(strs));
    }
    return 0;
}

Trie树的经典应用：最大异或对(LeetCode421.数组中两个数的最大异或值)

注意INT型为1符号位加31位数值位。

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
//插入操作
void insert(int val)
{
    int p = 0, v;
    for(int i = 30; i >= 0; --i)
    {
        v = (val >> i) & 1;
        if(!sons[p][v]) sons[p][v] = ++idx;
        p = sons[p][v];
    }
}

//求异或的查询操作
int query(int val)
{
    int p = 0, v, res = 0;
    for(int i = 30; i >= 0; --i)
    {
        v = (val >> i) & 1;
        if(sons[p][!v])
            res += 1 << i, p = sons[p][!v];//注意这里判断!v是否存在
        else
            p = sons[p][v];
    }
    return res;
}

发表于 分类于
本文字数： 558 阅读时长 ≈ 1 分钟

原理就不赘述了，忘记了就去看《大话数据结构》。

给定模式串 S 以及模板串 P ，所有字符串中只包含大小写英文字母以及阿拉伯数字。

模板串 P 在模式串 S 中多次作为子串出现。

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 <cstdio>
using namespace std;

const int N = 1e5 + 10, M = 1e6 + 10;
char s[M], p[N];
int next[N];

int main()
{
    int n, m;
    scanf("%d%s%d%s", &n, p + 1, &m, s + 1);
    for(int i = 2, j = 0; i <= n; ++i)
    {
        while(j && p[i] != p[j + 1]) j = next[j];
        if(p[i] == p[j + 1]) ++j;
        next[i] = j;
    }
    for(int i = 1, j = 0; i <= m; ++i)
    {
        while(j && s[i] != p[j + 1]) j = next[j];
        if(s[i] == p[j + 1]) ++j;
        if(j == n)
        {
            printf("%d ", i - n);
            j = next[j];//为了多次匹配
        }
    }
    return 0;
}

发表于 分类于
本文字数： 759 阅读时长 ≈ 1 分钟

差分是前缀和的逆运算

例题：

输入一个长度为n的整数序列。

接下来输入 $m$ 个操作，每个操作包含三个整数 $l, r, c，$表示将序列中 $[l, r]$ 之间的每个数加上 $c$。

请你输出进行完所有操作后的序列。

(输入输出格式以及数据范围就不贴了)

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
#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int vals[N];

void myinsert(int l, int r, int val)
{
	vals[l] += val, vals[r + 1] -= val;
}

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		int val;
		scanf("%d", &val);
		myinsert(i, i, val);
	}
	while (m--)
	{
		int l, r, c;
		scanf("%d%d%d", &l, &r, &c);
		myinsert(l, r, c);
	}
	int res = 0;
	for (int i = 1; i <= n; i++)
	{
		res += vals[i];
		printf("%d ", res);
	}
	return 0;
}

一开始输入的数组被看作一个前缀和数组。一开始使用 $myinsert(i, i, val)$ 构造出了一个新数组，这个新数组的前缀和是原数组。直接对原数组一个区间上的一次修改操作是 $O(n)$ 的，现在对新数组修改一次是 $O(1)$ 的；最终结果则是新数组求一次前缀和就能得到答案结果数组。