CSP-J 必学的 26 个算法与数据结构

零、背景

关于 CSP，之前分享了很多知识与算法了，如下：

这里分享一下 CSP-J 必须知道的 26 个算法。

一、排序

排序不需要自己写，直接使用 cpp 的 sort 函数即可。

默认是升序，降序时可以使用 greater<int>() 函数对象。
对于复杂结构，需要自定义比较函数，记住小于是升序，大于是降序，然后按需组合即可。

// 默认升序
sort(nums.begin(), nums.end());

// 降序
sort(nums.begin(), nums.end(), greater<int>());

// 自定义
sort(nums.begin(), nums.end(), [](int a, int b) {
    return a < b; // 升序
    return a > b; // 降序
});

二、栈

栈是一种先进后出的数据结构，栈顶元素先出栈。
可以使用 cpp 的 stack 容器实现。

// 初始化栈
stack<int> stack;

// 入栈
stack.push(1);

// 出栈
stack.pop();

// 栈顶元素
int top = stack.top();

// 栈大小
int size = stack.size();  

// 是否为空
bool isEmpty = stack.empty();

有些题目需要维护一个单调栈，然后需要在栈上二分查找，这时候就必须自己实现栈了。

// 初始化栈
vector<int> stack;

// 入栈
stack.push_back(1);

// 出栈
stack.pop_back();

// 栈顶元素
int top = stack.back();

// 栈大小
int size = stack.size();  

// 是否为空
bool isEmpty = stack.empty();

三、队列

队列是一种先进先出的数据结构。
可以使用 cpp 的 queue 容器实现。

// 初始化队列
queue<int> queue;

// 入队
queue.push(1);

// 出队
queue.pop();

// 队头元素
int front = queue.front();

// 队尾元素
int back = queue.back();

// 队列大小
int size = queue.size();  

// 是否为空
bool isEmpty = queue.empty();

有时候队首队尾都需要删除元素，这时候就需要使用双向队列 deque 了。

// 初始化双向队列
deque<int> deque;

// 队尾入队
deque.push_back(1);

// 队尾出队
deque.pop_back();

// 队首入队
deque.push_front(2);

// 队首出队
deque.pop_front();

// 队头元素
int front = deque.front();

// 队尾元素
int back = deque.back();

// 队列大小
int size = deque.size();  

// 是否为空
bool isEmpty = deque.empty();

四、双向链表

双向链表很少使用，但是遇到了需要能手敲出来。

一般需要自定义双向链表的节点结构体，然后实现双向链表的插入、删除、遍历等操作。

对于链表，我的习惯是定义一个头节点和一个尾节点，然后在头节点和尾节点之间维护双向链表。

struct DoubleLink {
  int val;
  DoubleLink* prev;
  DoubleLink* next;
  DoubleLink(int val = 0) : val(val), prev(nullptr), next(nullptr) {}
};
DoubleLink headNode, tailNode;
DoubleLink *head, *tail;

void Init(){
  head = &headNode;
  tail = &tailNode;
  head->next = tail;
  tail->prev = head;  
}

在一个元素之前或之后插入一个元素，逻辑完全一样，都是先把插入节点连起来，然后再把旧边断开。

void InsertAfter(DoubleLink* pre, DoubleLink* now) {
  now->prev = pre;
  now->next = pre->next;

  now->prev->next = now;
  now->next->prev = now;
}

void InsertBefore(DoubleLink* next, DoubleLink* now) {
  now->prev = next->prev;
  now->next = next;

  now->prev->next = now;
  now->next->prev = now;
}

删除一个元素，直接把左右两边的节点连起来即可。

void Delete(DoubleLink* now) {
  now->prev->next = now->next;
  now->next->prev = now->prev;
}

五、前缀和

前缀和几乎所有比赛都需要用到。
通过前缀和，可以快速计算出区间和。

我的习惯是下标从 1 开始，这样可以避免边界问题。

vector<ll> prefixSum(n + 1, 0);
for (int i = 1; i <= n; i++) {
    prefixSum[i] = prefixSum[i - 1] + nums[i];
}

区间查询时，左右都是闭区间，所以左区间需要减去 1。

scanf("%d %d", &l, &r); // [l,r]
printf("%lld\n", prefixSum[r] - prefixSum[l - 1]);

六、二分搜索-库函数

对于二分搜索，优先建议使用 cpp 的库函数。
大于等于使用 lower_bound 函数。
大于使用 upper_bound 函数。

auto it = lower_bound(nums.begin(), nums.end(), x);
auto it = upper_bound(nums.begin(), nums.end(), x);

七、二分搜索-手写

如果是二分一个答案，或者很大的数字，这时候就需要手写二分搜索了。

对于二分，我的习惯是左闭右开，最终得到的是第一个不满足的答案。

所有的二分，都可以通过 check 函数的封装，把值域映射为前部分是 1，后部分是 0。
使用 1 与 0 来理解，就很容易实现二分搜索。

ll Search() {
  ll l = 0, r = maxH;  //
  // 1 1 1 0 0 0 
  while (l < r) { // [l, r)
    const ll mid = (l + r) / 2;
    if (Check(mid)) {
      l = mid + 1;
    } else {
      r = mid;
    }
  }
  return r - 1;
}

如上代码，查到的是第一个 0 的位置。
如果需要求最后一个 1，搜索到第一个 0 的位置再减去 1 即可。

这是一个很重要的思路。

比如有很多有重复的数字，求最后一个数字 x 的位置。
我们就可以先求出大于 x 的第一个位置，然后减去 1 即可。

八、枚举 - 可重复排列

k 个数字，可以重复使用，求长度为 n 的排列。
共有 k^n 种排列。

int n, k;
vector<int> sta;
void Dfs(int p) {
  if (p == n) {
    Output();
    return;
  }
  for (int i = 1; i <= k; i++) {
    sta.push_back(i);
    Dfs(p + 1);
    sta.pop_back();
  }
}

九、枚举 - 子集

有 n 个人，每个人选择或者不选择，共有 2^n 种子集。

int n;
string s;
void Dfs(int p) {
  if (p == n) {
    Output();
    return;
  }
  s.push_back('0');
  Dfs(p + 1);
  s.pop_back();
  s.push_back('1');
  Dfs(p + 1);
  s.pop_back();
}

十、枚举 - 排列

有 n 个人，选择 k 个，共有 A(n, k) 种排列。
由于每个人只能选择一次，所以需要使用 vis 数组来标记是否被选择过。

int n, k;
vector<int> a;
vector<int> vis;

void Dfs(int p) {
  if (p == k) {
    Output();
    return;
  }
  for (int i = 1; i <= n; i++) {
    if (!vis[i]) {
      vis[i] = 1;
      a.push_back(i);
      Dfs(p + 1);
      a.pop_back();
      vis[i] = 0;
    }
  }
}

十一、网格移动

给一个 n * m 的网格，问从 (1, 1) 到 (n, m) 是否存在路径。

对于上下左右移动这种题目，我会封装一个 dir 数组，来表示四个方向。

正常情况下建议使用递归来实现，会简单很多。
如果要求最短路径，则只能使用 bfs 来实现。

int n, m;
char g[111][111];
int dir[4][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };
bool Check() {
  queue<pair<int, int>> q;
  q.push({1, 1});
  g[1][1] = '#';
  while (!q.empty()) {
    const auto [x, y] = q.front();
    q.pop();
    for (int i = 0; i < 4; i++) {
      const int nx = x + dir[i][0];
      const int ny = y + dir[i][1];
      if (nx < 1 || nx > n || ny < 1 || ny > m || g[nx][ny] == '#') {
        continue;
      }
      if (nx == n && ny == m) {
        return true;
      }
      q.push({nx, ny});
      g[nx][ny] = '#';
    }
  }
  return false;
}

十二、差分

有时候需要对区间做很多次修改，但只需要最后查询一次。
这时候，就可以使用差分数组来实现。

差分简单记忆就是左加右减。
输入都是闭区间，差分需要使用左闭右开，即需要在下个位置减去对应的值。

for (int i = 0; i < p; i++) {
  int x, y, z;
  scanf("%d %d %d", &x, &y, &z);
  diff[x] += z;
  diff[y + 1] -= z;
}

查询时，需要先计算前缀和，得到的就是对应位置的值。

ll pre = 0;
for (int i = 0; i < n; i++) {
  pre += diff[i];
}

十三、滑动窗口

如果是一维数组，求长度为 m 的子数组的最大值。
可以维护一个长度为 m 的窗口与元素和，右边进入窗口，左边退出窗口，并更新元素和。

如果是二维数组，求一个边长为 m 的子矩阵的最大值。
思想类似，把同一列 m 行的元素和当做一个数字，问题就转化为了一维数组的问题。

同一列 m 行的元素和从上到下移动过程中，这又是一个滑动窗口的问题。

int SolverEx() {
  int ans = 0;
  for (int i = 0; i <= maxX; i++) {
    int sum = 0;
    for (int j = 0; j <= maxY; j++) {
      // 上下滑动窗口
      rows[j] += g[i][j];
      if (i + 1 > m) {
        rows[j] -= g[i - m][j];
      }

      // 左右滑动窗口
      sum += rows[j];
      if (j + 1 > m) {
        sum -= rows[j - m];
      }
      
      // 更新答案
      ans = max(ans, sum);
    }
  }
  return ans;
}

十四、快速幂

快速幂算法，用于计算 a^b % p。
时间复杂度为 O(log b)。

ll Pow(ll a, ll b, ll p) {
  ll res = 1;
  while (b) {
    if (b & 1) {
      res = res * a % p;
    }
    a = a * a % p;
    b >>= 1;
  }
  return res;
}

如果模数比较大，res * a 超过最大值，则乘法也需要使用二进制来实现。

// 乘法取模
ll MulMod(ll a, ll b, ll c) {
  ll res = 0LL;
  for (; b; b >>= 1, a = (a << 1) % c) {
    if (b & 1) res = (res + a) % c;
  }
  return res;
}

// 快速幂
ll PowMod(ll a, ll b, ll c) {
  if (a == 0) return 0;
  if (b == 0) return 1;
  ll res = 1LL;
  for (; b; b >>= 1, a = MulMod(a, a, c)) {
    if (b & 1) res = MulMod(res, a, c);
  }
  return res;
}

十五、素数

打素数表一般使用埃氏筛，时间复杂度为 O(n log log n)。
N 为范围，M 为质数数量。
可以根据题目来设置 N，然后本地运行打印一下 prmCnt，就可以知道 M 的值了。

// 埃氏筛求 N 范围内的所有质数
const int N = 100000000;
const int M = 7849900;
bool is[N];
int prm[M];
int prmCnt = 0;
int InitPrimes() {
  // O(n log log n)
  if (prmCnt > 0) return prmCnt;
  int e = (int)(sqrt(0.0 + N) + 1), k = 0, i;
  memset(is, 1, sizeof(is));
  prm[k++] = 2;
  is[0] = is[1] = 0;
  for (i = 4; i < N; i += 2) is[i] = 0;
  for (i = 3; i < e; i += 2) {
    if (is[i]) {
      prm[k++] = i;
      for (int j = i * i; j < N; j += i * 2) {
        is[j] = 0;
      }
    }
  }
  for (; i < N; i += 2) {
    if (is[i]) {
      prm[k++] = i;
    }
  }
  return prmCnt = k;
}

十六、质因数分解

质因数分解，用于将一个数字分解成质数的乘积。
需要先打印出素数表，从小到大枚举素数，判断是否能整除。

注意事项：最后如果 n 还大于 1，说明 n 本身也是质数，也需要加入答案。

for (int i = 0; i < prmCnt && n > 1; i++) {
  while (n % prm[i] == 0) {
    ans.push_back(prm[i]);
    n /= prm[i];
  }
}
if (n > 1) {
    ans.push_back(n);
}

十七、质因数分解实战 - 组合数

题目来源：NOIP 2016 提高组 D2T1

问题：给三个数字 n、m、k，问存在多少个组合数 C(i,j) 可以整除 k，其中 i 不大于 n，j 不大于 m。
数据范围：n=2000, m=2000, k<=21

共有 n*m 个组合数，但是这些组合数会非常大，根本存不下。
显然，突破口在 k，最大只有 21。

假设值是 21，如果可以被 21 整除，则组合数值的质因数中至少需要有 1 个 3 和 1 个 7。
由此，就可以找到正确的解法了。
对于每个组合数，只需要统计质因数 3 和 7 的个数即可。

预处理 k 有哪些质因数，可以发现，21 以内要么是 1 个，要么是两个不同的质因数。
也就是说，每个组合数只需要统计不超过 2 个质因数。

如何快速统计出一个组合数指定质因数的个数呢？
这就需要进行组合数推导了。

首先有基本公式，如下。

C(i,j) = i! / (j! * (i-j)!)

把 j 替换为 j-1，则可以得到。

C(i,j-1) = i! / ((j-1)! * (i-j+1)!)

从而可以推导出：

C(i,j) = C(i,j-1) * (i-j+1) / j

因此，C(i,j) 的质因数个数，等于 C(i,j-1) 的质因数个数，加上 i-j+1 的质因数个数，再减去 j 的质因数个数。
预处理出每个数字的质因数个数，就可以快速统计出 C(i,j) 的质因数个数了。

最后再根据每个组合数是否是答案，求矩阵前缀和即可。

for (int i = 1; i < maxN; i++) {
  for (int j = 1; j < maxN; j++) {
    auto& Cij = C[i][j];
    g[i][j] = g[i][j - 1] + g[i - 1][j] - g[i - 1][j - 1];
    if (Check(i,j)) {
      g[i][j]++;
    }
  }
}

十八、最长上升子序列

给一些数字，求最长上升子序列的长度。
二分的时间复杂度为 O(n log n)。

使用 lower_bound 时是严格递增。
使用 upper_bound 时是非递减。

template <typename T>
int Lis(vector<T>& a) {
  vector<T> dp;
  dp.reserve(a.size());
  for (auto x : a) {
    auto it = lower_bound(dp.begin(), dp.end(), x); 
    if (it == dp.end()) {
      dp.push_back(x);
    } else {
      *it = x;
    }
  }
  return dp.size();
}

十九、最长公共子序列

给两个数组，求最长公共子序列的长度。
最基础的动态规划。

for (int i = 1; i <= n; i++) {
  for (int j = 1; j <= m; j++) {
    if (nums1[i - 1] == nums2[j - 1]) {
      dp[i][j] = dp[i - 1][j - 1] + 1;
    } else {
      dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    }
  }
}

二十、无限背包

给一个背包，容量为 T，每个物品有一个重量与价值，可以重复选择，求最大价值。

基本思路：容量从小到大就是允许重复选择物品。

ll PackAll(vector<pair<ll, ll>>& w, ll T) {
  int n = w.size();
  vector<ll> f(T + 1, 0);
  for (auto [t, V]: w) {
    for (ll l = t; l <= T; l++) {
      f[l] = max(f[l], f[l - t] + V);
    }
  }
  return f[T];
}

二十一、01背包

给一个背包，容量为 T，每个物品有一个重量与价值，只能选择一次，求最大价值。

基本思路：容量从大到小就是不允许重复选择物品。

ll PackZeroOne(vector<pair<ll, ll>>& w, ll T) {
  int n = w.size();
  vector<ll> f(T + 1, 0);
  for (auto [t, V]: w) {
    for (ll l = T; l >= t; l--) {
      f[l] = max(f[l], f[l - t] + V);
    }
  }
  return f[T];
}

二十二、区间DP

给一排石子，每次选择相邻的两堆合并为一堆，代价是这两堆石子的重量的和。
求合并所有石子的最小代价。

思路：枚举最后两堆的位置分割线，假设左右两部分已经合并，计算答案。

ll Dfs(int l, int r) {
  ll& ret = dp[l][r];
  if (ret != -1) {
    return ret;
  }
  if (l == r) {
    return ret = 0;
  }
  ret = INFL;
  for (int i = l; i < r; i++) {
    ret = min(ret, Dfs(l, i) + Dfs(i + 1, r) + preSums[r] - preSums[l - 1]);
  }
  return ret;
}

二十三、环形区间DP

给一个环形数组，每次选择相邻的数字合并为一个数字，代价是这两个数字的和。
求合并所有数字的最小代价与最大代价。

分析：最大与最小的算法是一样的，只是一个求最大，一个求最小。
思路：环形首尾可能相连更优，所以需要枚举边界，转化为普通数组。
技巧：将数组复制一份，拼接起来，就变成了普通数组。

for (int i = 1; i <= n; i++) {
  nums[i + n] = nums[i];
}
ll ansMin = INFL;
ll ansMax = 0;
for (int i = 1; i <= n; i++) {
  auto [minMin, maxMax] = Dfs(i, i + n - 1);
  ansMin = min(ansMin, minMin);
  ansMax = max(ansMax, maxMax);
}

二十四、二叉树的遍历

给一个二叉树，分别求前序、中序、后序遍历。

void DfsPre(int u) {
  if (u == 0) return;
  preOrder.push_back(u);
  DfsPre(nodes[u].l);
  DfsPre(nodes[u].r);
}

void DfsMid(int u) {
  if (u == 0) return;
  DfsMid(nodes[u].l);
  midOrder.push_back(u);
  DfsMid(nodes[u].r);
}

void DfsPost(int u) {
  if (u == 0) return;
  DfsPost(nodes[u].l);
  DfsPost(nodes[u].r);
  postOrder.push_back(u);
}

二十五、图的存储

给一个图，分别求邻接表、邻接矩阵。

vector<vector<int>> g;
vector<vector<int>> G;
scanf("%d %d", &n, &m);
g.resize(n + 1);
G.resize(n + 1, vector<int>(n + 1, 0));
for (int i = 0; i < m; i++) {
  int u, v;
  scanf("%d %d", &u, &v);
  g[u].push_back(v);
  g[v].push_back(u);
  G[u][v] = 1;
  G[v][u] = 1;
}

二十六、图的遍历

给一个图，分别求深度优先遍历、广度优先遍历。

深度优先遍历比较简单，直接递归就可以了。

vector<int> visited;
void Dfs(int u) {
  if (visited[u]) return;
  visited[u] = 1;
  dfsOrder.push_back(u);
//   sort(g[u].begin(), g[u].end());
  for (auto v : g[u]) {
    Dfs(v);
  }
}

广度优先队列需要自己来操作队列。

void Bfs() {
  queue<int> que;
  que.push(1);
  visited[1] = 1;
  while (!que.empty()) {
    int u = que.front();
    que.pop();
    bfsOrder.push_back(u);
    for (auto v : g[u]) {
      if (visited[v]) continue;
      visited[v] = 1;
      que.push(v);
    }
  }
}

二十七、最后

这二十六个算法或数据结构覆盖了排序、栈、队列、双向链表、前缀和、二分、枚举排列组合与子集、网格路径、差分、滑动窗口、快速幂、素数表、质因数分解、最长上升子序列、最长公共子序列、无限背包、01背包、区间DP、环形DP、二叉树遍历、图的存储与遍历。

如果这些你都掌握了，那 CSP-J 获取一等奖应该是没问题的。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号 ID：tiankonguse-code

本文首发于公众号：天空的代码世界，微信号：tiankonguse
如果你想留言，可以在微信里面关注公众号进行留言。