模板 分类

动态规划

1. 背包问题

背包问题常用枚举方法

第一维枚举物品
第二维枚举体积
第三维枚举决策

1.1 01 背包

有 $n$ 件物品，背包容量为 $m$ ，每件物品只能使用一次。

BraumAce2024年7月1日大约 18 分钟

基础算法

1. 快速排序

快排属于分治算法，分治算法都有三步：

分成子问题

递归处理子问题

子问题合并

主要步骤：

确定分界点，可以任选 a[l]，a[r]，a[(l + r) / 2] 其中一个作为分界点。
设置两个头尾指针 i, j，初始化 i = l - 1, j = r + 1 (避免发生边界问题导致死循环) ，向中间移动。每次循环都先将 i 右移和 j 左移，然后判断，如果 a[i] > a[j] 且 i < j，就交换 a[i] 和 a[j].
最后根据分界点分别递归左右两部分。

BraumAce2024年7月1日大约 15 分钟

搜索与图论

1. 树与图的存储

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

(2) 动态邻接矩阵：

int n;
struct Edge
{
    int id, w;
};
vector<Edge> h[N];
int dist[N];

void dfs(int u, int father, int distance)
{
    dist[u] = distance;

    for (auto node : h[u])
        if (node.id != father)
            dfs(node.id, u, distance + node.w);
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        h[a].push_back({b, c});
        h[b].push_back({a, c});
    }

    dfs(1, -1, 0);
    
    // 寻找两点之间的最大距离
    int u = 1;
    for (int i = 1; i <= n; i ++ )
        if (dist[i] > dist[u])
            u = i;
    dfs(u, -1, 0);
    for (int i = 1; i <= n; i ++ )
        if (dist[i] > dist[u])
            u = i;

    int s = dist[u];

    printf("%lld\n", s * 10 + s * (s + 1ll) / 2);

    return 0;
}

BraumAce2024年7月1日大约 17 分钟

数学知识

1. 质数

1.1 试除法判定质数

从小到大遍历，只判断能否被小于 sqrt(x) 的数整除。

时间复杂度为 O(sqrt(n)).

bool is_prime(int x)
{
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i++)
        if (x % i == 0)
            return false;
    return true;
}

BraumAce2024年7月1日大约 21 分钟

数据结构

1. 数组模拟链表

1.1 单链表

也称静态链表（邻接表： $n$ 个链表，主要应用：存储图和树）单链表只能存储当前节点的值和指向下一节点的指针，无法存储上一节点

BraumAce2024年7月1日大约 14 分钟

贪心

1. 区间问题

1.1 区间选点

给定 N个闭区间，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。输出选择的点的最小数量。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;

struct node
{
    int l, r;

    bool operator < (const node &W) const
    {
        return r < W.r;
    }
    
} arr[N];

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) 
        cin >> arr[i].l >> arr[i].r;
    
    //按右端点从小到大排序
    sort(arr + 1, arr + 1 + n);
    
    int ans = 0;
    int R = -2e9; //R表示上一连续区间的最右端的点
    for (int i = 1; i <= n; i++)
    {
        if (arr[i].l > R) //如果不能覆盖掉右端点，则点数+1，更新右端点
        {
            ans++;
            R = arr[i].r;
        }
    }
    
    cout << ans << endl;
    
    return 0;
}

BraumAce2024年7月1日大约 3 分钟