代码竞赛里算法设计与优化直接决定提交能否通过。很多题目数据规模达到十万甚至百万级别，若采用暴力枚举往往复杂度是平方级，评测机一秒只能处理千万次操作，必然超时。因此拿到题目先要估算输入输出规模，反推可接受的时间复杂度，再选择对应算法范式。
从复杂度出发设计算法结构
拿到一道竞赛题，第一步不是写代码而是做复杂度建模。假设题目给出n等于十万，若算法是O(n平方)，总操作数约一百亿，远超一秒时限；此时必须寻找O(n log n)或O(n)的方法。常用范式包括排序加双指针、前缀和、哈希表计数、贪心以及动态规划。以“统计区间内和为k的连续子数组”为例，暴力需要两层循环，而使用前缀和配合哈希表可将时间降到O(n)。
设计阶段还要考虑空间限制。有些题目内存只有32MB，此时不能开二维大数组，需用滚动数组或就地压缩。动态规划中经典背包问题，一维数组替代二维就能把空间从O(nW)降到O(W)。另外，递归深度过大会栈溢出，应改写为迭代或使用手工栈。这些结构选择都属于算法设计范畴，而非单纯代码技巧。
下面给出一个前缀和配合哈希表的代码示例，用于解决子数组和为k的问题。该写法在竞赛中常见且稳定。
#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
unordered_map<long long, int> cnt;
cnt[0] = 1;
long long sum = 0, ans = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
sum += x;
// 查找是否存在前缀和等于 sum-k
if (cnt.find(sum - k) != cnt.end()) {
ans += cnt[sum - k];
}
cnt[sum]++;
}
cout << ans << endl;
return 0;
}
竞赛中的常见优化手段
算法框架定好后，常数优化往往成为压线通过的救命稻草。最基础的是输入输出优化，C++里关闭同步或使用快读能将大量数据的读取时间缩减数倍。对于数值运算，用位移代替乘除二、用位与判断奇偶，都比普通运算稍快。在循环内部避免重复调用函数、把不变的计算提到外层，也是基本素养。
另一个重点是减少冗余状态转移。动态规划中若发现某些转移永远用不到，应剪枝；搜索题中用可行性剪枝和最优性剪枝能大幅缩减搜索树。以深度优先搜索为例，若当前累计值已劣于已知最优解，立即返回。这种优化不改变渐进复杂度，但实战中常决定能否 AC。
以下展示一个快读函数的简单实现，用于替代缓慢的 cin 或 scanf。
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;
}
用动态规划改写暴力递归
许多竞赛题初看像搜索，实则可用动态规划在多项式时间内解决。例如编辑距离、最长公共子序列，暴力递归是指数级，而加记忆化或递推后变为O(nm)。设计状态时要遵循“无后效性”，即当前决策只依赖之前状态。若状态维度多，可尝试降维或状态压缩，比如用二进制数表示集合。
以零一背包为例，原始二维转移为 dp[i][w] = max(dp[i-1][w], dp[i-1][w-v]+val)，观察发现第i行只依赖第i-1行，因此可用一维数组从后往前更新。这样不仅省内存，还提升缓存命中率。竞赛中写出稳健的 DP 边界处理，比如初始化负无穷、注意容量恰好填满与不超过的区别，都是设计优化的细节。
下面给出降维后的零一背包核心代码，展示如何通过逆序遍历避免重复选取。
// capacity为背包容量，v和val为体积与价值数组
int dp[10005] = {0};
for (int i = 0; i < n; i++) {
for (int w = capacity; w >= v[i]; w--) {
// 逆序保证每件物品只用一次
dp[w] = max(dp[w], dp[w - v[i]] + val[i]);
}
}
算法设计与优化是代码竞赛的基本功。先以复杂度锁定大方向，再用数据结构与范式搭建解法，最后以常数优化和状态精简提升效率。平时训练应多复盘自己超时的提交，对比题解中的状态定义，逐步形成可复用的思考路径。