简介2017年HDU多校联合训练第一场的官方标程与完整测试数据面向备战ACM竞赛的大学生及算法爱好者也适合教练用于组织模拟训练。压缩包共40个文件包体36.69MB包含15份C标程、12组输入数据及12份对应输出另附一个可执行验证程序。标程覆盖该场次多道赛题的标准解法其中含verify校验版本与spj特判程序可帮助读者理解题目的特殊判定逻辑配套的in/out数据支持在本地运行程序后逐组比对结果便于排查边界条件与算法缺陷。目前已有450人学习下载对于希望系统复盘官方思路、提升解题速度与代码稳健性的选手是一份可反复研读的实战资料通过对比多份标程的实现差异还能进一步掌握常见算法的多种优化手法。1. 2017hdu多校联合训练第一场这套标程和数据值得拆开看一遍每年七月底备赛区域赛的队伍都会盯着HDU的多校联合训练。2017hdu多校联合训练第一场是当年暑期的开场硬战打完一场网上流传的不只是题解还有一套官方标程和全部测试数据。对绝大多数人来说这套数据才是真正值钱的部分它能让你从“看题解觉得自己会了”变成“对拍跑通后确认自己真的会”。这篇文章不打算复述题目而是把“标程及数据”这个资源怎么拆、怎么跑、怎么用来对拍讲清楚。适合谁准备暑期训练的ACM选手、带队的教练以及想拿现成题做回归测试的工程师。2. 拿到资源先别急着跑先看懂标程与数据的目录结构2.1 一套多校资源的标准结构题面、标程、数据三件套2017多校的资源包通常不是一个文件而是一个压缩包。解压后会看到若干按题号命名的目录。常见做法是以题号HDU OJ 上的题目编号作为目录名目录内放题面 PDF 或 HTML、标程源码以及若干数据文件。比如你解压后第一步应该做的是先看一下全貌unzip 2017-multi-university-round1.zip -d round1 cd round1 find . -maxdepth 2 -type f | head -40这条命令把压缩包解压到round1目录然后列出两层以内的全部文件只看前 40 行。-maxdepth 2是限制查找深度防止题目目录里的临时文件把终端刷爆-type f只显示普通文件不显示目录head -40是截断输出。如果解压过程出现乱码文件名多半是压缩包用了 GBK 编码建议在 Linux 下用unzip -O gbk再解一次。我自己在 Windows 解压后拷到 Linux 上经常遇到这类问题。资源包的排布方式大致可分两种。第一种是根目录下只有一个solutions/和一个data/所有标程平铺在solutions/里数据按data/1.in、data/1.out这样的编号集中存放第二种是按题目分子目录比如6052/里面既有solution.cpp也有data/或testcase/子目录。先搞清是哪种比直接写评测脚本重要得多因为评测脚本必须同时处理“数据目录在哪”和“源文件叫什么”两个变量。实际包内文件命名千奇百怪题面可能叫1001.pdf、statement.md标程可能叫main.cpp、solution.cpp、std.cpp数据可能是1.in/1.out也可能是input/input1.txt/output1.txt。不要在脚本里写死某一个名字而是先跑一遍上面那句find把命名规律看清楚再动手。我见过最离谱的包把数据放在.h文件里导致评测脚本怎么都找不到.in文件最后发现是出题人把测试点序列化之后放到了头文件里。2.2 用题号绑定本地目录从HDU OJ比赛页对回每一道题多校第一场在 HDU OJ 上有正式比赛页面每道题有公开题号和标题。本地资源包里目录名如果写的是“A、B、C”而不是题号就需要手动绑定。我一般会写一个bind_titles.py把比赛页的题目列表保存成文本然后扫描本地目录生成一份“题号-目录名-标题”的映射表。先把比赛页的题目列表存成problem_list.txt每行一个题号加标题用 Tab 分隔例如6052 Curvy Little Bottle 6053 Killer Names然后运行下面这个 Python 脚本#!/usr/bin/env python3 # bind_titles.py把本地题目目录与比赛题号绑定起来 import re, sys, pathlib mapping {} with open(problem_list.txt, encodingutf-8) as fp: for line in fp: parts line.rstrip(\n).split(\t) if len(parts) 2: mapping[parts[0]] parts[1] for p in sorted(pathlib.Path(.).iterdir()): if not p.is_dir(): continue m re.search(r(\d{4}), p.name) if not m: continue pid m.group(1) title mapping.get(pid, 未匹配) print(f{pid}\t{title}\t{p})脚本逻辑很简单先读映射表再用正则从目录名里抓 4 位数字当作题号最后把题号、标题、路径一起打印出来。正则\d{4}是按 HDU 多校题号通常是 4 到 5 位数字设计的如果你的目录名是Problem03这种两位编号把正则改成\d{2}即可。mapping.get(pid, 未匹配)的默认值很有用它会把可能有题号但没在比赛页名单里的目录也标出来方便你去人工核对。为什么我强调用本地脚本而不是直接爬 HDU 比赛页一方面2017 年的比赛页到今天仍然能访问但频繁请求容易被限流把列表存成文本再跑脚本是最稳的做法。另一方面本地目录名和题目编号经常对不上比如有人喜欢叫A/B/C有人叫1001/1002脚本扫出来之后你一眼就能看出哪些目录缺少数据文件。这张映射表后面写评测脚本时也会用到所以这一步不要跳。2.3 数据命名与多测试点关系什么时候一个题有几十个in/out对ACM 数据通常分两种组织方式。一种是一个题对应多个测试点文件每个测试点是一组完整输入程序读完后必须自己处理“多组测试用例直到 EOF”的结构另一种是整个题只有一个大input.txt和output.txt里面串联多组测试用例。两种方式下评测脚本的写法完全不同所以要先用统计脚本判断数据包到底是哪一种。多文件形式最直观data/1.in和data/1.out配对循环跑每个.in文件就行。单文件多测试点形式则要小心input.txt可能几百 MB程序必须流式处理评测时也只比较最终输出。判断一个数据包是哪一种先看看目录里的文件个数和行数for f in data/*.in; do printf %s %8.2f MB %6d lines\n $f $(du -k $f | awk {print $1/1024}) $(wc -l $f) done | sort -k2 -n这里du -k以 KB 为单位取文件大小除以 1024 转成 MBwc -l统计行数。为什么不用du -h因为1.2M和900K这种字符串没法按数字排序用du -k拿到纯数字才能交给sort -k2 -n。排序后你会看到一个清晰的尺度分布大部分点很小一两个点特别大那特别大的通常是极限数据对拍时最值得盯着它。如果你发现某个数据目录里只有input.txt和output.txt没有拆分好的1.in那它就是“单文件多测试点”格式。这种格式下评测脚本不能把每个文件当成一组用例只能把整个文件跑完再统一比较。判断逻辑也简单如果一个题有几十个.in文件那就是多点拆分如果只有一两个多半是整包式。还有少数包会在数据文件开头用第一行写测试组数T后面才是各组输入这种题目用多文件格式时评测脚本需要在每个.in文件里读T但比较输出时无需关心因为输出已经包含了所有组的答案。3. 从编译到跑通用最小脚本把标程和数据变成可复现评测3.1 先跑单个题g 编译、重定向输入输出、diff 对比最朴素但最可靠的单题评测流程进入题目目录、编译标程、对每个数据点跑一遍、用diff比较输出。我在日常复现时不会一上来整自动化而是先单题跑通一个数据点确认没有环境问题再批量。cd round1/6052 g -O2 -stdc14 solution.cpp -o solution mkdir -p myout ./solution data/1.in myout/1.out diff -bB data/1.out myout/1.out echo accept这里-O2是优化等级和 OJ 评测机行为一致-stdc14是 2017 年多校常用的标准如果标程用了 C17 语法就换成-stdc17。和是 shell 重定向把data/1.in当作标准输入把程序输出写到myout/1.out。diff -bB忽略空白数量和文件末尾空行差异这正是 ACM 比较输出的常见宽容模式。diff退出码为 0 就输出accept非 0 说明该点不一致。如果编译报错先别急着怀疑标程有问题。2017 年的标程很多是用旧版 G 写的可能用了bits/stdc.h或者非标准扩展。把报错限制在前 30 行看g -O2 -stdc14 solution.cpp -o solution 21 | head -3021把标准错误也并进标准输出head -30截断头部。模板报错通常会刷屏几千行直接看第一行“error:”位置比翻满屏更有用。常见的坑是scanf没写#include cstdio但写的是#include bits/stdc.h这种包在较新版本 GCC 下也能编译不用管。真正要改的是main返回类型或者某个结构体的构造函数看到报错位置再修。3.2 批量评测整场题目for循环、timeout、结果汇总表整场题少则 8 道多则 12 道每道题又有若干个数据点手动跑不现实。用脚本批量跑是唯一正经做法。我习惯用 Python 而不是纯 bash因为要处理路径差异和汇总结果。下面是一个直接能用的judge_all.py#!/usr/bin/env python3 import subprocess, sys, pathlib, tempfile, os round_dir pathlib.Path(sys.argv[1]) if len(sys.argv) 1 else pathlib.Path(.) timeout_sec int(sys.argv[2]) if len(sys.argv) 2 else 20 results {} for prob in sorted(round_dir.iterdir()): if not prob.is_dir(): continue cpps list(prob.glob(*.cpp)) if not cpps: continue src cpps[0] exe prob / solution subprocess.run([g, -O2, -stdc14, str(src), -o, str(exe)], checkTrue, capture_outputTrue) data_dir next((prob / d for d in (data, testcase, cases) if (prob / d).is_dir()), None) if not data_dir: print(f{prob.name}: no data dir) continue in_files sorted(data_dir.glob(*.in)) pass_cnt fail_cnt 0 for in_file in in_files: out_file in_file.with_suffix(.out) if not out_file.exists(): continue try: cp subprocess.run([str(exe)], stdinopen(in_file), stdoutsubprocess.PIPE, stderrsubprocess.PIPE, timeouttimeout_sec) except subprocess.TimeoutExpired: print(f{prob.name} | {in_file.name} | timeout) fail_cnt 1 continue if cp.returncode ! 0: print(f{prob.name} | {in_file.name} | runtime error) fail_cnt 1 continue with tempfile.NamedTemporaryFile(wb, deleteFalse) as tmp: tmp.write(cp.stdout) tmp_name tmp.name cmp_ret subprocess.run([diff, -bB, str(out_file), tmp_name], capture_outputTrue).returncode os.unlink(tmp_name) if cmp_ret 0: pass_cnt 1 else: fail_cnt 1 print(f{prob.name} | {in_file.name} | output mismatch) print(f{prob.name}: pass {pass_cnt}, fail {fail_cnt}) results[prob.name] {pass: pass_cnt, fail: fail_cnt}脚本的大致流程遍历根目录下每个子目录找第一个.cpp文件当成标程编译再从data、testcase、cases里挑一个存在的目录作为数据目录最后对每个.in文件跑程序输出写到临时文件再和对应的.out做diff。值得注意的几个点编译用checkTrue编译失败会直接抛异常这样不会出现“跑了半个赛季才发现某个题没编译出来”的尴尬timeouttimeout_sec是防止某个数据点死循环把整个批量任务卡死临时文件用tempfile.NamedTemporaryFile生成最后用os.unlink删掉不在源码目录留垃圾。跑的时候传参很简单python3 judge_all.py round1 20第一个参数是题目根目录第二个参数是单点超时秒数。如果你的某个题数据特别大比如极限数据有 100 万行20秒可能不够可以单独先跑该题看看耗时再决定要不要整体调大。3.3 评测脚本的3个必调参数timeout、diff 模式和数据目录批量脚本能跑起来只是第一步真正决定评测结果可不可信的是这三个参数。第一个是timeout_sec默认 20 秒只适合大部分常规题但碰上数据规模大的模拟题标程跑 10 秒以上很正常。建议先用time命令手动跑一组数据看基线time ./solution data/max.in /dev/nulltime输出的real是墙钟时间user是 CPU 时间。如果user已经到 15 秒那批量脚本里的 20 秒就很危险网络负载高一点就会误报 timeout。这种情况我会把timeout_sec调到 60甚至 120宁可多等也不能误伤。第二个是diff模式。上面的脚本统一用diff -bB它忽略行尾空白的数量差异和空行差异但不会忽略行首缩进。如果题目输出的是矩阵多一个空格在 OJ 上通常是 WA用diff -bB正好能复现这种严格判断。但有些题目只关心数值答案比如输出一个浮点数保留三位小数这时候你可以把比较模式改成diff -w连行内多余空格一起忽略。不同模式对应不同场景比较模式diff参数什么时候用严格精确diff题目明确要求输出格式完全一致忽略行尾空白diff -b常见 ACM 判题模式推荐默认忽略所有空白diff -w你只关心答案数值不关心排版第三个是数据目录的选择。不同资源包叫data、testcase、cases的都有脚本里用next()按优先顺序挑一个存在的目录这样换一个包也能跑。如果你拿到的包是“单文件多测试点”格式这里的.in遍历就匹配不上了需要单独写一个只比较input.txt和output.txt的分支不要混用一个逻辑。4. 对拍和评测的5个常见翻车点与避坑手册4.1 对拍脚本怎么写用随机数据生成器把标程和你的代码搅在一起所谓对拍就是拿官方标程和你的代码在同一个随机输入上分别运行然后比较输出。标程是“标准答案”但你不该只拿它做单次对比而要用随机生成器制造出尽可能多的输入逼出两个程序的分歧。最朴素的对拍循环长这样# 编译两份代码 g -O2 -stdc14 std.cpp -o std g -O2 -stdc14 my.cpp -o my # 生成随机数据并循环 for i in $(seq 1 1000); do python3 gen.py input.txt ./std input.txt output_std.txt ./my input.txt output_my.txt if ! diff -bB output_std.txt output_my.txt /dev/null; then echo 第 $i 组数据不一致已保留 input.txt break fi done这个循环的价值不在于一次跑多少组而在于当它停下来时input.txt就是你最宝贵的调试材料。seq 1 1000可以换成seq 1 50000做压力测试每轮生成和运行都很快瓶颈通常只在diff所以用/dev/null丢弃 diff 输出。如果跑了几百组都不出错再换上更刁钻的数据范围继续压。生成器写得好不好直接决定对拍有没有意义。下面是一段最简单的随机数据生成器# gen.py生成一个 n 和 n 个整数的输入 import random n random.randint(1, 10**5) print(n) for _ in range(n): print(random.randint(-10**9, 10**9))生成器必须严格遵循题目输入格式尤其注意n的范围要贴合题面。很多人习惯把n固定成最大值结果永远只测到“大数据”漏掉了n1、n2这种边界。更稳的做法是让n从 1 到上限之间随机取再用另一套生成器专门生成边界值比如正好等于 1、正好等于上限、以及上限附近的值。4.2 坑1标程也超时先看数据文件是不是真的大现象标程在官方数据上跑出了超过 10 秒的成绩你怀疑官方标程写得差但其实问题出在评测脚本上。原因某个数据点文件可能几百 MB标程本身是流式处理跑得并不慢但你的脚本把输出写到临时文件再做diffIO 成了隐藏瓶颈。尤其是diff一个几百 MB 的输出文件时间比运行程序还长。解决用time分开测“运行程序”和“diff”的时间time ./solution data/max.in /tmp/max.out time diff data/max.out /tmp/max.out如果diff占了一大半时间就把输出重定向到内存盘/dev/shm或者干脆把 diff 放在对所有数据点循环完之后做只对失败点做细致对比。这条经验在跑大数据集时特别值钱。4.3 坑2Windows 数据文件的换行符在 Linux 下造成 diff 全线飘红现象本地明明通过了样例但批量评测时每个数据点都报 output mismatch打开 diff 看却只有最后一行的\ No newline at end of file或者整行后面多了一个^M。原因资源包从 Windows 机器打包.out文件是\r\n结尾而 Linux 下标程输出是\n。diff -b在某些版本下会忽略\r但diff -bB不一定全忽略于是每个文件都被判不通过。解决评测前先把所有.in和.out统一转成 LFsed -i s/\r$// data/*.in data/*.outsed -i会直接改文件建议先复制一份原始数据做备份。如果你拿到的是zip包解压时用unzip加-a参数也能自动转换文本换行符但从数据完整性的角度我更喜欢看得到摸得着的备份。4.4 坑3混用 scanf 和 cin对拍结果在数据量上来后全线错乱现象随机数据量小的时候对拍一直通过一旦n加大输出开始出现错位甚至同一份输入两次运行结果不同。原因标程里用了scanf你的代码里cin和scanf混用而没有关掉 C 和 C 的 IO 同步。混用两种 IO 体系会导致读入顺序不确定表现就是玄学一般的随机错乱。这个坑在 C 选手身上属于血泪级别。解决统一 IO 方式。要么全部用cin并在main开头加一行ios::sync_with_stdio(false); cin.tie(nullptr);要么全部用scanf不要混着来。对拍脚本本身帮不了这个忙但一旦你发现小数据对、大数据乱的规律第一反应就该检查 IO 混用而不是怀疑算法写错。4.5 坑4数据包不完整标程在官方数据上也翻车现象官方数据明明有几十组但标程跑挂了一两组你以为是资源包下错了。原因网上流传的多校资源包有时只放“样例数据”或“部分测试点”并不是一次完整提交里的全部测试数据。标程本身可能只提交了部分测试点另一个隐藏测试点的答案可能和标程给出的输出不一致。解决别去修标程。用对拍生成随机数据把标程当参考实现压测。如果标程在随机数据上 WA先检查生成器是否越界了题面约束比如题面说n 10^5你生成了n 10^9。如果没越界那就是标程存在边界 bug记录这一组输入但这时你自己的代码更值得信赖。4.6 坑5隐藏文件和文件名后缀在不经意间让脚本白跑现象批量评测时某个题显示 pass 0fail 0脚本什么都没报错但就是没跑任何一个数据点。原因数据目录里混入了__MACOSX隐藏文件夹或者.in文件实际叫input1.in.txtglob(*.in)匹配不到。Mac 解压zip生成的__MACOSX目录里全是资源派生文件会把遍历逻辑搅乱。解决先用find全盘列出真实文件名find data -type f | head -20看清后缀再做匹配。如果确实混入了隐藏目录批量脚本里过滤掉data_dir next((d for d in prob.iterdir() if d.is_dir() and not d.name.startswith(__)), None)这个startswith(__)判断虽小能省掉你排查诡异行为的大把时间。5. 拿到标程后的三个月我还在用这套数据做的三件事第一件事是把官方数据当成回归基线。每次改代码都跑一遍这场的全部数据点防止改了新逻辑把老功能破坏掉。不需要每次都跑完整对拍只要跑一遍第 3 章的judge_all.py看 pass/fail 数有没有掉。这套数据本身就是最好的测试集比你自己攒的样例覆盖面广得多。第二件事是用数据规模反推算法再把标程当复杂度对照。统计每个数据点的最大n比如排序后看到一两个特别大的点就明白这道题必须做到O(n log n)如果所有点都很小可能允许O(n^2)。这个判断在赛后复盘时非常有用能帮你快速估算自己在考场上时间分配是否合理。第三件事是把随机数据生成器沉淀成自己的武器库。2017 年这套题的生成器写好之后后面的多校场次我都是先写生成器再写代码而不是先写代码再补数据。数据生成器比代码更值得保留因为它逼你先把输入边界想清楚。数据特征推测算法要求验证方式最大 n 10^5O(n log n) 可过压测 n 10^5 随机数据多组输入直到 EOF每组初始化要干净重点看第一组和最后一组输出含浮点数可能需要 eps 比较写特判或调 diff 模式我现在的习惯是拿到任何一场多校的“标程及数据”先跑一遍官方数据确认标程能过再写自己的代码最后用随机生成器交叉对拍。以前我拿到标程直接开刷结果被一个隐藏的初始化 bug 坑了半个赛季后来才明白最值钱的是数据里的边界。这套方法论我从 2017 年用到现在希望帮到你。本文还有配套的精品资源点击获取