如果你打过算法竞赛一定见过这种场面自己辛辛苦苦写出来的代码复杂度在草稿纸上怎么看都够用结果交上去一个大大的 TLE。很多人第一反应是“算法不够好”但还有一个经常被忽略的原因——常数太大。“卡常”这个词说的就是把代码在常数层面的时间开销压下来的过程。它不改变算法复杂度却能让同一份算法从超时变成稳定通过是竞赛代码里最实在的工程细节之一。这篇是“如何卡常”系列的第一篇主要讲最基础也最容易见效的几个方向输入输出改造、编译选项与代码习惯、内存访问布局。适合已经能写出正确代码、却在时限上反复栽跟头的选手。我会尽量讲清楚每个优化背后的原理而不只是丢出模板。毕竟卡常这件事不了解原因就乱抄技巧往往只能用在某一道题上换个场景又被打回原形。1. 卡常到底是什么从复杂度正确却超时说起1.1 复杂度“正确”和能过评测是两回事算法竞赛里说的 O(n log n)、O(n√n)本质是渐进复杂度描述的是当数据规模趋向无穷大时运行时间的增长趋势。它回答的是“数据翻倍时间大概翻几倍”的问题但没有回答“这一秒内到底能跑多少次操作”。两个复杂度一样的实现常数可能差上三倍五倍。举个例子同样是遍历 n 个元素做统计用for循环顺序扫数组和每次都去查某个哈希表理论上都是 O(n)但实测可能是 0.2 秒和 1.8 秒的差距。当限时 2 秒时前者轻松通过后者已经在危险边缘。这个差距就来自常数因子指令条数、内存访问模式、分支预测结果、函数调用开销全部折叠进“常数”这个词里。所以“卡常”不是在追求炫技而是在把那些不必要的、可压缩的时间开销逐项找出来。这和复杂度设计是两条平行的路复杂度的天花板决定了你最多能处理多大的数据常数决定了在同样复杂度下你能跑得多快。1.2 常数的几个主要来源我平时给代码做体检时基本会把常数来源分成四块。第一块是输入输出。这是所有竞赛代码里最容易被忽视、又最容易被快速优化的一环。C 风格 IO 和 C 流之间、不加缓冲的逐字符读取和块读取之间时间差距可以非常大。第二块是内存与容器。动态分配new/delete有成本vector的扩容和拷贝也有成本。更隐蔽的是缓存命中率CPU 读连续内存时硬件预取能帮你把数据提前搬到高速缓存如果访问是跳跃的内存延迟就藏在每一条语句背后。第三块是运算与分支。除法、取模需要的 CPU 周期远高于加减法和位运算。分支密集的代码一旦预测失败流水线就要清空重来代价比多加几条普通指令还大。第四块是算法内部的常数。比如同样的平衡树操作红黑树和 Treap 的随机化成本不同同样的图遍历邻接表用vector存边和用前向星存边寻址模式也不一样。卡常就是在这些层面逐个做减法。每减一点可能只是一两毫秒但累计起来就是 TLE 到 AC 的区别。1.3 卡常不是玄学是有顺序的工程方法我见过不少选手一卡常就去背各种花哨模板什么超大快读、手写哈希、指令集加速结果代码改得面目全非时间没快多少正确性反而出了问题。其实卡常有一套稳定的排查顺序先做基准测试定位热点再从成本最低、收益最大的地方开始改通常是输入输出和内存布局最后才轮到指令级微优化。这篇文章后面的章节就是按这个顺序展开的。2. 先测再优化找到时间真正去向的三种朴素手段2.1 准备一个能复现的基准测试场景很多新手卡常失败不是因为优化技巧不对而是因为根本没有“度量”。你连代码慢在哪里都不知道就凭感觉去改那和闭眼打靶没什么区别。我自己的习惯是在本地准备一组能覆盖题目最大数据范围的数据。如果题目给了n 10^5那我就造n 10^5、n 10^6的测试点。数据生成器里尽量让各种边界情况都出现比如最大值、最小值、随机分布、单调递增。这样跑出来的时间才有说服力。然后把测试代码固定成一种稳定形式用命令行重定向输入文件连续跑多次取平均。Windows 和 Linux 下计时方式有点差异但更重要的是保证测试环境稳定别开着浏览器一堆后台任务来跑基准。2.2 用 chrono 和 clock 记录分段耗时基准测试的第一步是给整段代码计时。C 里最常用的是chrono#include chrono using namespace std::chrono; auto st steady_clock::now(); // 被测代码段 auto ed steady_clock::now(); double cost duration_castmilliseconds(ed - st).count();这个精度完全够用。注意用steady_clock而不是system_clock因为系统时钟可能被 NTP 校准或被日历操作打断而稳态时钟只负责单调计时。如果你不想引入 chrono也可以用ctime里的clock()double t clock(); // 被测代码段 double sec (clock() - t) / CLOCKS_PER_SEC;clock()返回的是进程消耗的 CPU 时间平时测单线程代码够用。但要注意它在不同平台上的含义不完全一致Linux 下按 CPU 时间累加Windows 下也是按起止时间差测出来的值可以直接当秒数看。2.3 分段计时把时间拆到函数或者循环块整段时间不够还得知道慢在哪一段这就要引入分段计时。做法很简单把可能耗时的几个部分分别标记时间戳。比如处理一个图问题可能包括“读入”“建图”“DFS 遍历”“输出答案”。你可以在这四段之间分别记录时间打印出来。哪个段占大头一目了然。不少题目的时间分配会非常反直觉你以为要优化搜索结果发现读入一个大矩阵就耗了 0.8 秒建图又一堆动态分配真正跑搜索的部分反而只占一小半。分段计时还有一个好处每次优化完可以直接对照同一段的耗时变化明确知道这次改动赚了多少、亏了多少。有的优化看起来快实测负优化这一对比立刻现形。2.4 测评机不可控本地测试怎么贴近实际测评机的 CPU 主频、内存带宽、编译器版本都可能和你的笔记本不一样。所以本地测出 1.5 秒交上去变成 1.1 或 2.3 都不奇怪。我的做法是给自己留至少 20% 到 30% 的余量本地跑 1.5 秒限时 2 秒我才敢交如果本地已经 1.9 秒那就老实回去继续优化。另外多组数据的题要特别留意累计读取量。很多输出时间接近限时的题不是单组慢而是测试组数太多每读一次文件都在兜底。这种情况下快读的收益会非常明显。3. 输入输出提速从 scanf 到 fread 的完整改造路线3.1 cin/cout 慢在哪儿sync_with_stdio 到底做了什么很多人一开始写代码直接cin n直到某天卡常了才想起快读。要理解快读为什么快得先知道cin为什么慢。C 为了兼容 C 的stdio默认让cin/cout和scanf/printf共享底层的缓冲区。这个同步机制带来额外开销。所以有人告诉你先写一句ios::sync_with_stdio(false); cin.tie(nullptr);第一行切断和 C 标准 IO 的同步第二行让cin不再每次和cout的缓冲区强行绑定。这两句加完cin的速度能接近scanf。但加完了还不够快。cin读数据本质还是一次一个字符地解析中间经过流缓冲层的多次函数调用。真正追求极限时还是要回到 C 风格的getchar/fread自己掌控读入过程。3.2 用 getchar 实现一个足够快的读入函数快读的原理很简单从缓冲区一个字符一个字符地读遇到空白跳过遇到数字就累加。用getchar的实现如下#include cstdio #include cctype inline int read() { int x 0, f 1; char c getchar(); while (!isdigit(c)) { if (c -) f -1; c getchar(); } while (isdigit(c)) { x x * 10 c - 0; c getchar(); } return x * f; }这段代码的要点是两个循环第一个循环跳过空白和符号第二个循环逐位累加。isdigit可以换成手写c 0 c 9能省一次函数调用不过在小规模数据上差别不大。这个版本已经能应对大部分题目的读入需求。它比scanf快的主要原因是少了格式化字符串的解析环节直接按纯数字逻辑处理。3.3 再进一步用 fread 把读取推到极限getchar本身还有一点开销它每次从标准输入流读取一个字符相当于一次函数调用。数据量上了几百万字符时这个调用次数就很可观了。更快的方案是先用fread把一大段数据一次性装进内存然后在内存里用指针扫描。const int SZ 1 20; char buf[SZ], *p buf, *q buf; inline char getc() { return p q (q (p buf) fread(buf, 1, SZ, stdin), p q) ? EOF : *p; } inline int read() { int x 0, f 1; char c getc(); while (c ! - !isdigit(c)) c getc(); if (c -) { f -1; c getc(); } while (isdigit(c)) { x x * 10 c - 0; c getc(); } return x * f; }这段代码把 1MB 数据先读进bufgetc只负责从内存里取字符只有当当前位置p走到了缓冲区尾部才真正触发一次fread。这样一来几十万字符的读取实际系统调用只有几次。输入总量越大这个方案的优势越明显。我自己写题时如果预估读入字符数在 500 万以上就直接上fread版本。如果只有一两万那用scanf或cin加解绑都行不必过度设计。3.4 输出也要快putchar 和整串输出输出经常被忽略。很多人算时间只看输入其实当你有大量输出行时cout和printf的调用本身也在消耗时间。最简单的优化是把endl全改成\n。endl会先插入换行再强制刷新缓冲区这种刷新很贵。比赛里如果每次输出一个endl性能会被拖垮。再进一步可以用putchar手写数字输出inline void write(int x) { if (x 0) { putchar(-); x -x; } if (x 9) write(x / 10); putchar(x % 10 0); }递归版本在输出量特别大时会有函数调用开销。想再快可以改成把结果先存进字符串缓冲区然后一次性puts或fwrite。很多题目的输出量是几十万行每行几十个字符加总起来就是几百万字符此时块输出能明显减少函数调用次数。3.5 快读的边界和注意事项快读不是万能药有几个容易踩的坑。第一int溢出。快读模板默认按int解析读入超过2^31 - 1的整数时会出错。哪怕题目说答案范围是long long输入本身不超过 int你用来累加的临时变量也要小心。我习惯直接给read()写两个版本一个读 int一个读 long long或者干脆内部用long long存。第二EOF 处理。评测数据的末尾不一定有空白字符getc返回 EOF 后还要继续循环就会出现问题。所以推荐在while (isdigit(c))的循环条件里对 EOF 做兜底避免死循环或者读到负值字符。第三负号。和上面代码一样一定要先判断-。有些题目数据全是正整数可以省略负号判断省一点时间但如果你写的是通用模板还是保留稳妥。4. 编译器与代码习惯让 CPU 少绕弯路的常规操作4.1 评测机的编译选项-O2 是基线别乱加参数大多数评测系统会以-O2作为默认优化选项。这意味着编译器会替你做一些循环优化、内联、常量折叠。你在本地用什么选项题目环境就是什么选项。这带来一个启示能让编译器帮你做的优化不用专门手写。比如for (int i 0; i n; i) sum a[i];这种简单循环在 -O2 下会被自动向量化。你手动展开循环可能反而打乱编译器的向量化判断。所以先确认你的摸索环境是 -O2再考虑下一步。如果题目环境的编译选项未知通常按 -O2 来优化肯定是最稳妥的。别在代码里加#pragma GCC optimize(3)这种开启 O3 的指令。很多 OJ 会忽略用户定义的优化 pragma加了等于没加。即使生效O3 也可能带来代码膨胀和栈溢出的风险。关键是你无法保证这点优化能赢回正确性风险。4.2 内联、循环展开和消除循环内重复计算inline关键字在现代编译器手里只是一个提示。但当你在循环体内调用一个简短函数时把函数体直接粘进来可以减少调用开销。快读和快写里我标了inline就是这个原因。循环展开的思路是减少循环控制语句的执行次数。四路的写法如下int i 0; for (; i 3 n; i 4) { sum a[i] a[i1] a[i2] a[i3]; } for (; i n; i) sum a[i];这种写法在数据量很大时确实能省一点时间尤其当你自己写一个比较复杂的循环体时。但在 -O2 下编译器经常已经帮你做了展开手工再展开可能收益甚微甚至因为访存压力变大而变慢。所以我的建议是先依赖编译器只有当你明确测出循环控制是热点时再手工展开。比展开更重要的是消除循环内的重复计算。比如for (int i 0; i n; i) { ans (base * i % mod) * a[i]; }如果base * i % mod这个结果在每次迭代里都依赖i无法提前那没问题。但如果有一个不依赖循环变量的常量就应该提到循环外面。低于 2、优化器经常没法判断某个函数调用的副作用所以手动提前计算是很值得的。4.3 减少分支查表、常数条件、分支预测现代 CPU 有很深的分支预测机制在分支结果可预测时开销很低。但如果是随机数据每次分支跳向不确定的方向预测失败的成本就很高。一个典型例子是处理负数归零if (x 0) x 0;有经验的选手知道可以写成x ~(x 31)但这在普通场景下并不是必须的。真正值得做的是把概率悬殊的分支改成查表或者在循环外层处理边界避免每个元素都走一次条件判断。比如统计字符频率可以用数组cnt[256]每次直接cnt[(unsigned char)c]替代一堆if (c a) ... else if (c b) ...。这不仅分支更少也利用了数组随机访问的局部性。__builtin_expect是给编译器提供分支概率提示的if (__builtin_expect(flag, 0)) { // 小概率路径 }这个在 Linux 内核里很常见但竞赛代码里用得不多。对分支预测的优化重点始终是“减少分支”而不是“猜对分支”。4.4 昂贵的运算除法、取模和幂的替代思路CPU 做加法、位运算通常一个周期内完成做整数除法可能要几十个周期。所以优化运算的顺序很明确优先用位运算和查表。判断一个数是不是偶数x 1比x % 2快判断 2 的幂次倍数x % 16可以写成x 15。但注意只在这些运算确实合法时才是这样。对一般模数取模比如1e9 7不能直接用位运算替代。但如果你的模数固定且模数是一个足够接近 2 的幂的数一些场景下可以用乘法和高位溢出做优化。这种复杂度较大不是第一优先级。幂运算方面内存里开一张查表往往比每次快速幂快。比如计算2^k mod m的多个查询可以预处理pow2[i]数组查一次是 O(1)。比赛里很多“看起来需要快速幂”的场景本质都能用预处理数组覆盖。5. 内存布局与缓存友好数组布局比你想的更影响时间5.1 为什么连续访问比跳跃访问快一个量级现代 CPU 从主存读数据到寄存器的路上会经过多层缓存L1、L2、L3。读主存可能需要几十上百个周期而读 L1 缓存只要几个周期。关键点是缓存以“缓存行”为单位拉取数据通常是 64 字节。当你顺序读一个int数组时一次缓存行加载就能喂饱后续十几条访问。这就是顺序访问的威力。如果你在内存中跳跃访问比如反复读链表节点、频繁切换不同堆上的小块每次可能都触发一次缓存未命中。时间差可以是数量级的。这一段是卡常里最容易被轻视的部分因为从指令数上看顺序读和跳跃读都是“访问一个元素”但实际耗时完全不同。5.2 二维数组的扁平化改造竞赛里经常会写vectorvectorint dp(n, vectorint(m));这个写法写起来顺手内存却是零散的。每一行是一个独立的vector分配行与行之间不保证连续。访问dp[i][j]时如果 i 和 j 的变化跨度大缓存命中率会非常差。替换方案是开一个一维数组int *dp new int[n * m]; #define IDX(i, j) ((i) * m (j))这样做最大的收益是整块内存连续遍历时预取器能正常工作。我实际测过同样规模的 DP一维扁平化版本往往比vectorvectorint快 20% 到 50%数据越大差距越明显。5.3 循环方向i 在外还是 j 在外扁平化之后还有个容易被忽略的循环次序问题。访问数组时越靠后的下标变化得越快缓存命中率越差。以二重循环为例for (int i 0; i n; i) for (int j 0; j m; j) dp[IDX(i, j)] ...;这里每一行内存是连续的。因为j变化时内存地址连续变化预取器轻松工作。如果两层反过来for (int j 0; j m; j) for (int i 0; i n; i) dp[IDX(i, j)] ...;每次i增加地址都跳m个整数访问从连续变成大跨步缓存命中率直线下降。所以写矩阵相关代码时大脑里一定要有一张“内存连续方向”的图最内层循环最好贴着内存连续的那一维。5.4 结构体数组和数组结构体的选择处理对象数组时比如存储若干点的坐标和权值有两种布局结构体数组AoSstruct Point { int x, y, w; }; Point pts[100000];数组结构体SoAint x[100000], y[100000], w[100000];如果你要经常“只取所有点的 x 坐标做排序”那么 SoA 布局访问x[i]时是连续读同一个数组缓存友好AoS 布局读x时会把y、w也带进缓存浪费带宽。反之如果经常整对象读写AoS 更贴合逻辑。竞赛里最常用到的其实是排序和遍历。如果题目只需要对某一字段做聚合SoA 往往赢在缓存上。代价是代码写起来稍微麻烦一点。6. 卡常有边界优化策略的取舍与收手时机6.1 复杂度不对卡常救不了这是最需要记在心里的一点卡常只能优化“同一个复杂度实现里的常数因子”补不上复杂度本身的天花板。一道题你写的是 O(n²)别人是 O(n log n)n 上到 10^5 后你再怎么快读、再怎么调内存布局也不可能和一个 O(n log n) 的实现掰手腕。所以在卡常之前先确认自己的算法复杂度是题目期望的那一档。复杂度选错了卡常只是把 TLE 从 0.01 秒优化到 0.02 秒的区别。我见过太多选手在一个错误复杂度上反复折腾 IO最后也没救回来。复杂度是战略卡常是战术战术再好也赢不了战略失误。6.2 正确性和可读性是一条不可逾越的底线卡常再猛也不值得用正确性去换。常见的危险操作包括为了省一次取模直接用int累加导致溢出、为了省数组越界检查导致内存越界、为了省一个分支导致边界数据算错。竞赛代码虽然不需要像工程代码那样处处可维护但至少你自己要能在一小时后看懂。很多花式优化会降低可读性比赛时 debug 起来就是灾难。我的原则是只有对真正经过测试确认的瓶颈部分做局部优化其余部分保持最直白的写法。6.3 时间余量留多少才算安全评测机的负载、CPU 主频、环境温度都会带来波动。同样代码同一台机器连续交几次可能一次 1.7 秒一次 2.0 秒。所以本地测试必须留余量。我的经验底线是限时 2 秒的题本地测到 1.6 秒以内才敢交限时 1 秒的题本地最好跑进 0.8 秒。这个余量不是精确标尺但确实帮我避免了好多次因为波动而翻车的情况。用本地 0.9 秒去贴 1 秒限时是非常危险的尤其是输入输出量大的题目IO 和 CPU 调度的不确定性都会放大。6.4 我个人常用的卡常顺序清单最后分享一个我实际写题时会照做的顺序这也是“如何卡常”第一篇最核心的总结先确认算法复杂度正确粗糙地算一下最大数据下的操作量不超再继续。用本地最大数据跑一遍得到完整时间。分段计时找到最耗时的模块。优先加快读快写这是最稳的收益点。把二级及以上的vectorvectorint改成一维数组检查循环方向是否贴合内存连续方向。检查循环内有没有可以提出来、可以查表、可以用位运算替代的昂贵计算。每做一步重新跑基准确认是否真的变快。如果某次改动没有收益甚至负收益果断回退。这套顺序看着朴素但绝大多数限时紧张的题目都能靠前面三步解决掉 80% 的时间问题。第 7 步尤其重要卡常是一门实验学科不是信仰改完必须测。关于卡常这个话题能展开的东西还有非常多。这篇先聊到这里把输入输出、编译器习惯和内存布局这三个最基础也最通用的切面讲清楚了。后面我准备继续写进阶内容比如手写哈希和散列表的常数控制、位运算卷积、指令级层面的优化、以及如何在保证浮点安全的前提下做快速数学运算等等。如果你自己也有什么压常数的独家经验欢迎在评论里聊聊——每一次提交背后的挣扎都值得被认真对待。