发表更新C++算法1 分钟读完 (大约169个字)

Cpp算法-图论-Kruskal

说明

ufs[], find(int), unionn(int, int)并查集结构

edge[]链式前向星

cmp(Edge, Edge)边排序方案

实现

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
const int maxn = 1010;
int ufs[maxn];

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

void unionn(int x, int y)
{
    int a = find(x);
    int b = find(y);
    if (a != b)
    {
        ufs[a] = b;
    }
}

const int maxm = 100010;

struct Edge
{
    int a, b, w;
    bool select;
}edge[maxm];

bool cmp(Edge a, Edge b)
{
    if (a.w != b.w) return a.w < b.w;
    if (a.a != b.a) return a.a < b.a;
    return a.b < b.b; 
}

void kruskal()
{
    for (int i = 1; i <= n; ++i)
    {
        ufs[i] = i;
    }
    int k = 0, x, y;
    sort(edge + 1, edge + 1 + m, cmp);
    for (int i = 1; i <= m; ++i)
    {
        if (k == n - 1) break;
        x = find(edge[i].a);
        y = find(edge[i].b);
        if (x != y)
        {
            unionn(x, y);
            k++;
            edge[i].select = true;
        } 
    }
}
发表更新C++算法1 分钟读完 (大约116个字)

Cpp算法-字符串算法-KMP

例：洛谷P3375

说明

pre()求前缀数组

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
char s1[1000010], s2[1000010];
int nxt[1000010], l1, l2;

void pre()
{
    nxt[1] = 0;
    int j = 0;
    for (int i = 1; i < l2; ++i)
    {
        while (j > 0 && s2[j + 1] != s2[i + 1]) j = nxt[j];
        if (s2[j + 1] == s2[i + 1]) j++;
        nxt[i + 1] = j;
    }
}

void kmp()
{
    int j = 0;
    for (int i = 0; i < l1; ++i)
    {
        while (j > 0 && s2[j + 1] != s1[i + 1]) j = nxt[j];
        if (s2[j + 1] == s1[i + 1]) j++;
        if (j == l2)
        {
            printf("%d\n", i - l2 + 2);
            j = nxt[j];
        }
    }
}

int main()
{
    cin >> s1 + 1;
    cin >> s2 + 1;
    l1 = strlen(s1 + 1);
    l2 = strlen(s2 + 1);
    pre();
    kmp();
    return 0;
}
发表更新C++算法1 分钟读完 (大约145个字)

Cpp算法-字符串算法-哈希表

例：洛谷P4305

说明

hash[]哈希表

find(int x)查找哈希表中 $x$ 的位置

push(int x)将 $x$ 插入到哈希表中

check(int x)查找 $x$ 是否在哈希表中

实现

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
#define p 100003
#define hash(a) a%p

int h[p], t, n, x;

int find(int x)
{
    int y;
    if (x < 0) y = hash(-x);
    else y = hash(x);
    while (h[y] && h[y] != x) y = hash(++y);
    return y;
}

void push(int x)
{
    h[find(x)] = x;
}

bool check(int x)
{
    return h[find(x)] == x;
}

int main()
{
    scanf("%d", &t);
    while (t--)
    {
        memset(h, 0, sizeof(h));
        scanf("%d", &n);
        while (n--)
        {
            scanf("%d", &x);
            if (!check(x))
            {
                printf("%d ", x);
                push(x);
            }
        }
        printf("\n");
    }
    return 0;
}
发表更新C++算法1 分钟读完 (大约217个字)

Cpp算法-字符串算法-字符串哈希

例：洛谷P3370

单哈希(自然溢出)

1
2
3
4
5
6
7
8
9
10
11
12
typedef unsigned long long ULL;
ULL base = 131, a[10010];
char s[10010];

ULL hash(char* s)
{
    int len = strlen(s);
    ULL Ans = 0;
    for (int i = 0; i < len; i++)
        Ans = Ans * base + (ULL)s[i];
    return Ans & 0x7fffffff;
}

单哈希(单模数)

1
2
3
4
5
6
7
8
9
10
11
12
typedef unsigned long long ULL;
ULL base = 131, a[10010], mod = 19260817;
char s[10010];

ULL hash(char* s)
{
    int len = strlen(s);
    ULL Ans = 0;
    for (int i = 0; i < len; i++)
        Ans = (Ans * base + (ULL)s[i]) % mod;
    return Ans;
}

单哈希(大模数)

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef unsigned long long ULL;
ULL base = 131, a[10010], mod = 212370440130137957LL;
char s[10010];
int prime = 233317;

ULL hash(char* s)
{
    int len = strlen(s);
    ULL Ans = 0;
    for (int i = 0; i < len; ++i)
        Ans = (Ans * base + (ULL)s[i]) % mod + prime;
    return Ans;
}

双哈希

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
typedef unsigned long long ULL;
ULL base = 131, mod1=19260817, mod2=19660813;
char s[10010];
struct data
{
    ULL x,y;
}a[10010];

ULL hash1(char* s)
{
    int len = strlen(s);
    ULL Ans = 0;
    for (int i = 0; i < len; i++)
        Ans = (Ans * base + (ULL)s[i]) % mod1;
    return Ans;
}

ULL hash2(char* s)
{
    int len = strlen(s);
    ULL Ans = 0;
    for (int i = 0; i < len; i++)
        Ans = (Ans * base + (ULL)s[i]) % mod2;
    return Ans;
}
发表更新C++算法几秒读完 (大约55个字)

Cpp算法-数论-线性筛素数

说明

p[] 最终结果

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool vis[N];
int p[N], cnt;

void get_prime()
{
    for (int i = 2; i < N; ++i)
    {
        if (!vis[i])
            p[++cnt] = i;
        for (int j = 1; j <= cnt; ++j)
        {
            int v = i * p[j];
            if (v >= N) break;
            vis[v] = true;
            if (i % p[j] == 0) continue;
        }
    }
}
发表更新C++算法1 分钟读完 (大约188个字)

Cpp算法-图论-Floyd

说明

n, m, G[][]点数、边数、邻接矩阵

dist[][]每对顶点间路径长度

pre[][]每对顶点之间路径

make()建图

实现

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
const int maxn = 110;
int n, m, G[maxn][maxn], dist[maxn][maxn], pre[maxn][maxn];

void make()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            G[i][j] = INT_MAX;
    for (int i = 1; i <= n; ++i) G[i][i] = 0;
    for (int i = 1; i <= m; ++i)
    {
        int from, to, w;
        scanf("%d %d %d", &from, &to, &w);
        G[from][to] = w;
    }
    return;
}

void Floyd()
{
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            dist[i][j] = G[i][j];
            pre[i][j]  = i;
        }
    }
    for (int k = 1; k <= n; ++k)
    {
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX && dist[i][k] + dist[k][j] < dist[i][j])
                {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    pre[i][j]  = pre[k][j];
                }
            }
        }
    }
    return;
}
发表更新C++算法2 分钟读完 (大约244个字)

Cpp算法-图论-欧拉回路

邻接矩阵

说明

G[][]邻接矩阵

deg[]度

ans[]欧拉回路

n, e点数、边数

实现

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
int G[maxn][maxn], deg[maxn], ans[maxn];
int n, e, x, y, ansi, s;

void Euler(int i)
{
	for (int j = 1; j <= n; ++j)
	{
		if (G[i][j])
		{
			G[i][j] = G[j][i] = 0;
			Euler(j);
		}
	}
	ans[++ansi] = i;
}

int main()
{
	scanf("%d %d", &n, &e);
	for (int i = 1; i <= e; ++i)
	{
		scanf("%d %d", &x, &y);
		G[x][y] = G[y][x] = 1;
		deg[x]++;
		deg[y]++;
	}
	s = 1;
	for (int i = 1; i <= n; ++i)
		if (deg[i] % 2 == 1)
			s = i;
	Euler(s);
	for (int i = 1; i <= ansi; ++i)
		printf("%d ", ans[i]);
	printf("\n");
	return 0;
}

链式前向星

说明

n, m点数、边数

head, edge[]链式前向星

ans[], ansi路径、数组大小

vis[]记录

make()建图

实现

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
int head[maxn];
struct Node
{
	int to, next;
}edge[maxm];

void make()
{
	scanf("%d %d", &n, &m);
	for (int k = 1; k <= m; ++k)
	{
		int i, j;
		scanf("%d %d", &i, &j);
		edge[k].to = i;
		edge[k].next = head[i];
		head[i] = k;
	}
	return;
}

int ans[maxm];
int ansi = 0;
bool vis[2 * maxm];

void dfs(int now)
{
    for (int k = head[now]; k != 0; k = edge[k].next)
	{
        if (!vis[k])
        {
            vis[k] = true;
            vis[k ^ 1] = true;
            dfs(edge[k].to);
            ans[ansi++] = k;
        }
	}
}
发表更新C++算法1 分钟读完 (大约133个字)

Cpp算法-动态规划

待完成

多阶段过程决策的最优化问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
graph LR
    A --5--> B1
    A --3--> B2
    B1 --1--> C1
    B1 --6--> C2
    B1 --3--> C3
    B2 --8--> C2
    B2 --4--> C4
    C1 --5--> D1
    C1 --6--> D2
    C2 --5--> D1
    C3 --8--> D3
    C4 --3--> D3
    D1 --3--> E
    D2 --4--> E
    D3 --3--> E

!!! tldr “题目及注解”
求上图从 $A$ 到 $E$ 的最短距离


$K$: 阶段

$D(X_I, (X+1)_J)$: 从 $X_I$ 到 $(X+1)_J$ 的距离

$F_K(X_I)$: $K$ 阶段下 $X_I$ 到终点 $E$ 的最短距离

倒推:
$$
K=4\qquad F_4(D_1)=3\qquad F_4(D_2)=4\qquad F_4(D_3)=3
$$
$$
K=5\qquad F_3(C_1)=min(D(C_1,D_1)+F_4(D_1),D(C_1,D_2)+F_4(D_2))=min(5+3,6+4)=8
F_3(C_2)
$$

发表更新C++算法2 分钟读完 (大约360个字)

Cpp算法-图论-Dijkstra

说明

n, m点数、边数

G[][]邻接矩阵存图

dist[]路径长度

pre[]路径

make()建图

实现

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
const int maxn = 10010;
int n, m, G[maxn][maxn], dist[maxn], pre[maxn], s;

void make()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            G[i][j] = INT_MAX;
    for (int i = 1; i <= n; ++i) G[i][i] = 0;
    for (int i = 1; i <= m; ++i)
    {
        int from, to, w;
        scanf("%d %d %d", &from, &to, &w);
        G[from][to] = w;
    }
    return;
}

void Dijkstra()
{
    int k, min;
    bool p[maxn];
    for (int i = 1; i <= n; ++i)
    {
        p[i] = false;
        if (i != s)
        {
            dist[i] = G[s][i];
            pre[i]  = s;
        }
    }
    dist[s] = 0; p[s] = true;
    for (int i = 1; i <= n - 1; ++i)
    {
        min = INT_MAX; k = 0;
        for (int j = 1; j <= n; ++j)
        {
            if (!p[j] && dist[j] < min)
            {
                min = dist[j];
                k = j;
            }
        }
        if (k == 0) return;
        p[k] = true;
        for (int j = 1; j <= n; ++j)
        {
            if (!p[j] && G[k][j] != INT_MAX && dist[j] > dist[k] + G[k][j])
            {
                dist[j] = dist[k] + G[k][j];
                pre[j] = k;
            }
        }
    }
    return;
}

堆优化(链式前向星)

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
struct Edge
{
    int to, nxt, t;
}edge[maxm << 1];
int head[maxn], cnt;
void add(int a, int b, int t)
{
    edge[++cnt].to  = b;
    edge[cnt].nxt = head[a];
    edge[cnt].t   = t;
    head[a]       = cnt;
}

struct heap
{
    int u, d;
    bool operator < (const heap& a) const
    {
        return d > a.d;
    }
};

void Dijkstra()
{
    priority_queue<heap> q;
    for (int i = 0; i <= n; ++i) dist[i] = INF;
    dist[1] = 0;
    q.push((heap){1, 0});
    while (!q.empty())
    {
        heap top = q.top();
        q.pop();
        int tx = top.u;
        int td = top.d;
        if (td != dist[tx]) continue;
        for (int i = head[tx]; i; i = edge[i].nxt)
        {
            int v = edge[i].to;
            if (dist[v] > dist[tx] + edge[i].t)
            {
                dist[v] = dist[tx] + edge[i].t;
                dy[v] = i; 
                dx[v] = tx;    //记录路径
                q.push((heap){v, dist[v]});
            }
        }
    }
}
路径
1
2
3
4
5
6
int q = n, p[maxm];
while (q != 1)
{
    p[++tot] = dy[q];
    q = dx[q];
}
发表更新C++算法几秒读完 (大约95个字)

Cpp算法-树状数组

树状数组

模板：洛谷P3374

说明

tree[]树状数组

lowbit(int)神奇的函数

add(int x, int k)第 $x$ 个数加上 $k$

sum(int x)前 $x$ 个数的和

实现

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
int tree[2000010];

int lowbit(int k)
{
    return k & -k;
}

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

int sum(int x)
{
    int ans = 0;
    while (x != 0)
    {
        ans += tree[x];
        x -= lowbit(x);
    }
    return ans;
}
BiliBili主页

最新文章

归档

标签

AtCoder1
CSP-S2
CTF16
Cpp67
Haskell11
Linux1
Luogu5
NOIp33
Python1
RISC-V1
Rust2
SPOJ1
Writeup11
bfs1
blog2
bug2
dsu on tree1
git1
github3
hexo1
manim3
markdown3
mkdocs1
python5
spike1
图论2
学习2
左偏树1
差分约束1
并查集1
数据结构4
数论3
最大流1
最短路2
杂谈2
树状数组1
游记1
状态压缩1
生活3
笔记30
算法32
线段树1
网络流22
范畴论1
莫队5
计算几何1
费用流10
随笔3
题解36

分类

×