本指南旨在帮助参赛者系统性地梳理算法竞赛中的重要知识点，无论是初次学习还是考前复习，都能提供清晰的思路。

图论相关算法

• 割点判定算法

void tarjan(int u, int parent) {
  visited[u] = true;
  children = 0;
  discovery[u] = low[u] = ++timestamp;
  
  for (int i = adjacency[u]; i; i = edges[i].next) {
    int v = edges[i].target;
    if (!visited[v]) {
      children++;
      tarjan(v, u);
      low[u] = min(low[v], low[u]);
      
      if (parent != u && low[v] >= discovery[u] && !is_cut[u]) {
        is_cut[u] = true;
        cut_points++;
      }
    } else if (v != parent) {
      low[u] = min(low[u], discovery[v]);
    }
  }
  
  if (parent == u && children >= 2 && !is_cut[u]) {
    is_cut[u] = true;
    cut_points++;
  }
}

• 桥判定算法

void tarjan(int current, int parent) {
  parent_node[current] = parent;
  discovery_time[current] = low_link[current] = ++counter;
  
  for (int i = adjacency[current]; i; i = edges[i].next) {
    int neighbor = edges[i].target;
    if (!discovery_time[neighbor]) {
      tarjan(neighbor, current);
      low_link[current] = min(low_link[current], low_link[neighbor]);
      
      if (low_link[neighbor] > discovery_time[current]) {
        is_bridge[neighbor] = true;
        bridge_count++;
      }
    } else if (discovery_time[neighbor] < discovery_time[current] && neighbor != parent) {
      low_link[current] = min(low_link[current], discovery_time[neighbor]);
    }
  }
}

数据结构专题

• 哈夫曼树构建

struct Element {
  int weight, height;
  bool operator < (const Element &a) const {
    return a.weight == weight ? a.height > height : a.weight > weight;
  }
};

int main() {
  n = read_input();
  k = read_input();
  priority_queue<Element> heap;
  
  for (int i = 1, weight; i <= n; i++) {
    weight = read_input();
    heap.push((Element){weight, 1});
  }
  
  while ((heap.size() - 1) % (k - 1))
    heap.push((Element){0, 1});
    
  while (heap.size() >= k) {
    int max_height = -1, total_weight = 0;
    for (int i = 1; i <= k; i++) {
      Element element = heap.top();
      heap.pop();
      max_height = max(max_height, element.height);
      total_weight += element.weight;
    }
    total_cost += total_weight;
    heap.push((Element){total_weight, max_height + 1});
  }
  
  printf("%lld\n%lld\n", total_cost, heap.top().height - 1);
  return 0;
}

• 左偏树实现

namespace LeftistTree {
  #define left_child tree[node].left
  #define right_child tree[node].right
  bool exists[maxn];
  int parent[maxn], distance[maxn];
  int left_child[maxn], right_child[maxn];
  
  struct Element {
    int position, value;
    bool operator < (const Element &b) const {
      return value != b.value ? value < b.value : position < b.position;
    }
  } elements[maxn];
  
  int find_root(int x) {
    return parent[x] == x ? x : parent[x] = find_root(parent[x]);
  }
  
  int merge(int x, int y) {
    if (!x || !y) return x + y;
    if (elements[y] < elements[x]) swap(x, y);
    right_child = merge(right_child, y);
    if (distance[left_child] < distance[right_child]) 
      swap(left_child, right_child);
    distance[x] = distance[right_child] + 1;
    return x;
  }
}

• 笛卡尔树构建

int main() {
  n = read_input();
  for (int i = 1, k; i <= n; i++) {
    array[i] = read_input();
    k = stack_top;
    while (k && array[stack[k]] > array[i]) k--;
    if (k) right_child[stack[k]] = i;
    if (k < stack_top) left_child[i] = stack[k + 1];
    stack[++k] = i;
    stack_top = k;
  }
  
  for (int i = 1; i <= n; i++) 
    answer1 ^= (i * (left_child[i] + 1));
  for (int i = 1; i <= n; i++) 
    answer2 ^= (i * (right_child[i] + 1));
    
  printf("%lld %lld\n", answer1, answer2);
  return 0;
}

• 主席树实现

// 静态区间第k小查询
#define left_child(x) tree[x].left
#define right_child(x) tree[x].right
int n, m, total, count;
int array[maxn], sorted[maxn], root[maxn];
struct Node {
  int size, left, right;
} tree[maxn];

void insert(int previous, int &current, int left, int right, int position) {
  if (!current) current = ++count;
  tree[current].size = tree[previous].size + 1;
  if (left == right) return;
  int mid = left + right >> 1;
  if (position <= mid) {
    tree[current].right = tree[previous].right;
    insert(tree[previous].left, tree[current].left, left, mid, position);
  } else {
    tree[current].left = tree[previous].left;
    insert(tree[previous].right, tree[current].right, mid + 1, right, position);
  }
}

int query(int previous, int current, int left, int right, int k) {
  if (left == right) return left;
  int left_size = tree[left_child(current)].size - tree[left_child(previous)].size;
  int mid = left + right >> 1;
  if (k > left_size) 
    return query(tree[previous].right, tree[current].right, mid + 1, right, k - left_size);
  else 
    return query(tree[previous].left, tree[current].left, left, mid, k);
}

int main() {    
  n = read_input();
  m = read_input();
  for (int i = 1; i <= n; i++) 
    sorted[i] = array[i] = read_input();
  sort(sorted + 1, sorted + n + 1);
  total = unique(sorted + 1, sorted + n + 1) - sorted - 1;
  
  for (int i = 1; i <= n; i++) 
    array[i] = lower_bound(sorted + 1, sorted + total + 1, array[i]) - sorted;

  for (int i = 1; i <= n; i++) 
    insert(root[i - 1], root[i], 1, total, array[i]);
        
  for (int i = 1, l, r, k; i <= m; i++) {
    l = read_input();
    r = read_input();
    k = read_input();
    printf("%d\n", sorted[query(root[l - 1], root[r], 1, total, k)]);
  }
  return 0;
}

• 平衡树实现（Treap）

namespace Treap {
  int insert(int value) {
    values[++total] = value;
    priorities[total] = rand();
    sum[total] = count[total] = 1;
    return total;
  }
    
  void update(int node) {
    sum[node] = sum[left_child(node)] + sum[right_child(node)] + count[node];
  }
    
  void initialize() {
    root = insert(-INF);
    right_child(root) = insert(INF);
    update(root);
  }
    
  void rotate(int &node, int direction) {
    int temp = left_child(node) ^ direction;
    left_child(node) ^ direction = right_child(temp);
    right_child(temp) = node;
    node = temp;
    update(left_child(node));
    update(node);
  }
    
  void push(int &node, int value) {
    if (!node) { 
      node = insert(value); 
      return;
    }
    if (value == values[node]) 
      count[node]++;
    else {
      int direction = value < values[node] ? 0 : 1;
      push(left_child(node) ^ direction, value);
      if (priorities[node] < priorities[left_child(node) ^ direction]) 
        rotate(node, direction ^ 1);
    }
    update(node);
  }
    
  void remove(int &node, int value) {
    if (!node) return;
    if (value == values[node]) {
      if (count[node] > 1) { 
        count[node]--; 
        update(node); 
        return;
      }
      if (left_child(node) || right_child(node)) {
        if (!right_child(node) || priorities[left_child(node)] > priorities[right_child(node)])
          rotate(node, 1), remove(right_child(node), value);
        else 
          rotate(node, 0), remove(left_child(node), value);
        update(node); 
      } else 
        node = 0; 
      return;
    }
    value < values[node] ? remove(left_child(node), value) : remove(right_child(node), value);
    update(node);
  }
    
  int get_rank(int node, int value) {
    if (!node) return -2;
    if (value == values[node]) return sum[left_child(node)] + 1;
    if (value < values[node]) return get_rank(left_child(node), value);
    return sum[left_child(node)] + count[node] + get_rank(right_child(node), value);
  }
    
  int get_value(int node, int rank) {
    if (!node) return INF;
    if (rank <= sum[left_child(node)]) return get_value(left_child(node), rank);
    if (rank <= sum[left_child(node)] + count[node]) return values[node];
    return get_value(right_child(node), rank - sum[left_child(node)] - count[node]);
  }
    
  int get_predecessor(int value) {
    int current = root, predecessor;
    while (current) {
      if (values[current] < value) 
        predecessor = values[current], 
        current = right_child(current);
      else 
        current = left_child(current);
    }
    return predecessor;
  }
    
  int get_successor(int value) {
    int current = root, successor;
    while (current) {
      if (values[current] > value) 
        successor = values[current], 
        current = left_child(current);
      else 
        current = right_child(current);
    }
    return successor;
  }
}

• ST表实现

// 静态区间最大值查询
int n, m, array[maxn], st[maxn][30], l, r;

int query(int left, int right) {
  int k = log2(right - left + 1);
  return max(st[left][k], st[right - (1 << k) + 1][k]);
}

int main(){
  n = read_input();
  m = read_input();
  for (int i = 1; i <= n; i++) 
    scanf("%d", &st[i][0]);

  for (int j = 1; j <= 30; j++)
    for (int i = 1; i + (1 << j) - 1 <= n; i++)
      st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);

  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &l, &r);
    printf("%d\n", query(l, r));
  }
  return 0;
}

数论算法

• BSGS算法

// 求解 a^l ≡ b (mod Mod) 的最小非负整数解 l（Mod为质数）
int BSGS(int a, int b, int Mod, int &result) {
  a %= Mod;
  b %= Mod;
  if (!a) {
    if (!b) { 
      result = 1; 
      return 1; 
    } else 
      return 0;
  }
  int m = ceil(sqrt(Mod));
  map<int, int> hash_table;
  for (int i = 0, temp = b % Mod; i <= m; i++, temp = temp * a % Mod) 
    hash_table[temp] = i;
  a = quick_pow(a, m, Mod);
  for (int i = 1, temp = a % Mod; i <= m; i++, temp = temp * a % Mod)
    if (hash_table.count(temp)) { 
      result = i * m - hash_table[temp]; 
      return 1; 
    }
  return 0;
}

• 中国剩余定理（CRT）与扩展中国剩余定理（EXCRT）

// CRT
void extended_gcd(int a, int b, int &x, int &y) {
  if (b == 0) { 
    x = 1; 
    y = 0; 
    return; 
  }
  extended_gcd(b, a % b, x, y);
  int z = x;
  x = y;
  y = z - y * (a / b);
}

int main() {
  n = read_input();
  for (int i = 1; i <= n; i++) {
    a[i] = read_input();
    b[i] = read_input();
    M *= a[i];
  }
  for (int i = 1; i <= n; i++) {
    times[i] = M / a[i];
    int x = 0, y = 0;
    extended_gcd(times[i], a[i], x, y);
    result += b[i] * times[i] * (x < 0 ? x + a[i] : x);
  }
  cout << result % M;
  return 0;
}

// EXCRT
int main() {
  n = read_input();
  int answer, modulus, x, y;
  for (int i = 1; i <= n; i++) {
    moduli[i] = read_input();
    remainders[i] = read_input();
  }
  modulus = moduli[1];
  answer = remainders[1];
  for (int i = 2, A, B, C; i <= n; i++) {
    A = modulus;
    B = moduli[i];
    C = (remainders[i] - answer % B + B) % B;
    int now = extended_gcd(A, B, x, y), factor = B / now;
    x = quick_multiply(x, C / now, factor);
    answer += x * modulus;
    modulus *= factor;
    answer = (answer % modulus + modulus) % modulus;
  }
  printf("%lld\n", answer);
  return 0;
}

• 拉格朗日插值（朴素实现）

int main() {
  n = read_input();
  k = read_input();
  for (int i = 1; i <= n; i++) {
    x_coords[i] = read_input();
    y_coords[i] = read_input();
  }
  for (int i = 1, first, second; i <= n; i++) {
    first = y_coords[i] % MOD;
    second = 1;
    for (int j = 1; j <= n; j++) {
      if (i == j) continue;
      first = first * (k - x_coords[j]) % MOD;
      second = second * (x_coords[i] - x_coords[j]) % MOD;
    }
    answer = (answer + (first * quick_pow(second, MOD - 2) % MOD) + MOD) % MOD;
  }
  printf("%lld\n", answer);
  return 0;
}

• 拉格朗日插值（自变量连续时）

int main() {
  n = read_input();
  k = read_input();
  prefix[0] = factorial[0] = suffix[k + 3] = 1;
  for (int i = k + 2; i >= 1; i--) 
    suffix[i] = suffix[i + 1] * (n - i) % MOD;
  for (int i = 1; i <= k + 2; i++) {
    factorial[i] = factorial[i - 1] * i % MOD;
    prefix[i] = prefix[i - 1] * (n - i) % MOD;
  }
  for (int i = 1, first, second; i <= k + 2; i++) {
    temp = (temp + quick_pow(i, k)) % MOD;
    first = prefix[i - 1] * suffix[i + 1] % MOD;
    second = factorial[i - 1] * ((k - i) & 1 ? -1 : 1) * factorial[k + 2 - i] % MOD;
    answer = ((answer + temp * first % MOD * quick_pow(second, MOD - 2) % MOD) % MOD + MOD) % MOD;
  }
  printf("%lld\n", answer);
  return 0;
}

• 高斯消元法

int main() {
  n = read_input();
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n + 1; j++)
      scanf("%lf", &matrix[i][j]);
      
  for (int i = 1, max_row; i <= n; i++) {
    max_row = i;
    for (int j = i + 1; j <= n; j++)
      if (fabs(matrix[j][i]) > fabs(matrix[max_row][i])) 
        max_row = j;
        
    for (int j = 1; j <= n + 1; j++) 
      swap(matrix[i][j], matrix[max_row][j]);
      
    if (!matrix[i][i]) { 
      printf("No Solution\n"); 
      return 0; 
    }
    
    for (int j = 1; j <= n; j++) {
      if (j == i) continue;
      double factor = matrix[j][i] / matrix[i][i];
      for (int k = i + 1; k <= n + 1; k++) 
        matrix[j][k] -= matrix[i][k] * factor;
    }
  }
  
  for (int i = 1; i <= n; i++) 
    printf("%.2lf\n", matrix[i][n + 1] / matrix[i][i]);
  return 0;
}

字符串处理算法

• Trie树实现

struct Trie {
  int next[maxn][15], total;
  void insert(char *s) {
    int current = 0;
    for (int i = 1; s[i]; i++) {
      if (!next[current][s[i]]) 
        next[current][s[i]] = ++total;
      current = next[current][s[i]];
    }
  }
  int find(char *s) {
    int position = 0, length = strlen(s + 1);
    if (checked[s + 1]) 
      return result[s + 1];
    memset(visited, false, sizeof visited);
    visited[0] = true;
    for (int i = 0; i <= length; i++) {
      if (!visited[i]) continue;
      max_match = i;
      for (int j = i + 1; j <= length; j++) {
        int c = s[j] - 'a';
        position = next[position][c];
        if (!position) break;
        if (end_marker[position]) 
          visited[j] = true;
      }
    }
    checked[s + 1] = true;
    result[s + 1] = max_match;
    return max_match;
  }
} trie;

• AC自动机

namespace AC_Automaton {
  int next[maxn][30], fail[maxn];
  int total, end[maxn];
  queue<int> q;
  void insert(char *s) {
    int current = 0;
    for (int i = 1; s[i]; i++) {
      if (!next[current][s[i] - 'a']) 
        next[current][s[i] - 'a'] = ++total;
      current = next[current][s[i] - 'a'];
    }
    end[current]++;
  }
	
  void build() {
    for (int i = 0; i < 26; i++)
      if (next[0][i]) 
        q.push(next[0][i]);
    while (!q.empty()) {
      int current = q.front();
      q.pop();
      for (int i = 0; i < 26; i++) {
        if (next[current][i]) {
          fail[next[current][i]] = next[fail[current]][i];
          q.push(next[current][i]);
        } else 
          next[current][i] = next[fail[current]][i];
      }
    }
  }
		
  int query(char *s) {
    int current = 0, matches = 0;
    for (int i = 1; s[i]; i++) {
      current = next[current][s[i] - 'a'];
      for (int j = current; j && end[j] != -1; j = fail[j]) {
        matches += end[j];
        end[j] = -1;
      }
    }
    return matches;
  }
}

• KMP与EXKMP算法

// KMP算法
prefix[0] = prefix[1] = 0;
  int n = strlen(A + 1), m = strlen(B + 1);
  for (int i = 1; i < m; i++) {
    while (j && B[j + 1] != B[i + 1]) 
      j = prefix[j];
    if (B[i + 1] == B[j + 1]) 
      j++, prefix[i + 1] = j;
  }
  j = 0;
  for (i = 0; i < n; i++) {
    while (j && B[j + 1] != A[i + 1]) 
      j = prefix[j];
    if (B[j + 1] == A[i + 1]) 
      j++;
    if (j == m) 
      printf("%d\n", i + 2 - m), 
      j = prefix[j];
  }

// EXKMP算法
void compute_next() {
  next_array[0] = m;
  int now = 0, position = 1;
  while (text[now] == pattern[1 + now] && now + 1 < m) 
    now++;
  next_array[1] = now;
  for (int i = 1; i < m; i++) {
    if (i + next_array[i - position] < next_array[position] + position) 
      next_array[i] = next_array[i - position];
    else {
      now = next_array[position] + position - i;
      now = max(now, 0LL);
      while (now + i < m && now < m && text[now] == pattern[now + i]) 
        now++;
      next_array[i] = now;
      position = i;
    }
  }     
}

void extend_kmp() {
  compute_next();
  int now = 0, position = 0;
  while (text[now] == pattern[now] && now < m && now < n) 
    now++;
  extend_array[0] = now;
  for (int i = 1; i < n; i++) {
    if (i + next_array[i - position] < extend_array[position] + position) 
      extend_array[i] = next_array[i - position]; 
    else {
      now = extend_array[position] + position - i;
      now = max(now, 0LL);
      while (pattern[now] == text[now + i] && now < m && now + i < n) 
        now++;
      extend_array[i] = now;
      position = i;
    }
  }
} 

• 后缀数组（朴素实现）

bool compare(int x, int y) {
  return rank[x] != rank[y] ? rank[x] < rank[y] : rank[x + width] < rank[y + width];
}

int main() {
  scanf("%s", text + 1);
  n = strlen(text + 1);
  for (int i = 1; i <= n; i++) {
    suffix_array[i] = i;
    rank[i] = text[i];
  }
  for (width = 1; width < n; width <<= 1) {
    sort(suffix_array + 1, suffix_array + n + 1, compare);
    for (int i = 1; i <= n; i++) 
      old_rank[i] = rank[i];
    for (int i = 1, group = 0; i <= n; i++) {
      if (old_rank[suffix_array[i]] == old_rank[suffix_array[i - 1]] &&
        old_rank[suffix_array[i] + width] == old_rank[suffix_array[i - 1] + width])
        rank[suffix_array[i]] = group;
      else 
        rank[suffix_array[i]] = ++group;
    }
  }
  for (int i = 1; i <= n; i++) 
    printf("%d ", suffix_array[i]);
  return 0;
}

• Manacher算法

void build() {
  scanf("%s", chars + 1);
  n = strlen(chars + 1);
  string[++length] = '~';
  string[++length] = '#';
  for (int i = 1; i <= n; i++) {
    string[++length] = chars[i];
    string[++length] = '#';
  }
  string[++length] = '!';
}

void process() {
  for (int i = 2; i <= length - 1; i++) {
    if (i <= max_right) 
      palindrome[i] = min(palindrome[center * 2 - i], max_right - i + 1);
    else 
      palindrome[i] = 1;
      
    while (string[i - palindrome[i]] == string[i + palindrome[i]]) 
      palindrome[i]++;
      
    if (i + palindrome[i] > max_right) {
      max_right = i + palindrome[i] - 1;
      center = i;
    }
    max_length = max(max_length, palindrome[i]);
  }
}

int main() {
  build();
  process();
  printf("%d\n", max_length - 1);
  return 0;
}

动态规划专题

• 状态压缩、区间、树形、数位、背包等基本类型，都需要掌握。

其他算法

• 各种排序算法（基数排序、归并排序、锦标赛排序等）

// 基数排序
inline void radix_sort() {
  for (int i = 1; i < 256; i++) 
    count[i] = 0;
  for (int i = 1; i <= n; i++) 
    ++count[array[i] & 255];
  for (int i = 1; i < 256; i++) 
    count[i] += count[i - 1];
  for (int i = n; i >= 1; i--) 
    buffer[count[array[i] & 255]--] = array[i];
  
  for (int i = 1; i < 256; i++) 
    count[i] = 0;
  for (int i = 1; i <= n; i++) 
    ++count[buffer[i] >> 8 & 255];
  for (int i = 1; i < 256; i++) 
    count[i] += count[i - 1];
  for (int i = n; i >= 1; i--) 
    array[count[buffer[i] >> 8 & 255]--] = buffer[i];
  
  for (int i = 1; i < 256; i++) 
    count[i] = 0;
  for (int i = 1; i <= n; i++) 
    ++count[array[i] >> 16 & 255];
  for (int i = 1; i < 256; i++) 
    count[i] += count[i - 1];
  for (int i = n; i >= 1; i--) 
    buffer[count[array[i] >> 16 & 255]--] = array[i];
  
  for (int i = 1; i < 256; i++) 
    count[i] = 0;
  for (int i = 1; i <= n; i++) 
    ++count[buffer[i] >> 24 & 255];
  for (int i = 1; i < 256; i++) 
    count[i] += count[i - 1];
  for (int i = n; i >= 1; i--) 
    array[count[buffer[i] >> 24 & 255]--] = buffer[i];
}

// 归并排序
void merge_sort(int left, int right) {
  if (right - left <= 1) return;
  int mid = left + (right - left >> 1);
  merge_sort(left, mid);
  merge_sort(mid, right);
  int p = left, q = mid, s = left;
  while (s < right) {
    if (p >= mid || (q < right && array[p] > array[q])) {
      temp[s++] = array[q++];
    } else 
      temp[s++] = array[p++];
  }
  for (int i = left; i < right; i++) 
    array[i] = temp[i];
}

// 锦标赛排序
int winner(int position1, int position2) {
  int first = position1 >= n ? position1 : temporary[position1];
  int second = position2 >= n ? position2 : temporary[position2];
  return temporary[first] <= temporary[second] ? first : second;
}

void build(int &root) {
  for (int i = 0; i < n; i++) 
    temporary[n + i] = array[i];
  for (int i = 2 * n - 1, k, j; i > 1; i -= 2) {
    k = i / 2;
    j = i - 1;
    temporary[k] = winner(i, j);
  }
  root = temporary[temporary[1]];
  temporary[temporary[1]] = INF;
}

void rebuild(int &root) {
  int i = temporary[1];
  while (i > 1) {
    int j, k = i / 2;
    if (!(i % 2) && i < 2 * n - 1) 
      j = i + 1;
    else 
      j = i - 1;
    temporary[k] = winner(i, j); 
    i = k;
  }
  root = temporary[temporary[1]];
  temporary[temporary[1]] = INF;
}

void tournament_sort() {
  int root;
  build(root);
  for (int i = 0; i < n; i++) {
    array[i] = root;
    rebuild(root);
  }
}

• 线性基

void insert(int value) {
  for (int i = max_bits; i >= 0; i--) {
    if (!(value & (1LL << i))) continue;
    if (!basis[i]) {
      basis[i] = value;
      return;
    }
    value ^= basis[i];
  }
}

int main() {
  n = read_input();
  for (int i = 1; i <= n; i++) 
    insert(read_input());
  for (int i = max_bits; i >= 0; i--) 
    answer = max(answer, (answer ^ basis[i]));
  printf("%lld\n", answer);
  return 0;
}