★ FEATURED ARTICLE 简介《算法竞赛进阶指南》配套资源tedukuri-master是一份面向算法竞赛和程序员面试准备的离线资料包将GitHub仓库中与书本配套的代码、题库、测试样例和讲解文档统一打包解决国内读者因网络原因难以直接访问原仓库的困难。压缩包为ZIP格式共7941个文件总大小约893MB其中2714个in输入测试数据、2498个out输出文件、1166个txt说明文本、553个cpp源码、208个pdf资料以及ans/sol答案题解可逐步对照验证算法实现。截至目前已有851人学习下载。从内容结构来看资源围绕《算法竞赛进阶指南》的重点专题展开既有快速排序、归并排序、二分查找、深度/广度优先搜索等经典实现也有Dijkstra、Floyd-Warshall等图论算法以及动态规划、贪心、回溯的实战例题。学习者可以通过可运行代码和测试点验证自己的理解逐步优化时间与空间复杂度从而在备赛或面试中建立扎实的算法功底。1. 光盘不只是附件先想清楚哪些内容能合法拿来用《算法竞赛进阶指南》的配套光盘常被当成买书附赠的摆设拆封再没见过。其实盘里最有价值的部分不是整本书的电子稿而是按章节拆好的源码、样例数据、勘误表和生成脚本——这些随书发布的资源组合正是标题里 tedukuri 指代的那类内容手作、手工重制。我备赛时第一个动作不是满网找题解而是把光盘内容按算法类型重排进本地目录。下面内容适合两类人刚啃完书、想照着代码跑一遍的新手以及想把光盘模板沉淀成个人模板库、冲刺省赛或校内选拔的熟练选手。从拆光盘开始。2. 拆光盘典型目录结构与每部分能干什么拿到任何一本竞赛书的配套光盘先别急着把每个文件都打开看。我经手过好几本同类书的光盘目录结构虽然各不一样但顶层分类基本一致。先花五分钟看清这几类东西——代码、勘误、数据、课件——后面所有练习都建立在这张地图上。2.1 顶层目录一张表看懂光盘里通常有什么常见做法是把源码按书本章节建目录例如Chapter_03、Chapter_05这样章节下面再放对应的.cpp或.pas。下面这四类内容几乎所有盘里都有。目录常见内容用途代码按章组织的 .cpp / .pas对照正文验证算法模板勘误勘误表 PDF / Excel修正书里公式、代码错误数据样例 in/out、生成脚本跑通模板、做对拍课件章节讲义 PPT快速回顾概念代码目录是最常被使用的但也是最容易让人误会的它不等同于题解合集更不是在线评测系统。光盘里代码只覆盖了书里讲到的基础结构比如二叉堆、并查集、树状数组、线段树、最短路这些“模板型算法”。至于每个算法在具体题目里怎么变形还是要回到 OJ 上做原题。我一般拿到盘后先做一件事把整份代码目录复制到工作区按算法类型重新建索引而不是按章节顺序看。这里有个容易踩的认知偏差把光盘代码直接当成“标准答案”。作者写书时有当时的编译器环境部分代码用了非标准头文件在今天的严格编译选项下可能报警告甚至报错。这不是盘坏了是年代差。后面第 3 章会讲怎么用统一标准把它们全部编译通过。另外如果你拿到的是很老的版本里面还可能出现 Pascal 后缀源文件如今投入产出比太低我通常直接跳过只看 C/C 部分。2.2 代码和勘误表的对账顺序先编译再对照勘误表是我拿到光盘后第二个要看的东西因为书里的公式、代码在出版后常有修订。常见做法是把勘误表里提到的代码文件单挑出来和光盘里的同名文件做一次对比确认盘里的版本是否已经包含修正。我一般会这样操作把代码目录全部复制到一个临时目录然后跑一次批量编译把所有错误和警告汇总到一份日志里。这个动作能在十分钟内找出“哪些文件需要人工介入”。mkdir -p build_check cd build_check find ../disc/code -name *.cpp -print0 | xargs -0 -I{} sh -c \ echo {} build.log; g -stdc14 -O0 -Wall {} -o /dev/null build.log 21这段脚本的逻辑不复杂find负责把code目录下的所有.cpp文件路径找出来xargs -0保证带空格和特殊字符的路径也能安全传递g -stdc14 -O0 -Wall用 C14 标准做语法检查-O0是因为这里只验证可编译性、不优化。编译结果统一追加到build.log最后打开日志凡是出现error的行就是需要比照勘误表的文件。参数上有两个点可以按需调整如果只想看错误不想要警告噪音把-Wall去掉但我不建议因为警告往往暴露了当年代码里隐藏的整数转换问题。如果某些老代码用了 C98 才有的写法-stdc14会兼容如果连 C98 都扛不住说明文件本身写得太老直接放弃比硬修划算。2.3 样例和生成脚本别让数据躺在盘里吃灰光盘里的data目录常被忽略因为它的样例规模很小通常只有三五组。但它的真正价值不在“数据”本身而在“生成脚本”。常见做法是盘里带一个随机数据生成器有用 Python 写的也有用 C 写的用来产生大范围输入验证复杂度。举例树状数组模板需要测试n 10^5量级的数据手写输入不可能随机树生成器几行就能搞定。常见做法是把它直接放在工作区tools/下每次造数后先跑模板再与暴力算法对拍。下面这个生成器是我常用的结构专门用来生成树形数据import random n 10 ** 5 # 节点数 print(n, n - 1) # 第一行点数与边数 for v in range(2, n 1): u random.randint(1, v - 1) # 保证生成的图是一棵树 w random.randint(0, 10 ** 9) # 边权范围 print(u, v, w)这里设计的关键参数有三个n决定规模u的随机范围被限制在[1, v-1]这样生成的图一定是连通树而不会成环w的范围对齐大多数题目对边权的约束。如果要测最短路把w的范围改小一点比如[1, 10^6]就能避免溢出干扰线段树这类结构。读完这一层应该有一个动作立刻做把光盘里的生成脚本统一复制到工作区的tools/目录而不是留在光盘里。这样每次造数据都有一致入口也方便后续对拍脚本调用。脚本里的随机种子我也建议固定一个默认值调试时可复现正式对拍时再放开随机性。3. 从模板到可提交代码环境选择与编译排错光盘里的代码标注的是“能运行”到了评测环境则要求“严格可提交”。两者之间的差距几乎都由三件事造成编译器标准、头文件依赖、输入输出方式。这一章用一个树状数组模板走完全过程。3.1 环境选择先统一编译器参数我见过太多人栽在“本地能跑、OJ 编译失败”上常见原因就是编译器标准不统一。光盘发行时主流是 C98/11而现在本地编译器默认可能是更新的标准评测端也可能是另一套工具链。想保证结果一致唯一的办法是所有编译命令都明确写-std。g -stdc14 -O2 -Wall -Wextra main.cpp -o main参数说明-stdc14同时兼容了老代码的 C98 写法和后来的auto、lambda-O2是竞赛评测的普遍优化档位能暴露本地没开优化时根本不出现的未定义行为-Wall -Wextra开警告宁可本地吵一点也别到赛场上翻车。如果你所在平台没有 g建议装一个 MinGW 工具链或者直接在 Linux 环境里编译别拿纯图形界面 IDE 的默认设置愣编译老代码。统一环境这一步本质上是把“能不能编译”这个变量从训练流程里去掉。以后凡是新拿到的模板第一件事就是按这个命令跑一遍通过之后再谈别的。这能省掉后面大量排错时间。3.2 树状数组模板跑通最小示例树状数组是《算法竞赛进阶指南》里出场频率很高的基础结构配套光盘里几乎必有对应源文件。用它做示例最合适因为代码短、边界少却能讲清楚“模板类代码怎么由盘内版本改装成可提交版本”。#include cstdio const int MAXN 100000 5; int bit[MAXN]; void add(int idx, int delta, int n) { for (int i idx; i n; i i (-i)) bit[i] delta; } int sum(int idx) { int res 0; for (int i idx; i 0; i - i (-i)) res bit[i]; return res; } int main() { int n, m; scanf(%d%d, n, m); for (int i 1; i n; i) { int v; scanf(%d, v); add(i, v, n); } while (m--) { int op, a, b; scanf(%d%d%d, op, a, b); if (op 1) add(a, b, n); else printf(%d\n, sum(b) - sum(a - 1)); } return 0; }这段代码的逻辑很直白add用i i (-i)沿树状数组的更新链向上修改复杂度 O(log n)sum用i - i (-i)沿查询链向下累加同样 O(log n)。主程序里第一行n m分别表示数组长度和操作次数随后n个初始值建树每个值都当作一次单点增量最后循环处理m个操作op 1是单点加否则输出区间和。几个参数值得留意MAXN要按题目最大规模加 5 留余量防止越界数组下标一律从 1 开始这是树状数组的硬性要求理由在避坑章节会细说。接下来做一次完整的本地验证g -stdc14 -O2 -Wall -Wextra tree_array.cpp -o tree_array ./tree_array sample.insample.in是光盘里对应题目的样例输入。如果输出和sample.out完全一致说明模板在本机跑通。这里有个习惯值得养成把样例输出放到另一个文件用diff比较而不是肉眼对。3.3 从“能跑”到“能交”头文件与输入输出的三处改造树状数组能跑通并不意味着交到 OJ 上一定通过。我踩过的坑通常集中在三处。第一处是头文件。光盘代码有时写#include bits/stdc.h这个头文件在多数 Linux 环境的 g 上能用但部分评测环境或商业编译套件不支持。常见做法是改成显式头文件像我 3.2 里那样只写需要的cstdio顺便把using namespace std;收窄减少命名冲突。第二处是输入输出。性能瓶颈多数发生在这cin/cout没关同步时10^5 量级可能无所谓到 10^6 就容易超时。优先用scanf/printf如果你偏爱流式输入加一句ios::sync_with_stdio(false); cin.tie(nullptr);也可以只是老代码里很少写这个。第三处是格式串与类型匹配。老代码里printf(%d)配int没问题但当你按第 5 章的建议把变量改成long long后格式串必须同步改成%lld否则输出就会变成一组乱码似的数字。这三处改完光盘模板才真正变成可提交状态。4. 从光盘到训练系统三种用法和参数取舍光盘里的代码是静止的训练系统是活的。所谓 tedukuri在我理解就是用双手把散落的模板重新编排形成自己能随时调用的素材集。这一章给三种可落地的用法投入产出比依次递增。4.1 用法一按算法类型重排目录而不是按章节光盘按书本章节组织目录但训练时我很少按章节复习——更常遇到的是“在做图论题时想快速找到并查集模板”此时按算法类型索引比按章节翻目录高效太多。常见做法是建algorithms/目录下面分>mkdir -p algorithms/{data-structure,graph,string,math} find ../disc/code -name *.cpp | while read f; do case $f in *DSU*|*union*) cp $f algorithms/data-structure/ ;; *dijkstra*|*spfa*) cp $f algorithms/graph/ ;; *kmp*|*ac*) cp $f algorithms/string/ ;; *) cp $f algorithms/math/ ;; esac done这里的关键在文件名匹配光盘文件的命名通常带有算法缩写如DSU、SPFA可以根据实际命名调整case分支。参数上我一般只复制不移动因为原始目录里还有章节对照信息删了后悔药就没有了。重排完成后再配合一个README.md记录每个文件对应的原章节后面查找时两步到位。重排脚本本身也可以留在tools/里以后收到新版代码重跑一遍即可。4.2 用法二为每个算法建一张“模板卡”模板要变成战斗力不能只停留在“能编译”得能回答四个问题复杂度多少、适用数据范围、边界条件、易错点。我给每种算法建一张模板卡存档为 Markdown和代码放在同一目录格式大致如下字段内容算法树状数组单点修改 区间查询复杂度建树 O(n log n)单操作 O(log n)适用规模下标 1..nn 通常不超过 10^6易错点下标必须从 1 开始更新和查询的步进都靠i (-i)查询idx0会死循环可扩展long long版本、离线离散化、二维树状数组这张卡的价值在于比赛现场你不需要重新推导扫一眼就能决定“这题能不能用”。我一般把模板卡的维护节奏定为每周一次周末花半小时把本周新学或翻车的点补进去。表里“易错点”一栏是最值钱的部分它记录的是踩坑记录而不是教材原文。随着模板库变大卡片会逐渐形成自己的索引我后来找代码基本不翻目录直接按“算法名 场景”搜卡片正文。4.3 用法三用光盘生成脚本做对拍验证模板正确性模板卡写得再漂亮跑不对就是零。验证模板最有效的是对拍一个暴力程序、一个待测程序、一个数据生成器三者跑上千组随机数据输出不一致立刻报错。光盘里的生成脚本刚好满足“数据生成器”这一环省得自己重写。#!/bin/bash # 用法先分别编译 brute 与 fast再运行本脚本 for round in $(seq 1 1000); do python3 gen.py input.txt ./brute input.txt ans_brute.txt ./fast input.txt ans_fast.txt if ! diff -q ans_brute.txt ans_fast.txt /dev/null; then echo 第 ${round} 轮数据不一致 break fi done参数说明seq 1 1000是随机对拍轮数我一般小模板跑 1000 轮涉及高精度或大数据结构的算法降到 200 轮因为单轮生成和运行成本会涨。gen.py务必注意随机种子常见做法是用系统时间或固定种子调试时固定种子可复现正式对拍再放开随机性。遇到break退出后保留input.txt和两份输出逐行核对是哪一类边界出问题——这个保留动作是排错的关键。对拍还有个渐进式技巧先用小规模数据跑通逻辑再把生成脚本里的规模参数调大观察待测程序和暴力程序的时间差距。如果小规模两者都秒出规模一大暴力程序开始变慢这正是期望中的表现如果待测程序也跟着明显变慢说明复杂度估错了回到模板卡修正复杂度那一栏。三种用法从“整理”到“验证”递进前两种半小时就能做完第三种需要先写好暴力程序但投入一小时换来的是往后所有模板的稳定信心值。5. 避坑清单光盘代码最常见的五个坑这些坑看起来玄学实际背后全是机制原因。以下五条是我和周围几个同学反复踩过的按现象、原因、解决三段式写方便你直接对照。5.1 现象本地能跑交到 OJ 超时现象模板在自己电脑秒出结果提交后总是 TLE。原因绝大多数不是算法复杂度问题而是输入输出方式。光盘老代码习惯用cin/cout本地数据量小感觉不到OJ 上 10^6 级别输入时流式 IO 的开销被放大好几倍。解决改用scanf/printf或者关闭流同步。如果题目输入格式复杂我常用一个快速读入模板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; }这个函数把字符流手动转成整数比scanf还要快一截代价是只能处理整数浮点输入时老老实实用scanf。判断超时原因还有一个笨办法但很有效本地用生成器造一份最大规模数据计时跑一遍如果本地耗时已经逼近时限就别怪评测机慢。5.2 现象编译报错错误定位在bits/stdc.h现象光盘代码第一行是#include bits/stdc.h本地 g 编译正常拿到部分评测环境却报“文件找不到”。原因这个头文件是 GNU 扩展不是 C 标准的一部分。评测环境如果用精简编译链自然没有它。解决把这一行替换成实际用到的标准头文件。比如只用vector、algorithm、cstdio就列三行别嫌麻烦可移植性反而更好。如果担心漏引某个头文件可以用第 3 章的批量编译日志做回归检查。另外这类环境差异还容易出现在#pragma once、register关键字上老代码里的register在新标准里已经被废弃编译时会产生警告直接删掉即可。5.3 现象数据一大答案变负数现象本地小样例全过放大数据范围后输出突然出现负数。原因整型溢出。光盘模板的变量很多是intn10^5、边权10^9时乘法或累加结果超过int上限。解决把涉及求和、乘法的变量改成long long乘法处写1LL * a * b强制转类型。常见做法是全局搜一遍int凡是参与累加的改成long long数组下标保持int不改。这里还有一个容易被忽略的关联点二分答案、最短路这类模板里INF经常设成0x3f3f3f3f但int的INF在long long场景不够用要改成0x3f3f3f3f3f3f3f3fLL否则dist w还会溢出成负数。5.4 现象书和光盘代码对不上现象看书里某段代码再打开光盘对应文件发现行数、细节都不一样。原因印刷版次不同。光盘在书印刷时已经刻好后续印刷修正的代码不会回到光盘里勘误表也只是文字记录。解决以在线勘误或源码更新为准光盘文件当作“历史版本”保留。我个人习惯是在重排目录时给每个文件加一个version注释记录它是从哪个版次的光盘来的之后即便有更新也好做对比。书和盘对不上还有一个常见副作用你照着书敲了一遍发现和盘里运行结果不同别急着怀疑编译器先查勘误表。5.5 现象生成脚本跑不起来提示无权限或格式错现象复制过来的gen.py在多数平台能跑某天换到别的机器却报权限错误或者读入数据多出\r。原因Windows 和 Linux 的换行符不一样脚本文件从 Windows 复制到 Linux 后行尾多了\r解释时出错或者脚本没有可执行权限。另外一个隐蔽情况是脚本输出重定向到input.txt时编码不一致导致后续程序读到乱码。解决先chmod x gen.py或python3 gen.py直接调用不必给可执行位再执行dos2unix gen.py清理换行符。养成习惯所有从光盘或 Windows 环境复制来的脚本落地第一件事就是转行符 试运行。这条在多人协作或换机器时特别容易踩别问我怎么知道的。6. 进阶把模板库沉淀成自己的 tedukuri走到这一步你已经完成了三件事光盘资源按算法重排、模板卡建档、对拍脚本验证。下一步是让它长期运转而不是堆完就扔。6.1 维护节奏定为“每周半小时”我给自己定的节奏是每周日晚上跑一次回归全库编译一遍对拍脚本随机跑 200 轮凡是这周新加的模板必须补一张模板卡。动作不大但能保证三个月后你翻开目录每个文件都是能跑的。如果某周偷懒没做下一周一定要补上否则欠账会像滚雪球一样让模板库重新变成死文件堆。6.2 从“复制”到“重写”模板卡里只放自己的话光盘代码是作者的表达你的模板卡应该写你自己的理解。比如树状数组我不会照抄书里解释我会写“更新时沿着 lowbit 往上加查询时沿着 lowbit 往左收idx0 会死循环所以下标必须从 1 开始。”三句话比赛时扫一眼就够。参数怎么改、数据范围多大、和哪些算法容易混淆这些才是卡片的核心代码本身反而可以只留一个文件名链接。我吃过不少模板“看着会、赛时翻车”的亏后来才想明白原因是教材讲解是串行叙述模板卡是离散索引复习效率差好几倍。建好这套 tedukuri 之后我赛前只看模板卡和易错点不再翻整本书。这套习惯谈不上炫技但很管用。希望帮到你。本文还有配套的精品资源点击获取
阅读完成 · 觉得有帮助？
