拓冰网站定制 
简介这份资源是哈工大2023春季高级算法课程实验的配套学习包面向选课学生及算法自学者内容按Lab1至Lab5分层组织。从快速排序、二分查找等基础算法逐步深入到Dijkstra、Floyd-Warshall、动态规划、最小生成树与Bellman-Ford等进阶主题每个实验均配有可直接运行的Python源码和Markdown说明书便于理解问题要求、输入输出格式及算法步骤。压缩包共30个文件以23个py文件为主兼有4个txt说明、2个pickle数据及1个md文档整体约18.87MB模块划分明确可按需取用。已有109人学习浏览对完成课程设计、实验作业或系统复习高级算法都很有价值。通过阅读源码、运行调试并尝试修改优化既能巩固理论知识也能借鉴不同实现思路将算法迁移到新场景切实提升算法设计与编程能力。1. 哈工大2023春高级算法课程实验一份能直接跑起来的算法实验全家桶这学期算法课实验的作业被老师点名用这个包当标准模板。先说结论这不是一份照着抄就能过的答案而是一套带说明书、带源码、允许你自己改的算法实验骨架。里面是分治、动规、贪心、KMP、图论、排序对比这些课设必考的算法实现配了输入输出格式说明和报告要求拿到手先在本地把环境跑通再往里面填自己的思路比从零开始写省一多半时间。适合两类人一类是正在选课、被实验报告折磨的学生另一类是自学数据结构与算法、想找现成实现做参照的从业者。但有个前提评测平台认的不是源码是标准输入输出和主类入口这一步踩坑的人最多。下面按环境跑通 → 逐个实验复现 → 排错 → 验收的顺序拆。2. 实验环境速通文件布局、JDK与CLion配置、两种评测模式2.1 解压后先看文件布局别急着改代码拿到 zip 后第一件事不是双击打开源码而是把解压后的目录结构完整看一遍。实验中常见的布局是这样的algorithm-lab/ ├── src/ │ ├── main/java/ # 主实现源码 │ ├── test/java/ # 本地测试用例 ├── docs/ # 说明书、实验要求、评分标准 ├── data/ # 输入样例和输出样例 ├── output/ # 结果输出目录评测时会清空 └── README.md # 使用说明这个布局的意义在于说明书在 docs 里入口函数在 src 里样例数据在 data 里三者必须对得上。我第一次打开这个包时直接奔着源文件去了结果改了半天的类名跑到平台上一提交发现入口类找不到血泪经验。先读 README.md 和 docs 里的实验要求把每个实验的输入输出格式记下来。注意看评分标准里有没有算法复杂度分析这一项有的话报告里要单独写时间复杂度的推导过程这比代码本身占分还重。2.2 JAR 评测与 Native 评测两条完全不同的跑法这个包最核心的设计是支持两种评测模式说明书里通常叫JAR 模式和Native 模式。JAR 模式把整个工程编译打包成可执行 jar评测平台执行java -jar yourlab.jar input.txt output.txt。要求主类有main方法从标准输入读向标准输出写不允许写死文件名。Native 模式C/C 实现编译成可执行文件平台直接调用同样走标准输入输出。两种模式的区别在资源限制上——JAR 模式比 Native 模式多一个 JVM 启动开销所以评测时 JAR 模式的时限通常会放宽一点比如同一个实验 Native 给 1 秒JAR 给 3 秒。本地验证时我一般两个模式都测一遍尤其注意 JAR 模式下不要用Scanner读大数据量BufferedReader才是安全的选择。2.3 本机把环境跑通的三个步骤第一步确认 JDK 版本。这个包按 JDK 11 写的用 JDK 8 运行部分实验会报UnsupportedOperationException用 JDK 17 反而没问题但说明书里的 Maven 配置是按 11 来的。命令行先验证java -version javac -version mvn -version如果mvn没装直接用 IDEA 或 CLion 打开工程IDE 自带的编译器也能完成打包只是命令行脚本跑不了。第二步跑通样例数据。把data/下的每个输入文件对应跑一遍用 diff 和标准输出对比javac -encoding UTF-8 -d out src/main/java/*.java java -cp out Main data/exp1.in output/exp1.out diff output/exp1.out data/exp1.expecteddiff输出为空说明本地结果正确。这里的-encoding UTF-8不能省Windows 下不指定编码会乱码后面避坑章会细说。第三步改一个参数验证可自己修改的边界。这个包的说明书写明了哪些类可以动哪些不能动——入口类名、输入输出格式、包路径这三样不能改改了评测平台就找不到类。可以动的是算法实现部分比如把实验三的贪心策略换成剪枝策略只要输入输出不变平台不关心你内部怎么实现。2.4 两种模式下的参数选型表参数项JAR 模式Native 模式入口主类Mainpublic static void main(String[])main函数编译成可执行文件输入System.in逐行读stdin输出System.out.println每行一个结果printf或cout时限相对宽松受 JVM 启动影响严格按编译后运行时间计内存受-Xmx限制默认 256M受系统限制约 512M调试残留提交前必须去掉printStackTrace()提交前必须去掉cerr调试输出提示输出末尾有没有多余空行不影响评测但每行内不能有多余空格平台是按行 trim 后比较的。如果本地 diff 通过但平台报错先检查有没有打印调试信息。3. 六个核心实验的解题思路与可抄作业模板3.1 分治与归并从大整数乘法到逆序对计数这个包里的实验一通常是大整数乘法或逆序对计数本质都是分治。归并排序是这一实验最通用的骨架逆序对计数就是在归并的过程中统计左半和右半之间的逆序关系。先看这段能直接用的归并排序模板public class MergeSort { private int[] tmp; public long sort(int[] nums) { tmp new int[nums.length]; return mergeSort(nums, 0, nums.length - 1); } private long mergeSort(int[] nums, int left, int right) { if (left right) return 0; int mid (left right) 1; long count mergeSort(nums, left, mid) mergeSort(nums, mid 1, right); int i left, j mid 1, k left; while (i mid j right) { if (nums[i] nums[j]) { tmp[k] nums[i]; } else { tmp[k] nums[j]; count mid - i 1; // 逆序对计数核心 } } while (i mid) tmp[k] nums[i]; while (j right) tmp[k] nums[j]; System.arraycopy(tmp, left, nums, left, right - left 1); return count; } }逻辑说明mergeSort返回逆序对总数count mid - i 1这行是灵魂——当右半的nums[j]小于左半的nums[i]时左半从i到mid的所有元素都大于nums[j]这些全算逆序对。如果不需要逆序对把count相关行删掉即可。参数说明tmp数组复用避免每层递归都 new否则大数据量会频繁触发 GC。3.2 动态规划与贪心0-1 背包和活动选择的模板化写法实验二要么是 LCS 要么是 0-1 背包。0-1 背包用一维滚动数组是必须掌握的写法这个包里的模板也是这么给的public class Knapsack { public static int solve(int capacity, int[] weights, int[] values) { int[] dp new int[capacity 1]; for (int i 0; i weights.length; i) { for (int c capacity; c weights[i]; c--) { dp[c] Math.max(dp[c], dp[c - weights[i]] values[i]); // 注意 c 必须倒序遍历否则同一个物品会被拿两次 } } return dp[capacity]; } }参数说明capacity是背包容量weights和values的索引一一对应。dp[c]的含义是容量为c时能装的最大价值。内层循环倒序是 0-1 背包区别于完全背包的关键改成正序就变成了完全背包。做实验时先在本地把这两种情况跑一遍报告里对比输出差异比干写推导过程有说服力得多。贪心实验里最典型的是活动选择问题模板逻辑一句话按结束时间排序能接就接。这个包的说明书里要求证明贪心策略的正确性报告里写每次选结束时间最早的活动为后面的活动留出最大剩余时间这条就够了。3.3 KMP 字符串匹配与堆优化 Dijkstra两个高频压轴实验KMP 是必考实验next 数组的构造是最容易写错的。这个包给的是前缀函数版本写法更不容易翻车public class KMP { public static int[] buildPrefix(String pattern) { int m pattern.length(); int[] pi new int[m]; for (int i 1; i m; i) { int j pi[i - 1]; while (j 0 pattern.charAt(i) ! pattern.charAt(j)) { j pi[j - 1]; } if (pattern.charAt(i) pattern.charAt(j)) { j; } pi[i] j; } return pi; } public static int search(String text, String pattern) { int[] pi buildPrefix(pattern); int j 0; for (int i 0; i text.length(); i) { while (j 0 text.charAt(i) ! pattern.charAt(j)) { j pi[j - 1]; } if (text.charAt(i) pattern.charAt(j)) { j; } if (j pattern.length()) { return i - pattern.length() 1; } } return -1; } }逻辑说明buildPrefix求的是pattern每个前缀的最长相等前后缀长度search里失配时通过pi[j - 1]回退不回退已经匹配的字符。参数说明pi[0]恒为 0第一个字符没有真前缀。这个版本比next 数组整体右移一位的写法直观但注意两者在失配回退时下标差一位混用会 bug。图论实验如果涉及单源最短路堆优化 Dijkstra 是效率最稳的选择。核心是把维护距离最小值的操作交给优先队列复杂度从O(V^2)降到O(E log V)。这个实验很多人翻车在负权边——Dijkstra 对负权边不成立题目里没说无负权边时用 SPFA 或 Bellman-Ford 兜底。说明书里会点名这部分读题时要特别标注。3.4 排序算法全对比冒泡、快排、堆排、归并的复杂度验证实验六一般是排序算法对比要求对同一组数据分别跑冒泡、快排、堆排、归并比较时间。这个包的源码里给了完整的计时框架但有几个点必须自己改数据规模到10^5级冒泡排序基本就跑不动了压测时要分梯度做比如5*10^3、10^4、2*10^4三档。快排必须处理重复元素的情况不优化的话全相同数组上退化成O(n^2)时间直接爆掉。三路快排也就是把数组分成小于、等于、大于三个区间的做法是应对重复数据的最简单方案归并排序稳定但需要O(n)额外空间堆排序不稳定但空间O(1)。报告里把这四列的稳定性、空间复杂度、时间实测数据做成表能拿到的分比单纯贴代码高很多。4. 避坑从TLE、乱码到评测黑匣子七个高频翻车点4.1 现象本地秒出结果平台报 TLE原因本地数据规模小平台的数据是满规模的。比如归并排序的实验本地测了 1000 个元素没问题平台上可能是10^6个。这时候问题往往不在算法本身而在输入输出写法——Scanner逐行读10^6个整数时间全花在解析上了。解决换BufferedReader手动解析或者写一个快速读入器。Java 实验里这一步的差距能到 5 倍以上我一般直接改为BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine()); int n Integer.parseInt(st.nextToken());4.2 现象改了一个类的包名平台直接说找不到主类原因入口类的包路径是评测脚本写死的平台执行的命令是java -cp out Main如果你的Main类在org.example包下得写成java -cp out org.example.Main。解决所有主入口类放在默认包下不加package声明。这是这个实验包里最容易忽略的一条规定说明书里没用加粗标出来但在 README 最下方写了我第二次跑平台评测才发现。4.3 现象Windows 下编译通过输出却全是乱码原因源码文件是 UTF-8 编码Windows 命令行默认用 GBK 编译javac没指定-encoding UTF-8时中文字符串常量直接变乱码。解决统一指定编码IDEA 里在 Settings 中把 Project Encoding、Global Encoding、Properties Files 全改成 UTF-8命令行编译时javac -encoding UTF-8写在第一个。Native 模式同理g 编译时加-finput-charsetUTF-8 -fexec-charsetUTF-8。4.4 现象跟同学对答案结果一模一样平台上分数却差一截原因评测分不止看结果正确还看运行时间排名和内存占用。同样的算法有人用ArrayListint[]存图有人用链式前向星10^5条边的图测试下内存差 30MB 是完全可能的。解决提交前看data/里最大样例的规模按那个规模去估内存。Java 的默认堆内存是物理内存的 1/4平台限制 256M 时大数组直接 OOM此时需要显式压缩存储比如用int[]代替Integer装箱数组。4.5 现象实验报告里的复杂度分析和代码实际行为对不上原因比如代码里用了String 拼接循环报告里却写O(n)实际上 Java 的字符串拼接在循环里是O(n^2)。平台不查报告但助教查。解决交报告前自己先按代码走一遍复杂度推导尤其注意隐藏的循环——StringBuilder的append是均摊O(1)String的是每次创建新对象。把报告里的复杂度结论和代码逐行对齐宁可写保守的O(n log n)也不要吹成O(n)。4.6 现象平台能跑但输出格式跟样例差了最后一行换行原因多数评测系统对行尾换行无所谓但个别题目的校验器是逐字符比对。解决输出完所有结果后加一个System.out.println()或者用PrintWriter输出最后统一flush()。不确定时看样例文件末尾有没有空行用cat -A data/exp1.expected看一眼行尾符。如果是 Windows 平台的 CRLF 和 Linux 平台的 LF 混用最终文件会显示^M用dos2unix转一下再交。4.7 现象代码里加了一行 print 调试信息忘记删原因评测时标准输出只比对结果多出来的调试行会导致 diff 失败。解决提交前全局搜索System.out.println逐个确认是否是算法输出。这一条看起来弱智但每次实验提交都有人翻车我自己的习惯是写一个debug开关变量调试时置true提交前置false比逐个删注释更不容易漏。注意这个实验包最大的坑不在算法实现而在你以为跟平台一样的假设。任何改动改完先在本地重新跑一遍样例再用第四节的验收脚本做一次最终确认。5. 验收习惯从造数据、对拍到提交前检查清单前面把环境和代码都跑通了最后一步是建立一个不会坑到自己的验收流程。我的做法是三步造随机数据、写对拍脚本、走提交检查清单。第一步造随机数据。data/里的样例规模太小必须自己造大数据压测。用 Python 写一个随机数据生成器按每个实验的输入格式输出import random n 100000 with open(stress.in, w) as f: f.write(str(n) \n) f.write( .join(str(random.randint(1, 100000)) for _ in range(n)) \n)跑完后把它扔给两个实现——你自己写的版本和实验包里给的参考实现——对比输出是否一致。对拍脚本用 bash 写每次改完代码自动跑一遍javac -encoding UTF-8 -d out src/main/java/*.java java -cp out MySolution stress.in my.out java -cp out Reference stress.in ref.out diff my.out ref.out echo PASS || echo FAILdiff出现PASS说明这次改动没破坏已有功能FAIL就回去查。注意stress.in要至少跑三组不同规模的数据小规模验证逻辑大规模验证性能和内存。第二步提交前检查清单按这个顺序走压缩包内不能包含output/目录下的生成结果这些是运行时产物交上去只会增大包体工程里不能有.class文件IDEA 编译时会自动生成out/目录压缩前先删掉入口类是否在默认包下是否还有调试输出没关说明书里要求的文件命名是否一致一般是学号-姓名-lab.zip用zip -d把不需要的文件从压缩包中剔除而不是重新解压再压缩后者容易引入权限问题。第三步提交前先自己在命令行完整跑一遍从编译到评测的模拟流程不要依赖 IDE 的运行按钮。IDE 会自动加上 classpath、自动编译所有依赖这些在评测环境下都不存在。命令行跑通了平台才大概率能跑。从那以后我每次做完实验都强制走一遍造数据 → 对拍 → 清单检查三连哪怕只是改了一行排序的比较逻辑也会用三组数据重新打一遍。这个习惯帮我筛掉了至少三次因为粗心导致的提交失败也让我确认了一个事实实验包的正确答案其实是次要的真正值钱的是建立一套可信的本地验证环境让每一次提交都不心虚。希望这份拆解能帮你少踩几个坑把时间花在算法本身而不是环境折腾上。本文还有配套的精品资源点击获取 哈工大高级算法课程实验指南：环境配置、模板与避坑全解析
简介这份资源是哈工大2023春季高级算法课程实验的配套学习包面向选课学生及算法自学者内容按Lab1至Lab5分层组织。从快速排序、二分查找等基础算法逐步深入到Dijkstra、Floyd-Warshall、动态规划、最小生成树与Bellman-Ford等进阶主题每个实验均配有可直接运行的Python源码和Markdown说明书便于理解问题要求、输入输出格式及算法步骤。压缩包共30个文件以23个py文件为主兼有4个txt说明、2个pickle数据及1个md文档整体约18.87MB模块划分明确可按需取用。已有109人学习浏览对完成课程设计、实验作业或系统复习高级算法都很有价值。通过阅读源码、运行调试并尝试修改优化既能巩固理论知识也能借鉴不同实现思路将算法迁移到新场景切实提升算法设计与编程能力。1. 哈工大2023春高级算法课程实验一份能直接跑起来的算法实验全家桶这学期算法课实验的作业被老师点名用这个包当标准模板。先说结论这不是一份照着抄就能过的答案而是一套带说明书、带源码、允许你自己改的算法实验骨架。里面是分治、动规、贪心、KMP、图论、排序对比这些课设必考的算法实现配了输入输出格式说明和报告要求拿到手先在本地把环境跑通再往里面填自己的思路比从零开始写省一多半时间。适合两类人一类是正在选课、被实验报告折磨的学生另一类是自学数据结构与算法、想找现成实现做参照的从业者。但有个前提评测平台认的不是源码是标准输入输出和主类入口这一步踩坑的人最多。下面按环境跑通 → 逐个实验复现 → 排错 → 验收的顺序拆。2. 实验环境速通文件布局、JDK与CLion配置、两种评测模式2.1 解压后先看文件布局别急着改代码拿到 zip 后第一件事不是双击打开源码而是把解压后的目录结构完整看一遍。实验中常见的布局是这样的algorithm-lab/ ├── src/ │ ├── main/java/ # 主实现源码 │ ├── test/java/ # 本地测试用例 ├── docs/ # 说明书、实验要求、评分标准 ├── data/ # 输入样例和输出样例 ├── output/ # 结果输出目录评测时会清空 └── README.md # 使用说明这个布局的意义在于说明书在 docs 里入口函数在 src 里样例数据在 data 里三者必须对得上。我第一次打开这个包时直接奔着源文件去了结果改了半天的类名跑到平台上一提交发现入口类找不到血泪经验。先读 README.md 和 docs 里的实验要求把每个实验的输入输出格式记下来。注意看评分标准里有没有算法复杂度分析这一项有的话报告里要单独写时间复杂度的推导过程这比代码本身占分还重。2.2 JAR 评测与 Native 评测两条完全不同的跑法这个包最核心的设计是支持两种评测模式说明书里通常叫JAR 模式和Native 模式。JAR 模式把整个工程编译打包成可执行 jar评测平台执行java -jar yourlab.jar input.txt output.txt。要求主类有main方法从标准输入读向标准输出写不允许写死文件名。Native 模式C/C 实现编译成可执行文件平台直接调用同样走标准输入输出。两种模式的区别在资源限制上——JAR 模式比 Native 模式多一个 JVM 启动开销所以评测时 JAR 模式的时限通常会放宽一点比如同一个实验 Native 给 1 秒JAR 给 3 秒。本地验证时我一般两个模式都测一遍尤其注意 JAR 模式下不要用Scanner读大数据量BufferedReader才是安全的选择。2.3 本机把环境跑通的三个步骤第一步确认 JDK 版本。这个包按 JDK 11 写的用 JDK 8 运行部分实验会报UnsupportedOperationException用 JDK 17 反而没问题但说明书里的 Maven 配置是按 11 来的。命令行先验证java -version javac -version mvn -version如果mvn没装直接用 IDEA 或 CLion 打开工程IDE 自带的编译器也能完成打包只是命令行脚本跑不了。第二步跑通样例数据。把data/下的每个输入文件对应跑一遍用 diff 和标准输出对比javac -encoding UTF-8 -d out src/main/java/*.java java -cp out Main data/exp1.in output/exp1.out diff output/exp1.out data/exp1.expecteddiff输出为空说明本地结果正确。这里的-encoding UTF-8不能省Windows 下不指定编码会乱码后面避坑章会细说。第三步改一个参数验证可自己修改的边界。这个包的说明书写明了哪些类可以动哪些不能动——入口类名、输入输出格式、包路径这三样不能改改了评测平台就找不到类。可以动的是算法实现部分比如把实验三的贪心策略换成剪枝策略只要输入输出不变平台不关心你内部怎么实现。2.4 两种模式下的参数选型表参数项JAR 模式Native 模式入口主类Mainpublic static void main(String[])main函数编译成可执行文件输入System.in逐行读stdin输出System.out.println每行一个结果printf或cout时限相对宽松受 JVM 启动影响严格按编译后运行时间计内存受-Xmx限制默认 256M受系统限制约 512M调试残留提交前必须去掉printStackTrace()提交前必须去掉cerr调试输出提示输出末尾有没有多余空行不影响评测但每行内不能有多余空格平台是按行 trim 后比较的。如果本地 diff 通过但平台报错先检查有没有打印调试信息。3. 六个核心实验的解题思路与可抄作业模板3.1 分治与归并从大整数乘法到逆序对计数这个包里的实验一通常是大整数乘法或逆序对计数本质都是分治。归并排序是这一实验最通用的骨架逆序对计数就是在归并的过程中统计左半和右半之间的逆序关系。先看这段能直接用的归并排序模板public class MergeSort { private int[] tmp; public long sort(int[] nums) { tmp new int[nums.length]; return mergeSort(nums, 0, nums.length - 1); } private long mergeSort(int[] nums, int left, int right) { if (left right) return 0; int mid (left right) 1; long count mergeSort(nums, left, mid) mergeSort(nums, mid 1, right); int i left, j mid 1, k left; while (i mid j right) { if (nums[i] nums[j]) { tmp[k] nums[i]; } else { tmp[k] nums[j]; count mid - i 1; // 逆序对计数核心 } } while (i mid) tmp[k] nums[i]; while (j right) tmp[k] nums[j]; System.arraycopy(tmp, left, nums, left, right - left 1); return count; } }逻辑说明mergeSort返回逆序对总数count mid - i 1这行是灵魂——当右半的nums[j]小于左半的nums[i]时左半从i到mid的所有元素都大于nums[j]这些全算逆序对。如果不需要逆序对把count相关行删掉即可。参数说明tmp数组复用避免每层递归都 new否则大数据量会频繁触发 GC。3.2 动态规划与贪心0-1 背包和活动选择的模板化写法实验二要么是 LCS 要么是 0-1 背包。0-1 背包用一维滚动数组是必须掌握的写法这个包里的模板也是这么给的public class Knapsack { public static int solve(int capacity, int[] weights, int[] values) { int[] dp new int[capacity 1]; for (int i 0; i weights.length; i) { for (int c capacity; c weights[i]; c--) { dp[c] Math.max(dp[c], dp[c - weights[i]] values[i]); // 注意 c 必须倒序遍历否则同一个物品会被拿两次 } } return dp[capacity]; } }参数说明capacity是背包容量weights和values的索引一一对应。dp[c]的含义是容量为c时能装的最大价值。内层循环倒序是 0-1 背包区别于完全背包的关键改成正序就变成了完全背包。做实验时先在本地把这两种情况跑一遍报告里对比输出差异比干写推导过程有说服力得多。贪心实验里最典型的是活动选择问题模板逻辑一句话按结束时间排序能接就接。这个包的说明书里要求证明贪心策略的正确性报告里写每次选结束时间最早的活动为后面的活动留出最大剩余时间这条就够了。3.3 KMP 字符串匹配与堆优化 Dijkstra两个高频压轴实验KMP 是必考实验next 数组的构造是最容易写错的。这个包给的是前缀函数版本写法更不容易翻车public class KMP { public static int[] buildPrefix(String pattern) { int m pattern.length(); int[] pi new int[m]; for (int i 1; i m; i) { int j pi[i - 1]; while (j 0 pattern.charAt(i) ! pattern.charAt(j)) { j pi[j - 1]; } if (pattern.charAt(i) pattern.charAt(j)) { j; } pi[i] j; } return pi; } public static int search(String text, String pattern) { int[] pi buildPrefix(pattern); int j 0; for (int i 0; i text.length(); i) { while (j 0 text.charAt(i) ! pattern.charAt(j)) { j pi[j - 1]; } if (text.charAt(i) pattern.charAt(j)) { j; } if (j pattern.length()) { return i - pattern.length() 1; } } return -1; } }逻辑说明buildPrefix求的是pattern每个前缀的最长相等前后缀长度search里失配时通过pi[j - 1]回退不回退已经匹配的字符。参数说明pi[0]恒为 0第一个字符没有真前缀。这个版本比next 数组整体右移一位的写法直观但注意两者在失配回退时下标差一位混用会 bug。图论实验如果涉及单源最短路堆优化 Dijkstra 是效率最稳的选择。核心是把维护距离最小值的操作交给优先队列复杂度从O(V^2)降到O(E log V)。这个实验很多人翻车在负权边——Dijkstra 对负权边不成立题目里没说无负权边时用 SPFA 或 Bellman-Ford 兜底。说明书里会点名这部分读题时要特别标注。3.4 排序算法全对比冒泡、快排、堆排、归并的复杂度验证实验六一般是排序算法对比要求对同一组数据分别跑冒泡、快排、堆排、归并比较时间。这个包的源码里给了完整的计时框架但有几个点必须自己改数据规模到10^5级冒泡排序基本就跑不动了压测时要分梯度做比如5*10^3、10^4、2*10^4三档。快排必须处理重复元素的情况不优化的话全相同数组上退化成O(n^2)时间直接爆掉。三路快排也就是把数组分成小于、等于、大于三个区间的做法是应对重复数据的最简单方案归并排序稳定但需要O(n)额外空间堆排序不稳定但空间O(1)。报告里把这四列的稳定性、空间复杂度、时间实测数据做成表能拿到的分比单纯贴代码高很多。4. 避坑从TLE、乱码到评测黑匣子七个高频翻车点4.1 现象本地秒出结果平台报 TLE原因本地数据规模小平台的数据是满规模的。比如归并排序的实验本地测了 1000 个元素没问题平台上可能是10^6个。这时候问题往往不在算法本身而在输入输出写法——Scanner逐行读10^6个整数时间全花在解析上了。解决换BufferedReader手动解析或者写一个快速读入器。Java 实验里这一步的差距能到 5 倍以上我一般直接改为BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine()); int n Integer.parseInt(st.nextToken());4.2 现象改了一个类的包名平台直接说找不到主类原因入口类的包路径是评测脚本写死的平台执行的命令是java -cp out Main如果你的Main类在org.example包下得写成java -cp out org.example.Main。解决所有主入口类放在默认包下不加package声明。这是这个实验包里最容易忽略的一条规定说明书里没用加粗标出来但在 README 最下方写了我第二次跑平台评测才发现。4.3 现象Windows 下编译通过输出却全是乱码原因源码文件是 UTF-8 编码Windows 命令行默认用 GBK 编译javac没指定-encoding UTF-8时中文字符串常量直接变乱码。解决统一指定编码IDEA 里在 Settings 中把 Project Encoding、Global Encoding、Properties Files 全改成 UTF-8命令行编译时javac -encoding UTF-8写在第一个。Native 模式同理g 编译时加-finput-charsetUTF-8 -fexec-charsetUTF-8。4.4 现象跟同学对答案结果一模一样平台上分数却差一截原因评测分不止看结果正确还看运行时间排名和内存占用。同样的算法有人用ArrayListint[]存图有人用链式前向星10^5条边的图测试下内存差 30MB 是完全可能的。解决提交前看data/里最大样例的规模按那个规模去估内存。Java 的默认堆内存是物理内存的 1/4平台限制 256M 时大数组直接 OOM此时需要显式压缩存储比如用int[]代替Integer装箱数组。4.5 现象实验报告里的复杂度分析和代码实际行为对不上原因比如代码里用了String 拼接循环报告里却写O(n)实际上 Java 的字符串拼接在循环里是O(n^2)。平台不查报告但助教查。解决交报告前自己先按代码走一遍复杂度推导尤其注意隐藏的循环——StringBuilder的append是均摊O(1)String的是每次创建新对象。把报告里的复杂度结论和代码逐行对齐宁可写保守的O(n log n)也不要吹成O(n)。4.6 现象平台能跑但输出格式跟样例差了最后一行换行原因多数评测系统对行尾换行无所谓但个别题目的校验器是逐字符比对。解决输出完所有结果后加一个System.out.println()或者用PrintWriter输出最后统一flush()。不确定时看样例文件末尾有没有空行用cat -A data/exp1.expected看一眼行尾符。如果是 Windows 平台的 CRLF 和 Linux 平台的 LF 混用最终文件会显示^M用dos2unix转一下再交。4.7 现象代码里加了一行 print 调试信息忘记删原因评测时标准输出只比对结果多出来的调试行会导致 diff 失败。解决提交前全局搜索System.out.println逐个确认是否是算法输出。这一条看起来弱智但每次实验提交都有人翻车我自己的习惯是写一个debug开关变量调试时置true提交前置false比逐个删注释更不容易漏。注意这个实验包最大的坑不在算法实现而在你以为跟平台一样的假设。任何改动改完先在本地重新跑一遍样例再用第四节的验收脚本做一次最终确认。5. 验收习惯从造数据、对拍到提交前检查清单前面把环境和代码都跑通了最后一步是建立一个不会坑到自己的验收流程。我的做法是三步造随机数据、写对拍脚本、走提交检查清单。第一步造随机数据。data/里的样例规模太小必须自己造大数据压测。用 Python 写一个随机数据生成器按每个实验的输入格式输出import random n 100000 with open(stress.in, w) as f: f.write(str(n) \n) f.write( .join(str(random.randint(1, 100000)) for _ in range(n)) \n)跑完后把它扔给两个实现——你自己写的版本和实验包里给的参考实现——对比输出是否一致。对拍脚本用 bash 写每次改完代码自动跑一遍javac -encoding UTF-8 -d out src/main/java/*.java java -cp out MySolution stress.in my.out java -cp out Reference stress.in ref.out diff my.out ref.out echo PASS || echo FAILdiff出现PASS说明这次改动没破坏已有功能FAIL就回去查。注意stress.in要至少跑三组不同规模的数据小规模验证逻辑大规模验证性能和内存。第二步提交前检查清单按这个顺序走压缩包内不能包含output/目录下的生成结果这些是运行时产物交上去只会增大包体工程里不能有.class文件IDEA 编译时会自动生成out/目录压缩前先删掉入口类是否在默认包下是否还有调试输出没关说明书里要求的文件命名是否一致一般是学号-姓名-lab.zip用zip -d把不需要的文件从压缩包中剔除而不是重新解压再压缩后者容易引入权限问题。第三步提交前先自己在命令行完整跑一遍从编译到评测的模拟流程不要依赖 IDE 的运行按钮。IDE 会自动加上 classpath、自动编译所有依赖这些在评测环境下都不存在。命令行跑通了平台才大概率能跑。从那以后我每次做完实验都强制走一遍造数据 → 对拍 → 清单检查三连哪怕只是改了一行排序的比较逻辑也会用三组数据重新打一遍。这个习惯帮我筛掉了至少三次因为粗心导致的提交失败也让我确认了一个事实实验包的正确答案其实是次要的真正值钱的是建立一套可信的本地验证环境让每一次提交都不心虚。希望这份拆解能帮你少踩几个坑把时间花在算法本身而不是环境折腾上。本文还有配套的精品资源点击获取