跳至主要內容
搜索与图论

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. 分成子问题
  2. 递归处理子问题
  3. 子问题合并

主要步骤：

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

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.并查集是一种非常精巧实用的数据结构，它主要用于处理一些不相交集合的合并问题。一些常见的用途有求连通子图，求最小生成树的 Kruskal 算法和求最近公共祖先（LCA）等。

2.基本操作主要有：

（1）初始化 init

（2）查询 find

（3）合并 union

BraumAce2024年7月27日大约 5 分钟笔记数据结构并查集
贪心

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 分钟模板贪心
主题美化