★ FEATURED ARTICLE 简介2017年杭电多校联合训练第一场的官方标程与测试数据面向备战ACM竞赛的学生、高校算法爱好者及需要刷题复盘的程序员旨在提供完整的赛题复盘资料。压缩包内共40个文件包括15份cpp标准解答、12组in输入文件与12份out期望输出外加1个用于数据校验的exe程序整体大小约36.69MB。所有题目对应完整标程覆盖12道赛题的多种算法思路数据文件则可直接用于本地自测与结果比对帮助读者定位程序边界问题。目前已有450人学习下载。无论是初次接触ACM的新手还是希望提升竞赛水平的选手都能从中理解官方解题策略并通过实际数据验证与优化自己的代码。1. 多校联合训练第一场标程这份资源不是给你对答案的多数人拿到多校赛的标程包第一反应是把代码打开看一遍然后感叹“原来官方是这么写的”随手就关掉了。我拿到这套第一场的标程和数据时反而先建好目录、批量跑了一遍本地验证发现真正值钱的并不是那些标准代码而是被大多数人忽略的测试数据。这套资源把一场比赛从题面、标程到裁判用的输入输出数据完整打包适合备战 ACM、算法竞赛的选手做赛后复盘也适合用来把典型题固化成专题训练。只要手上有 C 编译器和一点命令行耐心你就能把整套标程在本地全部重跑还能顺手改造成自己的训练工具。2. 资源全景先按题号和数据目录看懂这套包多校赛的标程包通常不是一份读完就完事的文档而是按“一题一目录”的方式组织。想在本地复现每一道题第一步不是打开代码而是先把目录结构摸清楚否则后面写批量脚本时连路径都容易写错。2.1 根目录的划分方式解压之后根目录把每一道题单独放在一个子目录里子目录名一般就是 OJ 上的题号比如 1001、1002 这类编号。数据配套也沿用这套命名每组输入输出文件的编号和题号没有直接关系只表示这是该题的第几组数据。下面是我解压后看到的典型结构2017-multi-school-first/ ├── 1001/ │ ├── problem.pdf │ ├── solution.cpp │ ├── data/ │ │ ├── 1.in │ │ ├── 1.out │ │ ├── 2.in │ │ └── 2.out ├── 1002/ │ ├── problem.pdf │ ├── solution.java │ ├── data/ │ │ ├── 01.in │ │ ├── 01.out │ │ └── ... └── 1003/ ├── problem.pdf ├── solution.cpp ├── gen.cpp └── data/problem.pdf是原始题面solution.cpp或solution.java是官方标程data目录下按编号放多组输入输出。有些题的data目录旁还会带gen.cpp生成器这种题通常数据范围很大出题人需要用生成器临时造超过官方数据量的随机输入来压复杂度。这套结构的最大价值在于你不需要去 OJ 上一组一组提交就能在本地看到题面和答案的对应关系。我每次拿到新包会先把所有data目录复制到独立目录下和标程可执行文件分层摆放后续脚本只用相对路径省去一堆cd烦恼。2.2 标程语言与编译选项第一场多校赛的标程以 C 为主少量 Java基本看不到 Python。不是 Python 不能写而是竞赛评测环境下 C 的常数和内存表现更稳定。文件命名规律很直接solution.cpp对应 Csolution.java对应 Java。如果看到checker.cpp那是特判题专用的校验器不是正式答案。编译时主要用 G 的 C11 或 C14 标准加上-O2优化。常见做法是一行命令g -O2 -stdc14 solution.cpp -o solution-O2是多数 OJ 的默认优化等级会触发循环展开、函数内联等优化执行效率接近评测机。-stdc14是保证代码里的 auto、lambda、移动语义等语法不会被旧标准卡住。Java 标程按 OJ 惯例用 Java 8 编译本地 JDK 版本新一些也基本兼容但偶尔要处理模块化带来的类路径问题。标程本身不读文件统一从标准输入读往标准输出写评测系统通过重定向把它当黑匣子测。所以本地手动跑不需要改代码只需用重定向./solution data/1.in result.out这也是批量对拍能跑起来的前提。2.3 测试数据与标准答案的关系data目录里的.in和.out文件一一对应。普通题评测器会把你的输出和.out做文本比较规则一般是忽略行尾空格和最后是否多一个换行但行中间的空格不能多也不能少。特判题输出不唯一评测时会运行checker校验合法性。判断是否特判最直接的方法就是看目录里有没有checker.cpp或spj.cpp有就是特判没有就按严格比较处理。另外有一点容易踩.in文件名编号不代表数据规模。有些题1.in是最小样例有些题反而1.in就是极限数据命名顺序完全看造数据习惯。我见过10.in是极端数据、11.in是随机小数据的情况只按文件名推断规模会看错重点。所以完整跑完以后我会用wc -c看每个.in的字节数把最大的一组单独拎出来做压力测试。这个习惯能帮你快速避开“只跑了弱数据”的错觉。3. 核心模块拆解一道题从标准输入到答案输出的完整链路多校赛标程读起来不费劲因为绝大多数代码就是标准的三段式读入、处理、输出。我拆解时挑三个典型场景签到题、数据结构题和需要优化剪枝的搜索题基本能覆盖这套包里的常见题型。3.1 签到题多组测试数据下的读入与输出控制第一场的签到题经常是让处理 T 组数据每组算一个结果。这类标程会严格按题面说的“先给 T再给 T 组数据”来写不会把所有输入读完再一次输出而是每读一组就立刻输出。看一段简化后的标程#include cstdio int main() { int T; scanf(%d, T); // 先读测试组数 while (T--) { long long n, m; scanf(%lld%lld, n, m); long long ans n ^ m; // 按题意计算的表达式 printf(%lld\n, ans); } return 0; }scanf(%d, T)里的%d对应 int 类型T--作为循环条件会先判断再自减所以循环次数正好是 T 次。这里最值得留意的是%lld题目取值范围一旦超过 1e9long long和%lld缺一不可否则本地碰巧跑对交上去就翻车。这段代码还体现了一个工程习惯标程不写freopen不写文件 IO输入输出全走标准流。本地用重定向喂数据提交到 OJ 由评测端注入代码结构和比赛时保持一致能少踩一个“本地能跑、OJ 读不到文件”的坑。3.2 数据结构题线段树标程的 build 与 query 实现第一场基本必有一道用线段树或树状数组解决的题。标程通常用全局数组写法因为常数小、好调试。下面是一个典型的区间最大值线段树片段包含建树和查询const int MAXN 200005; int a[MAXN], tree[MAXN 2]; void build(int node, int l, int r) { if (l r) { tree[node] a[l]; return; } int mid (l r) 1; build(node 1, l, mid); build(node 1 | 1, mid 1, r); tree[node] tree[node 1] tree[node 1 | 1] ? tree[node 1] : tree[node 1 | 1]; } int query(int node, int l, int r, int ql, int qr) { if (ql l r qr) return tree[node]; int mid (l r) 1, res -1; if (ql mid) res query(node 1, l, mid, ql, qr); if (qr mid) { int right query(node 1 | 1, mid 1, r, ql, qr); if (right res) res right; } return res; }MAXN是数据范围上限tree开成MAXN 2是线段树的固定做法因为最坏情况下节点数接近 4 倍区间长度。node 1表示左孩子node 1 | 1表示右孩子比手写node * 2 1更直观。build先把区间切到单点回溯时合并左右儿子query分三种情况完全覆盖直接返回完全不相交会被递归条件自然过滤部分覆盖则合并左右子树的查询结果。这类标程的主函数里通常用while循环处理多组测试数据每组都重新build一次。二次开发时可以把全局数组改成结构体版本代码更好读但常数会略大。3.3 难题标程搜索剪枝与状态压缩压轴题经常出现“看似暴力、实际靠剪枝”的搜索题标程不会真去枚举所有状态而是用位运算压缩状态再配合记忆化或可行性剪枝。我拆过的某个标程里有这样一段关键函数int dfs(int mask, int last, int cost) { if (mask all) return cost; if (dp[mask][last] ! -1) return dp[mask][last] cost; int best INF; for (int i 0; i n; i) { if (mask (1 i)) continue; int nextCost cost dist[last][i]; if (nextCost lowBound[i] best) continue; best std::min(best, dfs(mask | (1 i), i, nextCost)); } return dp[mask][last] best - cost; }mask用一个整数表示哪些点已经访问过1 i是第 i 个点的标记mask (1 i)判断点是否已在集合中。dp[mask][last]存从当前状态到终点还需要的最小代价所以返回值里把已花费的cost单独剥出来避免同一个状态被重复计算。lowBound[i]是提前算好的下界用来在递归前判断“即使后面全走最优也不可能更短”这是大数据能不能跑完的关键。这类代码是标程里最难过到别的题上的部分因为剪枝条件高度依赖题目本身。想把它改造成自己的搜索模板重点不是抄递归框架而是理解lowBound怎么算、为什么剪掉某个分支后答案不会变。4. 把标程跑起来本地编译、批量对拍与常见报错处理标程不是用来看的是要在本地全部跑通的。这一章给一套我常用的流程先编译再批量对拍最后定位失败原因整个过程不依赖任何图形界面。4.1 环境准备与编译命令先确认本地有 G终端里执行g --version能输出版本号就说明可用。把每个题号目录的标程陆续编译我习惯把所有可执行文件输出到同一个bin/目录避免源码目录被一堆二进制文件弄脏mkdir -p bin g -O2 -stdc14 1001/solution.cpp -o bin/1001 g -O2 -stdc14 1002/solution.cpp -o bin/1002-o bin/1001表示把编译产物放到 bin 目录下文件名和题号保持一致方便后续脚本循环调用。如果编译报错先看是否缺头文件再看是否用了gets这类被废弃的函数多数标程在正常 GCC 下都能一次过。Java 标程需要先把.java编译成.class再用java命令运行。注意编译和运行要保持在同一个类路径下否则找不到入口主类javac -encoding UTF-8 1002/solution.java java -cp 1002 solution-cp 1002指定类路径根目录solution是主类名。如果出现找不到主类的错误去源文件里找public class后面的名字不要想当然用文件名。4.2 用批处理脚本批量跑完全部数据手动一组一组跑非常消耗耐心尤其是一道题可能有三四十组数据。写一个 bash 脚本遍历题号和data目录逐组运行并对比结果是竞速训练的基本功。下面这个脚本会遍历指定题号把每个.in对应的输出和标准答案比较#!/bin/bash for id in 1001 1002 1003; do for in_file in ${id}/data/*.in; do out_file${in_file%.in}.out ./bin/${id} ${in_file} /tmp/result.txt if diff -w -B /tmp/result.txt ${out_file} /dev/null; then echo ${in_file} OK else echo ${in_file} WA fi done done${in_file%.in}是把文件后缀.in裁掉得到对应的.out文件名 ${in_file}做输入重定向 /tmp/result.txt把程序输出写到临时文件。diff -w -B里的-w忽略行尾空格差异-B忽略空行差异模拟 OJ 的宽松比较。如果你想知道严格模式下会不会挂把两个参数去掉再跑一遍即可。提示如果脚本跑到一半卡住先单独执行一遍某组数据的重定向命令确认程序本身能正常结束再回来看脚本。八成问题出在没有固定随机种子或者读入死循环。遇到数据量大的题建议在执行行前加timeout防止死循环拖死整个脚本。把./bin/${id}换成timeout 5 ./bin/${id}超过 5 秒返回非零状态码脚本继续往下走不会停在原地。4.3 对照评测结果排查超时和 WA批量对拍之后常见失败有三种。第一种是输出里混进了调试信息标程里没删干净的printf会让你和.out一比对就出现巨大差异。第二种是程序在某一组数据上长时间不结束多半是搜索题没剪枝或递归爆栈先用timeout单独跑那组数据确认。第三种是多次运行结果不稳定通常是用了随机数而没固定种子或者读到了未初始化变量。我最常用的定位命令是单独跑失败组把输出和标准输出放到两侧逐行对比./bin/1001 1001/data/5.in /tmp/my.out diff -y /tmp/my.out 1001/data/5.outdiff -y分两栏显示差异左边是当前输出右边是标准输出哪一行不一样一眼就能看出来。对比完先判断是格式问题还是算法问题格式问题回到空白处理算法问题就把出错的那一行输入单独提取出来做小规模复现。5. 避坑指南多校赛复现路上最容易翻车的五个踩坑现场标程本身是准的但本地复现过程中最常见的意外几乎都出在运行方式和数据理解上。下面五条是我自己踩过、也看身边人踩过的坑每条按“现象、原因、解决”三层拆开。5.1 本地输出完全正确交到 OJ 却直接崩溃现象在本地 IDE 里跑输出和标准答案一模一样粘贴到 OJ 提交后返回运行时错误或没有任何输出。原因代码里残留了freopen(data.in, r, stdin)这类文件重定向。本地有这个文件所以一切正常OJ 评测环境没有这个文件程序在打开文件那一步直接异常退出。解决把输入输出全部改成标准流本地用重定向来喂数据。提交前在源码里全程搜索freopen和fopen看到就删。我一般会用grep -rn freopen 1001/solution.cpp扫一遍比肉眼快得多。5.2 多组数据循环边界没控制好现象第一组数据跑得对从第二组开始输出错位或者程序无法结束。原因把“先读 T再读 T 组”写成了while (scanf(...))外层套for内层的双层结构。一旦输入文件里有多余空白或注释内容内层循环就会多读一组残缺输入导致后续全部错位。解决严格按题面格式来题目给 T 就只读 T 次读完直接退出。题目没说 T、以文件结束符结尾时才用while (scanf(...) ! EOF)写法。这两种模式特别容易混建议在代码注释里写明“这里读 T”还是“这里读到 EOF”。5.3 64 位整数输出格式写错现象小数据没有异常数据稍微变大结果突然变成负数或乱码。原因long long的格式化符应当是%lld但有些本地环境会习惯性写成%I64d或者干脆用int接收结果。多校赛数据很喜欢卡 2^31 边界一个int溢出就直接错了。解决统一使用%lld和long long不要在算术表达式里混用int和long long。需要位移或强制类型转换时写成1LL n或(long long)value保证运算过程被提升到 64 位。排查这类问题时优先检查所有scanf和printf的格式化符。5.4 本地看起来一样OJ 却判 WA现象文本编辑器里对比我的输出和.out肉眼看不出区别提交却返回错误答案。原因编辑器自动修剪行尾空格或者自动补了换行和 OJ 的比较规则不一致。OJ 一般忽略行尾空格和文件末尾换行但不会忽略行中间多余的空格两边的判断基准不一样。解决本地比较用命令行工具严格模式用diff宽松模式用diff -w -B。先跑宽松模式如果宽松模式都是 WA那就不是空白问题回去查算法本身。5.5 本地测时 1 秒提交却超时现象本地用clock()测出来运行只要 1 秒提交到 OJ 却显示超时。原因clock()统计的是 CPU 时间在本地 IDE 或调试器里运行可能没开优化或者本地只跑了小规模样例没有覆盖真正的大数据组。解决测时用time ./solution data/big.in看墙钟时间或者直接拿数据目录里体积最大的那一组测试。多校赛的数据经常有接近 10MB 级别的大文件本地跑一遍最大数据的实际耗时才接近 OJ 上的表现。这五个坑里前三个和代码写法强相关后两个和数据理解强相关。把这几条刻进习惯里再回头看标程会顺眼很多。6. 二次开发思路把一套标程改造成可复用的日常训练工具跑通只是第一步。我做完这套资源的第一遍验证后最有效的一次投入是把静态目录改造成了日常可用的训练环境。先做一个带超时检测的自动评测脚本。第四章的 bash 脚本可以升级成支持每道题独立时限、自动统计用时的版本。做法是为每道题准备一个limit变量用date命令记录运行前后的毫秒时间戳for id in 1001 1002 1003; do start$(date %s%N) timeout ${limit[$id]} ./bin/${id} ${in_file} /tmp/result.txt status$? end$(date %s%N) elapsed$(( (end - start) / 1000000 )) if [ ${status} -eq 124 ]; then echo ${in_file} TLE fi donedate %s%N拿到纳秒级时间戳status$?取上一条命令的退出码timeout返回 124 表示超时。每次训练后能直接得到一个“哪题快、哪题慢”的列表比手动按秒表可靠得多。再把目录按知识点重排。原始目录按题号排列不适合按专题复习。我建一个topics.csv每行记录“题号、知识点、难度、状态”再用脚本把原始数据软链到problems/数据结构/线段树/1002这类目录下。多校赛的题覆盖数论、图论、字符串、计算几何等方向按专题分类后想练哪个模块就从对应文件夹拉数据。最后用生成器扩展边界测试。部分题自带gen.cpp编译后能生成远大于官方数据的随机输入。比如原题 N 最大 1e5生成器可以跑到 2e5这时就能验证标程是不是真的留了余量。没有生成器的题按题面数据范围手写一个小生成器专门制造最大值、最小值和全部相等三类极端数据放进data/extra/然后复用自动评测脚本跑一遍。从那以后我每次拿到新的标程资源都会强制走一遍“先看目录、再批量对拍、最后补一组极端数据”的流程而不是急着翻答案。别小看这三步它帮我少走了很多对着 OJ 猜谜的弯路。希望帮到你。本文还有配套的精品资源点击获取
阅读完成 · 觉得有帮助？
