小舞很执着

这个屌丝很懒，什么也没留下！

热门标签

（万字，细细阅读）竞赛算法入门必经算法模型(附带题目链接和模板)_新手入门算法竞赛

作者：小舞很执着 | 2024-07-19 10:57:11

踩

新手入门算法竞赛

文章前言,一个普通的ACM算法竞赛选手。

以前只知道写题，却没有自己弄一个算法流程，思考许久，决定整理一下算法，先从入门算法入手，如有不足，望指出。

持续更新......,直到完善，现在已经破万了，最后字数粗略估计将会达到6万字。写完有时间的话会写进阶版的。

我将介绍

（一）基础算法

（二）数据结构

（三）搜索和图论

（四）数学知识

（五）动态规划

（六）初认贪心

（七）STL容器简介

//一部分人初识算法却不知道要什么情况用,或者说学这个算法不清楚是为了解决什么问题,这里将会一一解答,这篇博客旨在为新手打开兴趣并打下扎实算法基础.

//(你学完了这个博客加上写了给的练习,虽然不会立马变得很xx,但是你看待问题的思维已经发生了改变,希望你以后通过大量练习,熟练运用给出的算法体系 )

//最后,此篇博客为开放给大众的,不涉及任何营销(不要攻击博主).

//里面的每一道例题博主都亲自ac过的,放心食用.

（一）基础算法

1.快速排序


void quick_sort(int q[], int l, int r)//快速排序模板
{
    if (l >= r) return;
 
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

2.归并排序


void merge_sort(int q[], int l, int r)//归并模板
{
    if (l >= r) return;
 
    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);
 
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];
 
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];
 
    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

3.二分


bool check(int x) {/* ... */} // 检查x是否满足某种性质
 
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

4.高精度

5.前缀和与差分


一维前缀和
S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]
二维前缀和
S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]
一维差分
给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c
 
二维差分
给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

6.双指针算法


for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;
 
    // 具体问题的逻辑
}
常见问题分类：
    (1) 对于一个序列，用两个指针维护一段区间
    (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

7.位运算


求n的第k位数字: n >> k & 1
返回n的最后一位1：lowbit(n) = n & -n

8.离散化


vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素
 
// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; // 映射到1, 2, ...n
}

9.区间合并


// 将所有存在交集的区间合并
void merge(vector<PII> &segs)
{
    vector<PII> res;
 
    sort(segs.begin(), segs.end());
 
    int st = -2e9, ed = -2e9;
    for (auto seg : segs)
        if (ed < seg.first)
        {
            if (st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        }
        else ed = max(ed, seg.second);
 
    if (st != -2e9) res.push_back({st, ed});
 
    segs = res;
}

（二）数据结构

1.单链表


// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;
 
// 初始化
void init()
{
    head = -1;
    idx = 0;
}
 
// 在链表头插入一个数a
void insert(int a)
{
    e[idx] = a, ne[idx] = head, head = idx ++ ;
}
 
// 将头结点删除，需要保证头结点存在
void remove()
{
    head = ne[head];
}

2.双链表


// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;
 
// 初始化
void init()
{
    //0是左端点，1是右端点
    r[0] = 1, l[1] = 0;
    idx = 2;
}
 
// 在节点a的右边插入一个数x
void insert(int a, int x)
{
    e[idx] = x;
    l[idx] = a, r[idx] = r[a];
    l[r[a]] = idx, r[a] = idx ++ ;
}
 
// 删除节点a
void remove(int a)
{
    l[r[a]] = l[a];
    r[l[a]] = r[a];
}

3.栈


// tt表示栈顶
int stk[N], tt = 0;
 
// 向栈顶插入一个数
stk[ ++ tt] = x;
 
// 从栈顶弹出一个数
tt -- ;
 
// 栈顶的值
stk[tt];
 
// 判断栈是否为空
if (tt > 0)
{
 
}

4.队列


1.普通队列
 
// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;
 
// 向队尾插入一个数
q[ ++ tt] = x;
 
// 从队头弹出一个数
hh ++ ;
 
// 队头的值
q[hh];
 
// 判断队列是否为空
if (hh <= tt)
{
 
}
2.循环队列
// hh 表示队头，tt表示队尾的后一个位置
int q[N], hh = 0, tt = 0;
 
// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;
 
// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;
 
// 队头的值
q[hh];
 
// 判断队列是否为空
if (hh != tt)
{
 
}

5.单调栈和队列


1.单调栈
常见模型：找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
    while (tt && check(stk[tt], i)) tt -- ;
    stk[ ++ tt] = i;
}
2.单调队列
常见模型：找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
    while (hh <= tt && check_out(q[hh])) hh ++ ;  // 判断队头是否滑出窗口
    while (hh <= tt && check(q[tt], i)) tt -- ;
    q[ ++ tt] = i;
}

6.KMP


// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}
 
// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)
    {
        j = ne[j];
        // 匹配成功后的逻辑
    }
}

7.trie树


int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量
 
// 插入一个字符串
void insert(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}
 
// 查询字符串出现的次数
int query(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

8.并查集


(1)朴素并查集：
 
    int p[N]; //存储每个点的祖宗节点
 
    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
 
    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ ) p[i] = i;
 
    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);
 
 
(2)维护size的并查集：
 
    int p[N], size[N];
    //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量
 
    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
 
    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        size[i] = 1;
    }
 
    // 合并a和b所在的两个集合：
    size[find(b)] += size[find(a)];
    p[find(a)] = find(b);
 
 
(3)维护到祖宗节点距离的并查集：
 
    int p[N], d[N];
    //p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离
 
    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x)
        {
            int u = find(p[x]);
            d[x] += d[p[x]];
            p[x] = u;
        }
        return p[x];
    }
 
    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        d[i] = 0;
    }
 
    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);
    d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量

9.堆


// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;
 
// 交换两个点，及其映射关系
void heap_swap(int a, int b)
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}
 
void down(int u)
{
    int t = u;
    if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}
 
void up(int u)
{
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u >>= 1;
    }
}
 
// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);

10.哈希表


（一）一般哈希
(1) 拉链法
    int h[N], e[N], ne[N], idx;
 
    // 向哈希表中插入一个数
    void insert(int x)
    {
        int k = (x % N + N) % N;
        e[idx] = x;
        ne[idx] = h[k];
        h[k] = idx ++ ;
    }
 
    // 在哈希表中查询某个数是否存在
    bool find(int x)
    {
        int k = (x % N + N) % N;
        for (int i = h[k]; i != -1; i = ne[i])
            if (e[i] == x)
                return true;
 
        return false;
    }
 
(2) 开放寻址法
    int h[N];
 
    // 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
    int find(int x)
    {
        int t = (x % N + N) % N;
        while (h[t] != null && h[t] != x)
        {
            t ++ ;
            if (t == N) t = 0;
        }
        return t;
    }
（二）字符串哈希
核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果
 
typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64
 
// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
    h[i] = h[i - 1] * P + str[i];
    p[i] = p[i - 1] * P;
}
 
// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

（三）搜索和图论

树与图的存储
树是一种特殊的图，与图的存储方式相同。
对于无向图中的边ab，存储两条有向边a->b, b->a。
因此我们可以只考虑有向图的存储。

(1) 邻接矩阵：g[a][b] 存储边a->b

(2) 邻接表：

// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;

// 添加一条边a->b
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

// 初始化
idx = 0;
memset(h, -1, sizeof h);

1.DFS


int dfs(int u)//模板
{
    st[u] = true; // st[u] 表示点u已经被遍历过
 
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j]) dfs(j);
    }
}

2.BFS


queue<int> q;//模板
st[1] = true; // 表示1号点已经被遍历过
q.push(1);
 
while (q.size())
{
    int t = q.front();
    q.pop();
 
    for (int i = h[t]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);
        }
    }
}

3.树与图的深度优先遍历


int dfs(int u)//模板
{
    st[u] = true; // st[u] 表示点u已经被遍历过
 
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j]) dfs(j);
    }
}

4.树与图的广度优先遍历


queue<int> q;//模板
st[1] = true; // 表示1号点已经被遍历过
q.push(1);
 
while (q.size())
{
    int t = q.front();
    q.pop();
 
    for (int i = h[t]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);
        }
    }
}

5.拓扑排序


bool topsort()
{
    int hh = 0, tt = -1;
 
    // d[i] 存储点i的入度
    for (int i = 1; i <= n; i ++ )
        if (!d[i])
            q[ ++ tt] = i;
 
    while (hh <= tt)
    {
        int t = q[hh ++ ];
 
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (-- d[j] == 0)
                q[ ++ tt] = j;
        }
    }
 
    // 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
    return tt == n - 1;
}

6.Dijkstra


1.朴素版dijkstra
时间复杂是 O(n^2+m), n 表示点数，m 表示边数
int g[N][N];  // 存储每条边
int dist[N];  // 存储1号点到每个点的最短距离
bool st[N];   // 存储每个点的最短路是否已经确定
 
// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
 
    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;     // 在还未确定最短路的点中，寻找距离最小的点
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
 
        // 用t更新其他点的距离
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);
 
        st[t] = true;
    }
 
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}
2.堆优化版dijkstra
typedef pair<int, int> PII;
 
int n;      // 点的数量
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储所有点到1号点的距离
bool st[N];     // 存储每个点的最短距离是否已确定
 
// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});      // first存储距离，second存储节点编号
 
    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();
 
        int ver = t.second, distance = t.first;
 
        if (st[ver]) continue;
        st[ver] = true;
 
        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }
 
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

7.bellman-ford

8.spfa

9.Floyd

10.Prim

11.Kruskal

12.染色法判定二分图

13.匈牙利算法

（四）数学/数论知识

1.质数

2.约数

3.欧拉函数

4.快速幂

5.扩展欧几里得算法

6.中国剩余定理

7.高斯消元

8.求组合数

9.容斥定理

10.简单博弈论

（五）动态规划

1.背包问题

2.线性dp

3.区间dp

4.计数类dp

5.数位统计dp

6.状态压缩dp

7.树形dp

8.记忆化搜索

（六）简单版贪心

1.区间贪心类

2.Huffman树

3.排序不等式

4绝对值不等式

5.推公式

（七）C++的STL简介

1.vector, 变长数组，倍增的思想

size() 返回元素个数
empty() 返回是否为空
clear() 清空
front()/back()
push_back()/pop_back()
begin()/end()
支持比较运算，按字典序

2.pair<int, int>

first, 第一个元素
second, 第二个元素
支持比较运算，以first为第一关键字，以second为第二关键字（字典序）

3.string，字符串

size()/length() 返回字符串长度
empty()
clear()
substr(起始下标，(子串长度)) 返回子串
c_str() 返回字符串所在字符数组的起始地址

4.queue, 队列

size()
empty()
push() 向队尾插入一个元素
front() 返回队头元素
back() 返回队尾元素
pop() 弹出队头元素

5.priority_queue, 优先队列，默认是大根堆

size()
empty()
push() 插入一个元素
top() 返回堆顶元素
pop() 弹出堆顶元素
定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;

6.stack, 栈

size()
empty()
push() 向栈顶插入一个元素
top() 返回栈顶元素
pop() 弹出栈顶元素

7.deque, 双端队列

size()
empty()
clear()
front()/back()
push_back()/pop_back()
push_front()/pop_front()
begin()/end()

8.set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列

size()
empty()
clear()
begin()/end()
++, -- 返回前驱和后继，时间复杂度 O(logn)

set/multiset

insert() 插入一个数
find() 查找一个数
count() 返回某一个数的个数
erase()
(1) 输入是一个数x，删除所有x O(k + logn)
(2) 输入一个迭代器，删除这个迭代器
lower_bound()/upper_bound()
lower_bound(x) 返回大于等于x的最小的数的迭代器
upper_bound(x) 返回大于x的最小的数的迭代器

map/multimap

insert() 插入的数是一个pair
erase() 输入的参数是pair或者迭代器
find()
注意multimap不支持此操作。时间复杂度是 O(logn)
lower_bound()/upper_bound()

unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
和上面类似，增删改查的时间复杂度是 O(1)
不支持 lower_bound()/upper_bound()，迭代器的++，--

bitset, 圧位
bitset<10000> s;

~, &, |, ^
>>, <<
==, !=

count() 返回有多少个1

any() 判断是否至少有一个1
none() 判断是否全为0

set() 把所有位置成1
set(k, v) 将第k位变成v
reset() 把所有位变成0
flip() 等价于~
flip(k) 把第k位取反

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小舞很执着/article/detail/851087

（万字，细细阅读）竞赛算法入门必经算法模型(附带题目链接和模板)_新手入门算法竞赛

文章前言,一个普通的ACM算法竞赛选手。

以前只知道写题，却没有自己弄一个算法流程，思考许久，决定整理一下算法，先从入门算法入手，如有不足，望指出。

持续更新......,直到完善，现在已经破万了，最后字数粗略估计将会达到6万字。写完有时间的话会写进阶版的。

我将介绍

（一）基础算法

（二）数据结构

（三）搜索和图论

（四）数学知识

（五）动态规划

（六）初认贪心

（七）STL容器简介

//一部分人初识算法却不知道要什么情况用,或者说学这个算法不清楚是为了解决什么问题,这里将会一一解答,这篇博客旨在为新手打开兴趣并打下扎实算法基础.

//(你学完了这个博客加上写了给的练习,虽然不会立马变得很xx,但是你看待问题的思维已经发生了改变,希望你以后通过大量练习,熟练运用给出的算法体系 )

（一）基础算法

1.快速排序

2.归并排序

3.二分

4.高精度

5.前缀和与差分

6.双指针算法

7.位运算

8.离散化

9.区间合并

（二） 数据结构

1.单链表

2.双链表

3.栈

4.队列

5.单调栈和队列

6.KMP

7.trie树

8.并查集

9.堆

10.哈希表

（三） 搜索和图论

1.DFS

2.BFS

3.树与图的深度优先遍历

4.树与图的广度优先遍历

5.拓扑排序

6.Dijkstra

7.bellman-ford

8.spfa

9.Floyd

10.Prim

11.Kruskal

12.染色法判定二分图

13.匈牙利算法

（四）数学/数论知识

1.质数

2.约数

3.欧拉函数

4.快速幂

5.扩展欧几里得算法

6.中国剩余定理

7.高斯消元

8.求组合数

9.容斥定理

10.简单博弈论

（五）动态规划

1.背包问题

2.线性dp

3.区间dp

4.计数类dp

5.数位统计dp

6.状态压缩dp

7.树形dp

8.记忆化搜索

（六）简单版贪心

1.区间贪心类

2.Huffman树

3.排序不等式

4绝对值不等式

5.推公式

（七）C++的STL简介

1.vector, 变长数组，倍增的思想

2.pair<int, int>

3.string，字符串

4.queue, 队列

（二）数据结构

（三）搜索和图论

bitset, 圧位
bitset<10000> s;