CSP初赛知识点整理

Twinkling · 2025-09-20 11:08:00 · 算法·理论

linux指令

变量类型

memset(a, 0x3f, sizeof a)的计算方式：

首先假设a为int型，由上表可知为32位。memset按照16进制赋值，这时候3f的含义其实是(1f)_{16} = (21)_{10}=(11111)_2

我们计算memset的时候按照上面的字节数进行计算，这时候a里面的每一个元素是0x1f1f1f1f，不要胡思乱想，按照16进制计算即可。

0x1f1f1f1f = 1 * 16^7 + F * 16^6 + 1 * 16^5 + F * 16^4 + 1 * 16^3 + F * 16^3 + 1 * 16 + F

位运算

&：相同为1，不同为0

|：含1为1，全0为0

^：相同为0，不同为1

位运算常见技巧（加粗为在阅读中可能看不懂的技巧）：

数论相关

辗转相除法：gcd(a,b) = gcd(b, a mod b)

费马小定理：若p为素数，a^p mod p = a mod p

lucas定理：C(n, k) = C(n % p, k % p) * C(n / p, k / p)

排列组合常忘思路：隔板法

错排公式：Dn = (n - 1) * (Dn-1 + Dn-2)

图论相关

欧拉路径：经过图中每条边恰好一次的路径。

欧拉回路：经过图中每条边恰好一次的回路。

欧拉图：存在欧拉回路的图。

半欧拉图：不存在欧拉回路但是存在欧拉路径的图。

二分图：可以刻画成这个样子的图。

割点/边：删掉之后图不连通的点/边。

点/边双（连通分量）：随便删掉一个点/边仍然联通的子图。

树的直径：树上任意两节点之间最长的简单路径。

树的重心：如果在树中选择某个节点并删除，这棵树将分为若干棵子树，统计子树节点数并记录最大值。取遍树上所有节点，使此最大值取到最小的节点被称为整个树的重心。说人话就是，以树的重心为根时，最大子树的大小取最小值。

树的中心：在树中，如果节点x作为根节点时，从x出发的最长链最短，那么称x为这棵树的中心。

计算带权路径长度：每个叶子节点的权值乘以它的路径长度（从根到该节点的边数），然后求和。

排序相关

不稳定：快速、希尔、选择、堆。

参考网上的记忆口诀：情绪不稳定，快些（希）选堆零食吃。

选择、冒泡、插入是比较朴素的排序方式。故时间复杂度均为n^2。

快速、堆、归并均为nlogn，但是快速排序可以被卡到n^2。

由于快速排序本质是归并的改良版本，所以空间复杂度均为n。

1. 冒泡排序

   • 原理：重复遍历列表，比较相邻元素，如果顺序错误就交换。每一轮将最大的元素“冒泡”到最后。

2. 选择排序

   • 原理：每次从未排序部分中选择最小（或最大）的元素，放到已排序部分的末尾。

3. 插入排序

   • 原理：将每个待排序元素插入到前面已排好序部分的正确位置，就像打扑克牌理牌一样。

4. 快速排序

   • 原理：分治策略。
     1. 选基准：从数组中挑一个元素作为“基准”。
     2. 分区：将数组重新排列，所有比基准小的放左边，比基准大的放右边。
     3. 递归：递归地对左右两个子数组进行快速排序。

5. 归并排序

   • 原理：分治策略。
     1. 分：递归地将数组分成两半，直到每个子数组只有一个元素。
     2. 治：将两个已排序的子数组合并成一个新的有序数组。

6. 堆排序

   • 原理：
     1. 建堆：将待排序数组构建成一个最大堆（或最小堆）。
     2. 排序：反复将堆顶元素（最大/最小值）与堆末尾元素交换，并减小堆大小，重新调整堆。

7. 计数排序

   • 原理：不是比较排序。假设输入数据都是小范围整数，统计每个元素出现的次数，然后直接算出每个元素的位置。

8. 桶排序

   • 原理：将数据分到有限数量的桶里，每个桶再分别排序（通常使用其他排序算法）。

9. 基数排序

   • 原理：按照位数（个位、十位、百位...）来进行排序，从最低位开始排。

排列组合

指针相关

指针的算术运算和数组下标访问是等价的。当你有一个指针 p 时，p[a] 实际上被编译器解释为 *(p + a)。

常用函数

易忘模板

LCA求直径：

#include <cstring>
#include <iostream>
#include <vector>

constexpr int MXN = 40005;
using namespace std;
vector<int> v[MXN];
vector<int> w[MXN];

int fa[MXN][31], cost[MXN][31], dep[MXN];
int n, m;
int a, b, c;

// dfs，用来为 lca 算法做准备。接受两个参数：dfs 起始节点和它的父亲节点。
void dfs(int root, int fno) {
  // 初始化：第 2^0 = 1 个祖先就是它的父亲节点，dep 也比父亲节点多 1。
  fa[root][0] = fno;
  dep[root] = dep[fa[root][0]] + 1;
  // 初始化：其他的祖先节点：第 2^i 的祖先节点是第 2^(i-1) 的祖先节点的第
  // 2^(i-1) 的祖先节点。
  for (int i = 1; i < 31; ++i) {
    fa[root][i] = fa[fa[root][i - 1]][i - 1];
    cost[root][i] = cost[fa[root][i - 1]][i - 1] + cost[root][i - 1];
  }
  // 遍历子节点来进行 dfs。
  int sz = v[root].size();
  for (int i = 0; i < sz; ++i) {
    if (v[root][i] == fno) continue;
    cost[v[root][i]][0] = w[root][i];
    dfs(v[root][i], root);
  }
}

// lca。用倍增算法算取 x 和 y 的 lca 节点。
int lca(int x, int y) {
  // 令 y 比 x 深。
  if (dep[x] > dep[y]) swap(x, y);
  // 令 y 和 x 在一个深度。
  int tmp = dep[y] - dep[x], ans = 0;
  for (int j = 0; tmp; ++j, tmp >>= 1)
    if (tmp & 1) ans += cost[y][j], y = fa[y][j];
  // 如果这个时候 y = x，那么 x，y 就都是它们自己的祖先。
  if (y == x) return ans;
  // 不然的话，找到第一个不是它们祖先的两个点。
  for (int j = 30; j >= 0 && y != x; --j) {
    if (fa[x][j] != fa[y][j]) {
      ans += cost[x][j] + cost[y][j];
      x = fa[x][j];
      y = fa[y][j];
    }
  }
  // 返回结果。
  ans += cost[x][0] + cost[y][0];
  return ans;
}

void Solve() {
  cin.tie(nullptr)->sync_with_stdio(false);
  // 初始化表示祖先的数组 fa，代价 cost 和深度 dep。
  memset(fa, 0, sizeof(fa));
  memset(cost, 0, sizeof(cost));
  memset(dep, 0, sizeof(dep));
  // 读入树：节点数一共有 n 个，查询 m 次，每一次查找两个节点的 lca 点。
  cin >> n >> m;
  // 初始化树边和边权
  for (int i = 1; i <= n; ++i) {
    v[i].clear();
    w[i].clear();
  }
  for (int i = 1; i < n; ++i) {
    cin >> a >> b >> c;
    v[a].push_back(b);
    v[b].push_back(a);
    w[a].push_back(c);
    w[b].push_back(c);
  }
  // 为了计算 lca 而使用 dfs。
  dfs(1, 0);
  for (int i = 0; i < m; ++i) {
    cin >> a >> b;
    cout << lca(a, b) << '\n';
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int T;
  cin >> T;
  while (T--) Solve();
  return 0;
}

Floyd算法：

for (k = 1; k <= n; k++) {
  for (x = 1; x <= n; x++) {
    for (y = 1; y <= n; y++) {
      f[k][x][y] = min(f[k - 1][x][y], f[k - 1][x][k] + f[k - 1][k][y]);
    }
  }
}

SPFA

struct edge {
  int v, w;
};

vector<edge> e[MAXN];
int dis[MAXN], cnt[MAXN], vis[MAXN];
queue<int> q;

bool spfa(int n, int s) {
  memset(dis, 0x3f, (n + 1) * sizeof(int));
  dis[s] = 0, vis[s] = 1;
  q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop(), vis[u] = 0;
    for (auto ed : e[u]) {
      int v = ed.v, w = ed.w;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        cnt[v] = cnt[u] + 1;  // 记录最短路经过的边数
        if (cnt[v] >= n) return false;
        // 在不经过负环的情况下，最短路至多经过 n - 1 条边
        // 因此如果经过了多于 n 条边，一定说明经过了负环
        if (!vis[v]) q.push(v), vis[v] = 1;
      }
    }
  }
  return true;
}

堆优化Dijstra

struct edge {
  int v, w;
};

struct node {
  int dis, u;

  bool operator>(const node& a) const { return dis > a.dis; }
};

vector<edge> e[MAXN];
int dis[MAXN], vis[MAXN];
priority_queue<node, vector<node>, greater<node>> q;

void dijkstra(int n, int s) {
  memset(dis, 0x3f, (n + 1) * sizeof(int));
  memset(vis, 0, (n + 1) * sizeof(int));
  dis[s] = 0;
  q.push({0, s});
  while (!q.empty()) {
    int u = q.top().u;
    q.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (auto ed : e[u]) {
      int v = ed.v, w = ed.w;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        q.push({dis[v], v});
      }
    }
  }
}