简介第四届百度之星决赛题目数据标程是面向ACM/ICPC与OI竞赛选手的官方配套资料完整提供了决赛各题目的输入输出数据与标准程序能够帮助选手熟悉赛题结构、命题风格与评测标准。压缩包共40个文件由10个输入文件.in、10个输出文件.out、10个Java标程和10个C标程组成整体大小2.06MB覆盖数据结构、图论、动态规划、贪心策略、字符串处理、数学应用等竞赛常见考点借助这些数据可自行搭建练习环境、验证算法正确性并对比两种语言实现思路。目前已有218人学习下载。通过研读标程与测试数据选手能深入理解决赛题目的设计思路、评分规则与复杂度要求训练快速建模、编码调试和临场应变能力为备战ACM/ICPC、NOI等高水平竞赛积累实战经验。1. 第四届百度之星决赛题目数据标程让官方数据替你揭穿 WA 的真相很多刷题的人卡在一个循环里题解看得懂代码写得出本地样例全过一提交就 WA而且永远不知道错在哪。这背后是大多数题解只给思路不给官方测试数据和标准程序。所以看到“第四届百度之星决赛题目数据标程”这类资源时我第一反应不是怀旧而是把它拆成三样东西分别用决赛题目负责定义问题测试数据负责暴露错误标程负责告诉你标准答案长什么样。这篇文章就讲这三者怎么配合以及怎么让它们变成一台能用的本地评测机。适合两类人准备算法竞赛的选手和想用真实难度题目做训练、却不想只靠平台黑匣子的求职者。2. 先拆资源决赛题目、测试数据、标程分别解决什么问题拿到一份旧竞赛题目数据标程第一件事不是急着打开代码而是先把目录结构整体过一遍。这类资料通常由三部分组成题目文本、按编号组织的输入输出数据、官方标程源码。它们解决的问题完全不同题目定义“做什么”数据定义“拿什么验证”标程定义“标准答案是什么”。把三者混在一起看效率很低。我习惯先把每一部分的可用性和边界评估清楚再决定用哪部分来训练这部分工作花不了多少时间但能避免后期对拍时找不到错位的根因。2.1 题目文本先别急着读先抓范围、时限、空间和格式题目文本是三个部分里信息密度最低的一个却是最容易看走眼的一个。我以前总从头到尾把题面读完才开始想算法后来发现这是效率最低的读题方式。正确顺序是先做参数抽取把数据范围、时间限制、空间限制、输入输出格式这四样东西单独抓出来它们共同决定了你能用什么复杂度级别的算法。参数从题面哪里找影响数据范围上限输入描述第一段决定算法复杂度上限时间限制题面顶部说明决定常数因子能不能大空间限制题面顶部说明决定能开多大数组输入格式细节输入描述与样例决定字符串解析方式比如同一道题n 上限是 10^5 还是 10^2算法选择完全不同。前者基本排除了 O(n^2) 的写法后者则允许更暴力的实现。所以我把参数抽取当成读题的第一步抽完再回来看算法逻辑思路会清晰很多。这一步很机械但值得养成习惯。如果题目文本是以纯文本形式单独存放的我会用一行命令先把数据范围相关的句子抓出来不用整篇翻grep -n -E n|m|最大|范围|10\^[0-9]|1e5|1e9 problem.txt | head -30这段脚本的逻辑是把题面文件里所有包含数据范围关键字和常见科学计数法写法的行筛选出来直接看命中结果省去从头读到尾的时间。参数说明-E 启用扩展正则head -30 限制最多输出 30 行防止文件里同名关键字太多刷屏命中行里通常会同时出现变量名和它的上限方便你判断哪些是真正影响复杂度的量。2.2 测试数据按编号读出门道小点、边界点、大点的识别方法测试数据是这三个部分里最容易被人忽略的。很多训练者只拿题目和标程走一遍数据文件看都不看这等于浪费了整套资源里最有诊断价值的部分。数据文件通常是按编号成对存放的一个输入文件配一个输出文件命名规则各套资料不统一。有的叫 1.in、1.out有的叫 case_01_input.txt、case_01_output.txt拿到手先不要猜直接列一遍最稳。for f in data/*.in; do echo $f : $(wc -l $f) 行, $(du -h $f | awk {print $1}) done这段脚本的逻辑是遍历 data 目录下所有 .in 文件打印每个文件的路径、行数和大小用一行输出概括一个数据点的体量。参数说明wc -l 统计文件行数行数直接对应输入数据的规模du -h 显示人类可读的文件大小awk {print $1} 只截取大小字段如果你要按数据规模排序只要把输出重定向到文件再 sort很容易找到边界点是哪一个。列完目录后我会按三个类别去看数据点。编号靠前的通常是样例或小规模数据用来确认程序能跑通基本流程中间编号里往往藏着边界用例要素数据、全相等数据、逆序数据、图不连通数据都爱出现在这一档末尾编号则是大数据专门考验复杂度和 IO 效率。对拍的时候不要盲目从 1 跑到末尾优先跑小数据验证正确性跑边界数据验证逻辑跑大数据验证性能这个顺序能让你快速定位问题到底出在哪一层。数据文件的这种组织规律不是某个人规定的但绝大多数竞赛数据都遵循同样的工程习惯你按这个思路去读会比随机打开几个文件看有效得多。2.3 标程的定位复杂度参照、答案生成器以及读它的顺序标程即标准程序是出题人写的参考实现。它的第一个作用是定义这道题的期望复杂度第二个作用是生成标准答案。很多选手把标程当“标准答案”来背这个定位从一开始就错了。标程证明的是题目可解、数据可跑不代表它是性能最优、风格最好的实现更不代表它就是唯一解。正确的用法是拿它做两件事一是对照复杂度二是当答案生成器。我在读一份标程之前会先花几十秒实测它的运行时间。数据文件里通常有最大的那个输入点拿它跑一下标程就能知道题库期望的时间线在哪里。time ./std data/10.in std.out这段脚本的逻辑是用 time 命令测量标程跑最大数据点的真实耗时输出重定向到文件时间统计的是程序完整执行时间。参数说明time 默认显示 real、user、sys 三项real 是墙钟时间最接近评测环境里的“运行时间”如果 real 已经和题目时限比如 10 秒接近说明标程本身就是卡线写法你写同复杂度代码就得严格控制常数如果 real 只是时限的 1/3说明同量级复杂度基本安全可以适当放松对常数的纠结。读标程的顺序也有讲究。我的习惯是先找 main 函数入口看它调用了哪些核心函数然后进入核心函数确认数据结构、循环层数和遍历方向最后才看输入输出处理段因为那段代码通常是工程性实现不承载算法思路。标程里的边界分支处理是它最有价值的地方那些在题面里不会写明的极端情况都会隐性地反映在代码里这部分值得花时间细看而不是扫一眼就过去。3. 搭一个能复现官方评测的本地环境从编译到批量自测拆完三个部分后下一步是把整套资源变成可以反复自测的本地环境。这一步没有技术难度但有不少细节决定对拍结果是否可信。我的做法是分成三层来做编译参数、批量执行脚本、输出比对规则。三层各解决一个问题任何一层出现偏差最后得出的 AC 结论都可能失真。这一章把三层逐一展开。3.1 编译参数别照抄-O2、-std 与 -static 到底在调什么本地编译老竞赛标程最保险的做法是用较新版本的 G然后选择合适的标准模式。我不建议直接用默认参数编译因为默认 -std 下的行为和老代码的期望标准多半对不上。找一个能兼容 C98 时代代码又支持新特性的折中标准通常能减少很多不必要的翻车。g -O2 -stdc11 -static -o main main.cpp这段命令的逻辑是把 main.cpp 编译成名为 main 的可执行文件开启竞赛评测常用的优化等级并用静态链接降低对运行环境动态库的依赖。参数说明-O2 对应竞赛评测的默认优化级别适合最终自测调试阶段建议改成 -O0 -g方便断点追踪-stdc11 是兼容老标程的保守选择既能编译 C98 风格代码也支持现代语法如果标程里用了 C17 特性再单独升版本-static 把标准库静态链进可执行文件避免换一台机器运行时缺 .so 文件。需要提醒的是-O2 和你日常写题用的 -O0 可能在浮点精度甚至整数溢出行为上有微妙差异。老标程在 -O0 下能过、在 -O2 下反而出错的案例并不少见所以最终自测阶段一定要用 -O2而不是一直停留在调试参数上。我见过有人拿调试编译版的测试结果去判断算法复杂度测出来的时间没有参考价值白跑一趟。提示调试和评测最好分成两条命令。调试用 -O0 -g自测用 -O2两者不要混用。3.2 批量自测脚本带超时、带耗时、跳过缺失数据单点测试一次只能验证一个数据点效率太低。决赛数据动辄几十个点全手动跑一遍既不现实也容易漏。我习惯写一个批量自测脚本把“跑数据、记耗时、判超时”这几件事合并成一个命令完成。#!/bin/bash mkdir -p out for i in $(seq 1 30); do indata/$i.in [ -f $in ] || continue start$(date %s%N) timeout 3 ./main $in out/$i.out 2/dev/null code$? end$(date %s%N) cost$(( (end - start) / 1000000 )) if [ $code -eq 124 ]; then echo case $i: TLE (${cost}ms) else echo case $i: exit$code (${cost}ms) fi done这段脚本的逻辑是依次处理 data 目录下按序号命名的输入文件跳过不存在的文件每个数据点最多跑 3 秒超时直接记录为 TLE正常退出则打印退出码和实际耗时。参数说明timeout 3 表示 3 秒超时返回码 124 代表超时date %s%N 取纳秒级时间戳两次时间戳相减再除以 1000000 得到毫秒数[ -f $in ] 判断文件是否存在防止数据编号不连续时脚本中断2/dev/null 丢弃程序自身的错误输出避免日志干扰结果列表。这个脚本输出的每一行对应一个数据点的测试结论。exit0 且输出比对通过基本可以判定 ACexit 非 0 说明程序崩溃或返回了异常值下一步要看崩溃发生在小数据还是大数据上。小数据崩溃多半是逻辑问题大数据崩溃多半是栈溢出或内存访问越界。配合后面要讲的 diff 环节这个脚本就是一台最小可用的本地评测机。3.3 输出比对diff 的三个变体与什么时候用严格模式跑完数据之后最重要的一步是输出比对。很多人在这一步用裸 diff结果被换行符和空白字符坑得体无完肤。算法题的输出判定的确有一些约定俗成的宽容度但作为自测环境我建议先严格比对把差异显式暴露出来再由你判断哪些差异是可以接受的。diff --strip-trailing-cr -q data/$i.out out/$i.out echo AC || echo WA这段命令的逻辑是把标准输出文件和你程序跑出来的输出文件做逐字符比较忽略行尾的 CR 字符结果用退出码表达。 和 || 把退出码翻译成 AC 或 WA 输出。参数说明--strip-trailing-cr 会忽略 Windows 换行符CR带来的差异这条参数在处理老数据文件时几乎是必需品-q 只返回是否相同不打印具体差异适合批量判断如果你想知道哪里不同去掉 -q配合 head 限制输出行数即可。还有一种常见做法是用 diff -w 忽略所有空白字符差异。我一般不建议这么做因为 -w 会把一行里多余的内部空格也忽略掉极端情况下两组语义不同的输出会被误判为相同。更稳妥的方案是先用严格比对找到差异再用肉眼判断差异是否合法。把这一步想清楚后整套本地评测流程就跑通了。接下来真正花时间的是那些让老数据在你机器上跑不起来的坑。4. 旧竞赛数据标程避坑清单五个翻车点与补救办法旧竞赛资源的坑集中在数据格式、编译器兼容性、运行环境差异这三个维度。下面五条是我在折腾这些老资料时踩过或帮别人排查过的典型问题每一条都按现象、原因、解决的顺序写清楚。你在本地搭环境时遇到类似报错可以直接对照处理。4.1 编译失败老头文件写法被新编译器拒绝现象标程源码在本地编译报错 fatal error: vector.h: No such file or directory后续还会连着一串找不到头文件的错误。用过旧 C 的人一眼就能认出问题但新手很容易卡在这第一步。原因早年很多标程沿用了 C 风格的带 .h 后缀头文件写法例如 vector.h、map.h、algorithm.h。C 标准化之后标准库头文件不再带 .h 后缀现代编译器只提供 、、 这些正规形式旧写法自然编译不过。解决把所有带 .h 后缀的 C 标准库头文件改成不带后缀的写法并在文件开头补上 using namespace std;。例如 #include vector.h 改成 #include map.h、set.h 同理。改动风险极低因为这些旧头文件和标准库的接口基本一致只是文件名变了。改完之后重新编译通常能直接通过。4.2 全 WA 的假象CRLF 与 LF 换行差异现象批量对拍结果出来一片 WA但打开输出文件和标准输出文件对比肉眼完全看不出区别。逐字节看才发现每行行尾都不一样。原因资料里的 .out 文件很大概率是在 Windows 环境下生成或保存的换行符是 CRLF你在 Linux 下编译运行的程序输出的是 LF。diff 是按字节比较的每一个行尾的 CR 都会被当成差异于是所有数据点全部判失败。解决最简单的处理是在 diff 命令里加 --strip-trailing-cr把行尾 CR 忽略掉。如果你要长期用这套数据做对拍建议直接把数据文件统一转成 LFsed -i s/\r$// data/*.out这段命令的逻辑是用 sed 把 data 目录下所有输出文件行尾的 \r 删除。参数说明-i 表示就地修改s/\r$// 匹配行尾的 CR 字符并替换为空。转换之后后续所有工具和脚本都不需要再考虑换行符差异比每次敲 diff 参数更省心。4.3 数据文件跳号编号连续不代表文件成对现象批量脚本按 1 到 20 的编号循环跑到一半突然少了某个文件脚本要么报错中断要么直接跳过。还有更隐蔽的情况输入文件有输出文件缺失脚本跑完才发现某一组数据无法判定。原因资料在多次打包和传输过程中部分数据点被抽走或单独存放过。比如 7 号数据缺失但 6 号和 8 号还在目录看起来仍然井然有序只有统计成对关系时才会暴露问题。解决提前列出所有文件按成对关系做一次检查。我一般会用一段短脚本扫描ls data/*.in | sed s/\.in$// /tmp/inputs while read base; do if [ ! -f ${base}.out ]; then echo missing ${base}.out fi done /tmp/inputs这段脚本的逻辑是把所有输入文件的路径去掉 .in 后缀再逐个检查同名 .out 文件是否存在缺失的会打印出来。参数说明sed s/.in$// 把每行末尾的 .in 去掉while read 逐行读取清理后的列表[ ! -f ... ] 判断文件不存在。跑完一遍你就能知道哪几个数据点是残缺的对拍脚本里也应该用文件存在性判断来跳过它们。4.4 深搜爆栈本地默认栈空间和评测环境差太多现象深搜或递归类算法在小数据点一切正常切到大数据点一跑就段错误退出码 139。怀疑过数组越界检查之后并没有越界最终定位在递归栈上。原因Linux 默认进程栈空间通常是 8MB而竞赛评测环境往往会显式扩大到 256MB 甚至更高。老标程里如果存在深度与数据规模同量级的递归比如深度 10^5 的 DFS在本地默认栈下直接爆栈在评测环境里却能正常跑完。解决本地复现评测环境时先用 ulimit -s 256 把栈临时扩大到 256MB再跑程序确认问题确实出在栈空间上。如果你不想依赖大栈最彻底的办法是在重写代码时把深搜改成显式栈模拟。这个改动量往往不大但能让程序在任何环境下都稳定运行我建议对自己写的版本做这一步而不是去改标程。4.5 diff 不适用多解题目必须写 checker现象自己重写的实现逻辑上确认无误输出也符合题意但和标程输出 diff 永远对不上。反复检查代码好几个小时找不到任何逻辑漏洞。原因题目允许多组合法解标程只是输出了它自己找到的那一组。图论选路、构造、搜索类问题特别容易出现这种情况两组输出都合法但内容不同diff 逐字符比较的模式在这里只会误判。解决放弃 diff为这类题写一个 checker 程序。checker 读入题目输入、你的输出和一组约束条件只判断输出是否合法不要求与某个具体答案完全一致。写 checker 时从标准输出文件里提取判定规则比如路径是否连通、总和是否最小、数列是否非降把它们转成代码里的断言。这个投入比反复对 diff 值多了因为问题本身就不是比对问题而是验证问题。5. 三步吃透一份标程从读代码到独立复现老标程的真正价值在于它把官方的思考路径用一种可运行的方式固定下来了。题目数据可以被你反复跑但只有标程能从代码层面告诉你出题人是怎么设计状态和转移的。这一章讲我读标程的三步方法核心思路是先搭骨架、再挖边界、最后独立复现验证。三步做完一份标程才算真正消化掉。5.1 先搭骨架图用 grep 找出函数入口和核心调用读标程最忌讳从头读到尾一行行顺序过一遍。人的短期记忆撑不住那么长的陌生代码读到后面前面讲过什么已经忘了。我拿到一份新的标程源码第一件是搭骨架图先知道这个程序由哪些函数组成谁调用谁再决定从哪里深入。grep -n int main\|void solve\|bool check\|int dfs std.cpp | head -20这段命令的逻辑是在标程源码里搜索主函数和核心函数名的定义位置输出行号快速建立函数分布图。参数说明-n 显示行号方便直接跳到目标行精读多个匹配模式用 | 分隔把最常见的入口函数都覆盖进来head -20 限制输出行数防止匹配过多刷屏。如果标程函数命名不规律可以进一步用 grep -n {. 但大多数标程会包含 main、solve、check、dfs 这类通用名字这批词命中率最高。骨架搭好之后按调用关系深入。先读没有被其他函数调用的入口函数再读它直接调用的子函数。看函数体时只关注三件事数据结构、循环嵌套层数、分支条件。数据结构决定空间复杂度循环层数决定时间复杂度分支条件决定边界处理是否完整。这三件事想清楚算法类型基本就定型了。输入输出处理放在最后看因为解析逻辑大多雷同不值得最先投入注意力。5.2 用边界数据反推分支临时日志的正确打法读代码时最容易漏掉的是边界分支的处理方式。出题人在代码里怎么写 n 等于 0、数组全相等、图有多个连通块这些分支往往只有几行但恰恰是出题人想考的部分。光靠眼睛看代码容易忽视它们我习惯用数据来逼出这些分支。选取一个边界数据点然后在标程里临时加输出观察这段代码实际走了哪条路fprintf(stderr, debug: n%d low%d high%d\n, n, low, high);这段代码的逻辑是把关键变量的值输出到标准错误流用于判断程序当前执行路径。参数说明用 stderr 而不是 stdout 输出原因是标准错误流不会影响对拍时对标准输出的比对你加了调试日志也不需要额外处理后患n、low、high 只是示例变量实际使用时替换成你想观察的状态变量跑完边界数据后记得把这一行删掉或注释掉避免污染最终代码。具体的做法是先挑三个数据点分别是规模最小的输入、结构最特殊的输入、规模最大的输入分别加上调试日志跑一遍。对比三条路径中分支条件的取值变化你就能精确知道哪段代码在什么条件下被触发。这比盯着代码猜要快得多尤其是处理那些只在中后段数据点才会触发的隐蔽分支。5.3 不看标程重写一版再自动对拍看懂标程和会写一道题之间的距离比大部分人想象的大。我看完标程后不会马上模仿着写而是合上源码用自己的话重新实现一遍。这个过程强迫你把标程里的算法结构转成自己能表达的逻辑转不出来或者转出来有差异的地方就是你还没学会的部分。重写完成后下一步是自动对拍#!/bin/bash for i in $(seq 1 10); do ./std data/$i.in std.out ./my data/$i.in my.out if diff -q std.out my.out /dev/null; then echo $i AC else echo $i WA diff std.out my.out | head -20 break fi done这段脚本的逻辑是把官方标程编译成名为 std 的可执行文件自己重写的版本编译成 my逐个数据点比较输出遇到不一致就打印差异并中断方便定位问题。参数说明diff -q 只比较输出是否一致不打印内容一旦查询到不一致后面的 diff 命令会把差异的前 20 行打印出来head -20 防止大数据输出刷爆终端break 让脚本在第一个失败点停下来避免继续跑后面无关的数据。对拍通过只代表你解决了固定数据集的验证。要增强说服力还需要把验证范围扩展到随机数据上这就是下一章要展开的对拍增强技巧。固定数据集的优势是边界案例齐全劣势是数量有限真正难的问题往往藏在你没有覆盖到的随机组合里。6. 让标程当裁判写一个能长期复用的对拍脚本6.1 随机数据对拍从固定数据到持续校验固定数据点再多测完一遍也就结束了。我现在的习惯是只要手上有标程不管题目来自哪里都会顺手搭一个随机对拍环境。随机对拍的核心是用数据生成器不断制造新的输入让标程和你的实现同步跑任何一处输出不一致都是送上门来的 bug 线索。这个方法的价值在于它不需要等官方数据也不需要人工构造样例机器会替你把组合爆炸的输入空间扫一遍。6.2 生成器要贴合题面约束先跑标程验证生成器随机对拍的前提是数据生成器必须严格遵守题面约束。生成器一旦生成了范围外的数据标程和你的实现会同时翻车反而浪费整晚。我写生成器有个固定习惯生成规则里每个随机范围都和题面参数一一对应写完先用标程跑一遍生成器输出的数据确认标程能正常产出答案再开始对拍。import random n random.choice([1, 2, 5, 10, 100, 100000]) print(n) for _ in range(n): print(random.randint(1, 10**9))这段脚本的逻辑是随机生成输入数据的规模 n再从一组候选值中挑一个作为当前数据点的大小随后输出 n 个随机数。参数说明random.choice 里的候选值需要按题面里的数据范围上限手动调整把题目允许的边界值和典型中等规模都放进去random.randint(1, 10**9) 控制数值范围也要对应题面里变量上下限来修改。这段只做演示真正使用时要把所有输入变量按题面结构生成出来少一个字段生成器就会作废。配套的对拍脚本长这样#!/bin/bash for i in $(seq 1 500); do python3 gen.py in.txt ./std in.txt std.out 2/dev/null ./my in.txt my.out 2/dev/null if ! diff -q std.out my.out /dev/null; then echo found mismatch at round $i break fi done echo done这段脚本的逻辑是每一轮用生成器产生新数据让标程和你的实现分别跑diff 结果不一致就记录轮次并停止。参数说明seq 1 500 控制最多跑 500 轮实际可以按需调大2/dev/null 丢弃两个程序的标准错误输出避免调试日志干扰in.txt、std.out、my.out 是每轮的临时文件下一轮自动覆盖不需要手动清理。对拍一轮跑完如果 500 轮内没有发现差异值得把轮次加大到几千甚至上万。多解题目要另外配置 checker不能用 diff 硬比上一章已经说过这个边界。这套随机对拍的习惯目前是我处理算法训练数据最依赖的验证手段。它不要求数据文件多齐全只要有一个可用的标程和一份题面约束说明就能构建出高频次的持续校验。我的个人经验是与其花大量时间人肉构造边界数据不如把这些时间花在写好一个生成器和一套对拍脚本上机器替你试错远比人肉试错来得彻底。希望这个流程对你有实际帮助。本文还有配套的精品资源点击获取