竞赛级算法优化指南¶
在编程竞赛中，除了掌握基础的数据结构和算法，还需要掌握各种优化技巧和高级算法。本教程将介绍竞赛中常用的优化方法和高级算法。
一、时间复杂度优化¶
（一）算法选择原则¶
1. 根据数据规模选择算法
| 数据规模 n | 建议时间复杂度 | 可用算法 |
|---|---|---|
| n ≤ 10 | O(n!) | 暴力枚举 |
| n ≤ 20 | O(2ⁿ) | 状态压缩DP |
| n ≤ 100 | O(n³) | Floyd算法 |
| n ≤ 1000 | O(n²) | 动态规划、Dijkstra |
| n ≤ 10000 | O(n log n) | 快速排序、堆排序 |
| n ≤ 10⁵ | O(n) 或 O(n log n) | 线性算法、分治 |
| n ≤ 10⁶ | O(n) 或 O(n log n) | 高效算法 |
2. 常数因子优化
// 慢速版本
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// 操作
}
}
// 优化版本（减少循环次数）
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// 操作（避免重复计算）
}
}
（二）空间换时间¶
1. 预处理
// 查询区间的最大值
int maxQuerySlow(int arr[], int l, int r) {
int max = arr[l];
for (int i = l + 1; i <= r; i++) {
if (arr[i] > max) max = arr[i];
}
return max;
}
// 预处理版本（ST表）
int st[20][MAXN]; // st[i][j] 表示从j开始的2^i个元素的最大值
int log2[MAXN];
void buildST(int arr[], int n) {
// 预处理log2
log2[1] = 0;
for (int i = 2; i <= n; i++) {
log2[i] = log2[i / 2] + 1;
}
// 初始化
for (int i = 0; i < n; i++) {
st[0][i] = arr[i];
}
// 构建
for (int j = 1; (1 << j) <= n; j++) {
for (int i = 0; i + (1 << j) - 1 < n; i++) {
st[j][i] = max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
}
}
}
int maxQueryFast(int l, int r) {
int j = log2[r - l + 1];
return max(st[j][l], st[j][r - (1 << j) + 1]);
}
2. 缓存优化
// 利用CPU缓存，优化矩阵乘法
void matrixMultiplyOptimized(int A[N][N], int B[N][N], int C[N][N]) {
// 分块处理，提高缓存命中率
int BLOCK = 64;
for (int i = 0; i < N; i += BLOCK) {
for (int j = 0; j < N; j += BLOCK) {
for (int k = 0; k < N; k += BLOCK) {
// 处理一个BLOCK大小的子矩阵
for (int ii = i; ii < i + BLOCK && ii < N; ii++) {
for (int jj = j; jj < j + BLOCK && jj < N; jj++) {
int sum = 0;
for (int kk = k; kk < k + BLOCK && kk < N; kk++) {
sum += A[ii][kk] * B[kk][jj];
}
C[ii][jj] += sum;
}
}
}
}
}
}
二、高级数据结构¶
（一）线段树 (Segment Tree)¶
线段树是一种二叉树结构，用于高效地处理区间查询和更新操作。
#define MAXN 100005
int tree[4 * MAXN]; // 线段树数组
int arr[MAXN]; // 原始数组
// 构建线段树
void build(int node, int start, int end) {
if (start == end) {
tree[node] = arr[start];
} else {
int mid = (start + end) / 2;
build(2 * node, start, mid); // 左子树
build(2 * node + 1, mid + 1, end); // 右子树
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
}
// 区间查询
int query(int node, int start, int end, int l, int r) {
if (r < start || end < l) {
return 0; // 完全在区间外
}
if (l <= start && end <= r) {
return tree[node]; // 完全在区间内
}
int mid = (start + end) / 2;
int p1 = query(2 * node, start, mid, l, r);
int p2 = query(2 * node + 1, mid + 1, end, l, r);
return p1 + p2;
}
// 点更新
void update(int node, int start, int end, int idx, int val) {
if (start == end) {
arr[idx] = val;
tree[node] = val;
} else {
int mid = (start + end) / 2;
if (start <= idx && idx <= mid) {
update(2 * node, start, mid, idx, val);
} else {
update(2 * node + 1, mid + 1, end, idx, val);
}
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
}
（二）树状数组 (Fenwick Tree / Binary Indexed Tree)¶
树状数组是一种更简单的数据结构，支持单点更新和前缀和查询。
#define MAXN 100005
int bit[MAXN]; // 树状数组
// 查询前缀和
int query(int idx) {
int sum = 0;
while (idx > 0) {
sum += bit[idx];
idx -= idx & (-idx); // 去掉最低位的1
}
return sum;
}
// 区间查询
int rangeQuery(int l, int r) {
return query(r) - query(l - 1);
}
// 点更新
void update(int idx, int delta) {
while (idx <= MAXN) {
bit[idx] += delta;
idx += idx & (-idx); // 加上最低位的1
}
}
// 构建树状数组
void build(int arr[], int n) {
for (int i = 1; i <= n; i++) {
update(i, arr[i]);
}
}
（三）并查集 (Disjoint Set Union - DSU)¶
并查集用于处理元素的分组和查询，支持合并和查找操作。
#define MAXN 100005
int parent[MAXN]; // 父节点
int rank[MAXN]; // 树的高度
// 初始化
void init(int n) {
for (int i = 1; i <= n; i++) {
parent[i] = i;
rank[i] = 0;
}
}
// 查找（带路径压缩）
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 路径压缩
}
return parent[x];
}
// 合并（按秩合并）
void unionSet(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
三、高级算法¶
（一）字符串算法¶
1. KMP算法（字符串匹配）
#include <string.h>
void computeLPS(char* pattern, int m, int* lps) {
int len = 0;
lps[0] = 0;
int i = 1;
while (i < m) {
if (pattern[i] == pattern[len]) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) {
len = lps[len - 1];
} else {
lps[i] = 0;
i++;
}
}
}
}
void kmpSearch(char* text, char* pattern) {
int n = strlen(text);
int m = strlen(pattern);
int lps[m];
computeLPS(pattern, m, lps);
int i = 0, j = 0;
while (i < n) {
if (pattern[j] == text[i]) {
i++;
j++;
}
if (j == m) {
printf("在位置 %d 找到匹配\n", i - j);
j = lps[j - 1];
} else if (i < n && pattern[j] != text[i]) {
if (j != 0) {
j = lps[j - 1];
} else {
i++;
}
}
}
}
2. 最长公共子序列（LCS）
int lcs(char* X, char* Y, int m, int n) {
int dp[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 0;
} else if (X[i - 1] == Y[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = (dp[i - 1][j] > dp[i][j - 1]) ? dp[i - 1][j] : dp[i][j - 1];
}
}
}
return dp[m][n];
}
（二）动态规划优化¶
1. 状态压缩DP
// 旅行商问题（TSP）
#define MAXN 16
#define INF 1e9
int dist[MAXN][MAXN];
int dp[1 << MAXN][MAXN];
int tsp(int n) {
// 初始化
for (int mask = 0; mask < (1 << n); mask++) {
for (int i = 0; i < n; i++) {
dp[mask][i] = INF;
}
}
dp[1][0] = 0; // 从城市0出发
// DP
for (int mask = 1; mask < (1 << n); mask++) {
for (int last = 0; last < n; last++) {
if (!(mask & (1 << last))) continue;
for (int next = 0; next < n; next++) {
if (mask & (1 << next)) continue;
int newMask = mask | (1 << next);
dp[newMask][next] = min(dp[newMask][next],
dp[mask][last] + dist[last][next]);
}
}
}
// 找回城市0的最短路径
int result = INF;
for (int i = 1; i < n; i++) {
result = min(result, dp[(1 << n) - 1][i] + dist[i][0]);
}
return result;
}
2. 斜率优化DP
// 斜率优化示例：石子合并
long long dp[MAXN][MAXN];
long long sum[MAXN];
long long getCost(int i, int j) {
return sum[j] - sum[i - 1];
}
// 斜率优化
void slopeOptimization(int n) {
for (int len = 2; len <= n; len++) {
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
dp[i][j] = INF;
// 使用四边形不等式优化
for (int k = i; k < j; k++) {
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + getCost(i, j));
}
}
}
}
（三）图算法优化¶
1. Dijkstra算法（优先队列优化）
#include <queue>
using namespace std;
#define INF 1e9
#define MAXN 100005
struct Edge {
int to;
int weight;
};
vector<Edge> graph[MAXN];
int dist[MAXN];
void dijkstra(int start, int n) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
// 初始化
for (int i = 1; i <= n; i++) {
dist[i] = INF;
}
dist[start] = 0;
pq.push({0, start});
while (!pq.empty()) {
int d = pq.top().first;
int u = pq.top().second;
pq.pop();
if (d > dist[u]) continue;
for (Edge& edge : graph[u]) {
int v = edge.to;
int w = edge.weight;
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
}
2. Floyd-Warshall算法（所有点对最短路径）
#define INF 1e9
#define MAXN 105
int dist[MAXN][MAXN];
void floydWarshall(int n) {
// 初始化
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) dist[i][j] = 0;
else dist[i][j] = INF;
}
}
// 动态规划
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
}
四、竞赛技巧¶
（一）输入输出优化¶
#include <cstdio>
// 快速输入
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
// 快速输出
inline void write(int x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
（二）位运算技巧¶
// 快速幂
long long fastPow(long long base, long long exp, long long mod) {
long long result = 1;
while (exp > 0) {
if (exp & 1) {
result = (result * base) % mod;
}
base = (base * base) % mod;
exp >>= 1;
}
return result;
}
// 位运算优化
// 判断是否是2的幂
bool isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
// 交换两个数
void swap(int& a, int& b) {
a ^= b;
b ^= a;
a ^= b;
}
// 取绝对值
int abs(int x) {
int mask = x >> 31;
return (x + mask) ^ mask;
}
（三）内存优化¶
// 小数组优化（避免动态分配）
int smallArray[100];
// 滚动数组优化（DP）
void dpOptimized(int n) {
int dp[2][MAXN]; // 只保存两行
int cur = 0, prev = 1;
for (int i = 1; i <= n; i++) {
swap(cur, prev);
for (int j = 1; j <= n; j++) {
dp[cur][j] = dp[prev][j - 1] + dp[prev][j + 1];
}
}
}
五、练习题目¶
基础优化： 1. 实现快速输入输出 2. 实现线段树的基础操作 3. 实现树状数组 4. 实现并查集
中级算法： 5. 实现KMP算法 6. 实现动态规划的斜率优化 7. 实现Dijkstra算法的优先队列优化 8. 实现LCS算法
高级竞赛： 9. 实现后缀自动机（SAM） 10. 实现网络流算法 11. 实现最短路算法的各种变种 12. 实现最小生成树算法
记住：竞赛编程不仅仅是掌握算法，更重要的是能够快速、准确地实现和优化。多练习、多总结，你的编程能力会不断提升！