刚把DHU机试题Day1的题目刷完趁着手感还在把整个思考过程整理出来。东华大学DHU的机试风格其实和很多搞竞赛的同学想象的不太一样它不拼那些冷门的图论板子也不考数学构造到天马行空更多是看你能不能把一道基础题写得干净、稳定、考虑周全。第一天上机最重要的不是证明自己会多少高阶算法而是先把“读题—设计—编码—自测—提交”这个完整闭环跑通。Day1的规划如果做得对后面几天会轻松很多。下面这份内容我会按我实际练习的节奏来写包括题目拆解、代码实现、踩坑记录和自检清单。如果你也正在准备DHU机试或者第一次接触上机考试可以参考这套思路不必完全照抄但至少能少走不少弯路。1. 先聊聊DHU机试到底考什么1.1 为什么备考第一天要卡在“能跑通”而不是“会算法”很多同学一听到机试第一反应就是去刷ACM题、啃算法模板结果到了考场上连多组输入的循环写法都卡了二十分钟。机试和算法竞赛的根本区别在于竞赛看谁能把最难的题解出来而机试看谁能把常规题写得最稳。判题系统一般按测试点给分一个点过不去就少一部分分而不是只看最后是否AC。DHU机试的题目分布通常也是从易到难前面几道基本都是模拟、字符串、简单递推真正需要复杂数据结构的题目往往靠后。所以Day1我给自己定的目标不是“每天十道题”而是“每道题都要一次写对”。这个“对”不只是逻辑对还包括变量类型够不够大、多组数据是否处理完整、数组有没有开够、输出格式有没有多余空格。第一天的计划我刻意把自己按在基础题上不去碰难题先把代码手感养起来。就像学做饭一样先把火候和切菜基本功练熟再谈做什么大菜。1.2 机试环境、语言选择与输入输出细节不同学校机试的上机环境差别很大有的用Windows下的Dev-C有的用Linux下的GCC有的允许Python但版本限制较多。DHU往年机试以C/C为主所以我Day1直接选C练习。原因很简单STL里的string、vector、sort、map在解题时能省下大量时间而且C的输入输出模式在OJ上更通用。第一天一定要先把环境确认清楚。比如Visual Studio里scanf要写成scanf_s而OJ上用的是标准GCC写scanf_s反而编译不过如果用了#include bits/stdc.h在部分严格环境下也可能出问题。我自己的习惯是尽量用标准头文件比如cstdio、iostream、string、cctype这样换到哪个OJ都安全。另一点需要提前适应的是输入输出重定向。本机调试时可以打开文件读数据但提交时所有代码走标准输入输出不要把文件操作留在提交代码里否则评测系统大概率判你运行时错误。2. Day1核心题目拆解从输入输出到边界处理2.1 题目一AB的“隐藏坑”——多组数据输入我Day1第一题是一个看起来简单到不能再简单的AB输入包含多组数据每组占一行包含两个整数处理到文件末尾。很多第一次上机的同学看到这题直接写一个scanf(%d%d, a, b)然后单组数据确实能过一提交就卡住问题就出在没有处理“多组数据到EOF”。这里其实考察的是scanf的返回值scanf返回成功读取的变量个数如果读到文件末尾返回EOF通常是-1。所以标准写法是#include cstdio int main() { int a, b; while (scanf(%d%d, a, b) 2) { printf(%d\n, a b); } return 0; }用C的cin也可以达到同样的效果#include iostream int main() { int a, b; while (std::cin a b) { std::cout a b std::endl; } return 0; }如果题目改成第一行给一个组数T后面再给T组数据那就不能再用EOF判断而是先读T再循环T次。这两种输入模式几乎是机试必考Day1一定要把它们的区别刻在脑子里。我还特意试过Python写法import sys for line in sys.stdin: a, b map(int, line.split()) print(a b)Python处理这种题很简洁但如果DHU机试限定了只能C/C还是老老实实用C。这题真正要练的不是加法而是“代码在未知数量的输入下能不能正确终止”。2.2 题目二字符串反转与回文判断核心是边界第二题是一道经典字符串题给定一行字符串忽略其中的空格和标点符号并且忽略大小写判断它是否是回文。比如A man, a plan, a canal: Panama处理后是amanaplanacanalpanama反转后仍然一样所以输出YES。这道题看起来不难但写起来很容易出小毛病。第一个坑是题目没说字符串里会不会包含大写字母所以要先统一转小写第二个坑是“忽略空格和标点”不等于直接删掉所有非字母字符而是要遍历一次把字母收集到一个新字符串里第三个坑是回文比较时下标容易弄错特别是空串、单字符字符串这种极端情况。我当时的实现是这样的#include iostream #include string #include cctype bool isPalindrome(std::string s) { std::string filtered; for (char c : s) { if (std::isalnum(c)) { filtered.push_back(std::tolower(c)); } } int left 0; int right (int)filtered.size() - 1; while (left right) { if (filtered[left] ! filtered[right]) { return false; } left; --right; } return true; } int main() { std::string line; std::getline(std::cin, line); std::cout (isPalindrome(line) ? YES : NO) std::endl; return 0; }用std::isalnum判断字母或数字std::tolower统一转小写都是C标准库自带的功能。这里有个细节isalnum和tolower的参数是int类型但传入char也没问题只是如果有中文输入按字节处理会出现意外好在机试题目一般都会规定输入只含英文字符和常见标点。std::getline可以读入带空格的整行如果题目要求读入多行字符串就要注意上一行输入残留的换行符问题。Day1我在这道题上吃过亏输出格式要求是“YES”或“NO”全大写结果第一次写成了“Yes”直接被判WA所以读题时一定要把输出格式看清。2.3 题目三斐波那契列变体从“会递归”到“会递推”第三题是斐波那契数列的变形F(1)1F(2)1F(n)F(n-1)F(n-2)输入一个n要求输出F(n) % 1000000007。n的范围可能到10^7甚至更大。如果一上来就写递归int fib(int n) { if (n 1 || n 2) return 1; return fib(n - 1) fib(n - 2); }遇到稍微大一点的n程序就直接卡死或者栈溢出。因为递归会重复计算大量子问题时间复杂度是指数级的。正确做法是从前往后递推用三个变量滚动更新只保留最近两个值#include cstdio const int MOD 1000000007; int main() { int n; scanf(%d, n); long long a 1, b 1, c 1; for (int i 3; i n; i) { c (a b) % MOD; a b; b c; } printf(%lld\n, c); return 0; }这里用long long不是小题大做。虽然取模前a b最大约2 * 1000000006还没超过int上限但在其他题目里可能就没这么幸运。养成“数值计算一律给long long留余量”的习惯能少踩很多雷。取模操作放在每次递推之后能避免中间结果过大。Day1做这道题我的目标是理解“递推代替递归”的意义。如果n给到10^18靠循环也会超时那是后面要学的矩阵快速幂。第一天上手不贪多先把滚动递推练熟已经足够应对大多数机试基础题。3. 实操过程代码实现与自测设计3.1 本地IDE与OJ编译器的差异别让环境拖后腿我在Day1实操时踩过一个看似很蠢的坑本地用的是Visual Studio写scanf被强制要求改成scanf_s于是为了省事把代码里的输入函数全部换成了scanf_s本地一跑正常结果丢到OJ上直接编译失败。后来又老老实实改回scanf才意识到“编译器环境不一致”是机试备考最容易忽略的问题。建议第一天就把自己的开发环境固定下来。如果图省心直接装Code::Blocks或者VS Code GCC用MinGW的g编译这样和很多学校OJ使用的GCC环境基本一致。还要注意main函数一定写return 0;这不仅是规范也是很多OJ判题的一个隐含约定。虽然不写也可能能过但没必要在细节上冒险。调试方面本地用断点看变量没问题但提交前一定要把所有的printf调试输出删掉或注释掉。我还习惯在编码前先在纸上写下算法的大致步骤尤其是题目有多个限制条件时先列出来再动手写代码比边写边想效率高很多。3.2 核心代码调试用输出定位也要防止输出污染Day1第二题的回文判断我第一次提交WA因为输出写成了“Yes”而不是“YES”。这种错误如果只看样例是永远发现不了的因为样例也许刚好用“YES”。后来我在代码里临时加了一句std::cout filtered std::endl;把过滤后的字符串打出来检查发现字母大小写虽然转了但标点符号也被保留了下来。问题在于我误用了isalpha它只判断字母不包含数字而题目里明确写了要忽略“空格和标点”但没说忽略数字。最后改用isalnum将字母和数字都保留才通过。调试时加输出是个好办法但提交前一定要清理干净。有一次我为了定位一个循环边界问题在循环体里加了一行printf(%d , i);本地测完忘了删直接提交结果输出多了一大堆数字被判WA。这种问题比算法写错还冤。我的经验是在代码文件顶部用一个#define DEBUG宏调试输出都包在#ifdef DEBUG里面提交前只注释掉宏定义就行再用编辑器全局搜索printf或cout确认清理干净。3.3 自测数据怎么设计光靠样例远远不够很多同学写完代码把题目给的样例一贴能过就提交结果一提交就挂在隐藏测试点上。机试的测试点最爱的就是边界值数组长度是0、输入n是1、字符串里全是空格、数字达到题目最大值。Day1我就针对每道题专门做了几组自测数据。第一题AB不能只测1 2这种正常数据还要测空文件也就是直接回车还要测负数看scanf返回值会不会受影响。字符串回文那题自测数据包括空字符串、单字符、大小写混合、前后左右全是标点的情况。斐波那契那题自测n1、n2、n3、n50再用递归版暴力程序对拍结果。这里分享一个笨但有效的方法写一个确定正确但效率低的暴力函数再写一个优化后的函数用随机数据跑循环比较结果是否一致。一旦发现不一致就缩小数据规模很快能定位问题。4. 常见问题与排查技巧实录4.1 Runtime Error快速定位数组越界是头号嫌疑Day1第一天就碰到一次Runtime Error我明明在本地跑得好好的交上去就报RE。后来翻来覆去检查发现是在做字符串处理时访问了s[s.size() - 1]但当时的字符串恰好是空串size()返回00 - 1在无符号数下变成一个巨大的数直接越界。修复办法是先判断!s.empty()再访问末尾元素。在机试里RE最常见的两个原因就是数组越界和除零。排查思路是这样的先把代码里所有数组下标打印出来确认没有小于0或大于等于数组大小再检查所有除法或取模的变量是否可能为0。如果代码很长可以用二分注释法把一半功能注释掉看RE是否消失快速缩小范围。还有一个经验数组开大不亏宁可多开10个元素也不要卡着上限开。比如题目说字符串长度不超过1000建议直接开char s[1010]留出一点点余地防止\0和边界误判。4.2 TLE超时先算时间复杂度再想优化超时这类问题Day1暂时遇得少但很多同学第一次用递归写斐波那契时就会体验到什么叫TLE。看到一个题第一步不是动手写而是先看数据范围如果n最大是10^7那么O(n)的算法大概率能过如果n最大是10^9O(n)也悬如果n最大是10^18基本只能考虑快速幂或矩阵优化。有了数量级概念才知道该用哪种写法。Day1我在斐波那契那题上特意试了一下用cin和cout代替scanf和printf在n比较大的时候明显更慢。后来养成了习惯在需要读入大量数据的题目里要么直接用scanf/printf要么在main开头加上两行std::ios::sync_with_stdio(false); std::cin.tie(0);这两行能把C流和C标准IO的同步关掉让cin、cout快很多。不过要注意如果混用cin和scanf关闭同步后两者可能会乱序所以最好永远只用一种输入输出风格。4.3 Day1自检清单提交前逐项过一遍我把第一天踩过的坑整理成一张清单每次提交前都看一眼特别管用检查项常见问题我的处理方式变量类型int溢出、printf格式写错数值累加或取模前先估算范围必要时用long long数组大小越界、末尾\0位置不够上限再加10字符串开大一点多组输入没有处理EOF、循环内变量未重置确认是“读到EOF”还是“先给T组”字符串处理s.empty()没判断、大小写没统一访问前判空统一转小写输出格式大小写、空格、换行、多输出调试信息逐字读输出要求提交前全局搜索cout/printf取模中间结果溢出每次运算后立即取模别攒到最后全局变量多组数据测试时状态残留每组数据开始前重新初始化这张清单我打印出来放在键盘边上。只要提交前逐项检查很多低级WA都能避免。5. Day1完成之后我建议你这样做5.1 第一天不必追求题量关键是建立流程我Day1一共只刷了大概五道题数量不多但每一道都经历了“看题→想边界→写码→自测→提交→总结”的完整过程。这种感觉很重要机试考的不只是算法知识更是考试节奏。第一天如果把流程跑顺后面刷题时会越来越快如果第一天只追求AC数量忽略自测和总结那第二天很容易原地踏步。有个小技巧是每做完一道题在代码注释里写一句“这题我踩了什么坑”比如“忘记重置sum”“输出多了空格”“数组开小了”。到考前一周再翻这些注释就是你的个性化错题集比任何资料都有效。5.2 第二天可以开始碰排序和二分Day1把输入输出、字符串、递推这三种基础练熟之后Day2我建议安排排序、贪心和二分查找。这些是DHU机试的第二梯队考点几乎每年都会出现。排序要会用std::sort但也要知道自定义比较函数怎么写二分查找要理解边界条件比如while (left right)和while (left right)的区别。这些内容不需要第一天就硬啃先把地基打牢。最后再说句实在话DHU机试和真正搞竞赛的同学水平之间还是有距离的不用被网上那些ACM金牌选手的题单吓住。Day1安心把基础题写稳把环境摸熟把自测习惯练出来就已经比大多数人准备工作做得好。第二天开始你会发现原来很多看着唬人的题目拆开之后就是今天这些基本功的组合。