简介这份打包文件收纳了杭州电子科技大学在线OJ平台1000至1099号区间的多道题目C/C题解共90个文件以62个cpp源文件与16个c源文件为主另附少量Visual C工程调试文件pdb、dsp、opt等压缩包整体仅1.1MB。题目覆盖基础算法、数据结构、数学应用与逻辑推理涉及大数运算、最大子段和、状态压缩动态规划、图论最短路等经典问题难度梯度丰富适合正在刷题备战比赛或系统提升编程能力的同学使用。代码均已标注调试通过可对照题意拆解解题思路学习指针、结构体、递归等C/C特性在真实问题中的应用也能体会如何通过优化降低时间与空间复杂度。资源已有1824人学习下载体积轻量、无需复杂环境即可查看源码是一份便于在线复习和反复揣摩的高性价比OJ代码合集。 如果你在搜索引擎里敲下“杭州电子科技大学在线oj_1000-1099代码”这串字符我猜你大概率是被算法课作业、考研复试上机或者ACM社团招新推到了这里。杭州电子科技大学在线评测系统也就是大家常说的HDU OJ是国内老牌ACM训练平台之一题号从1000开始编号1000到1099这100道题正好是给新人准备的一条完整入门跑道。这篇文章不准备把100道题的原样代码全部堆给你那样既违反OJ刷题的意义也太容易让人看一遍就忘我更想把这个区间里最值得吃透的几类题、最容易踩的坑、每道经典题背后的思路节点讲清楚。如果你刚注册账号不久或者正在准备复试上机这篇应该能帮你少走不少弯路。1. 为什么是1000-1099HDU OJ入门区间的真实定位1.1 题号即难度HDU OJ没有花哨的难度标签老用户基本靠题号判断题目年代和难度。1000是一道AB1001是一道求和1002就变成大数加法1003是最大子段和1005是递推取模。前几十题看着简单其实是在用最简洁的题目逼你把在线评测系统的脾气摸透多组输入、EOF、输出空行、Case前缀、数据范围。这些基本功不过关后面做任何题都会反复吃罚时。很多第一次注册的人会觉得“AB也算题”于是直接跳过前面几题去挑难题做。我的建议是不要跳。1000到1009这几道题价值不在于算法而在于让你在没有心理负担的情况下熟悉提交、编译、看判题结果这几个动作。等你把1001的Presentation Error调通就会记住“输出格式也是答案的一部分”这条铁律。1.2 难度曲线的真实拐点这个区间的难度并不是持续爬坡而是有明显拐点。1000到1009以模拟和基础数学为主属于“看懂题就能写”的阶段。1010开始出现DFS加剪枝1016是素数环回溯搜索1018开始用斯特林公式估阶乘位数1023是卡特兰数1024是最大m子段和的动态规划1025是LIS1026是BFS路径输出。可以说从1000刷到1099等于把基础算法里的模拟、高精度、贪心、搜索、DP、数论、组合数学都过了一遍。很多学校的算法课大纲差不多就是按这个顺序排的。1.3 谁在刷这个区间刷这个区间的基本是三类人。第一类是大一新生算法课老师把HDU OJ的题目当作业布置1000-1099几乎是默认作业段位。第二类是考研党不少院校复试上机会指定HDU OJ作为练习平台很多人会集中把前一千多题刷一遍。第三类是ACM社团新人学长通常会丢一句“先把1000到1099过完再来找我”。所以这个区间在网上的搜索量一直很高二手代码满天飞但真正把它刷出价值的人反而不多原因就在于很多人只是交了代码没有总结。2. 从1000到1002在线评测的第一课是格式不是算法2.1 1000 AB ProblemEOF多组输入模板先看最基础的AB它最大的特点就是多组输入输入数据不知道有多少组一直读到文件末尾为止。很多新生在这里就翻车因为老师上课讲的是单组输入的cin a b遇到多组输入就只处理了一组然后奇怪为什么Wrong Answer。#include cstdio int main() { int a, b; while (scanf(%d%d, a, b) ! EOF) { printf(%d\n, a b); } return 0; }这段代码是HDU OJ刷题生涯里最常复用的模板以后凡是题目描述里出现“Input contains multiple test cases”或“EOF”字样的题都用这个结构开头。用scanf而不是cin主要是效率和习惯问题。OJ上输入量大时scanf和cin的性能差距会很明显建议新人早点习惯scanf/printf的组合。这个模板要练到不用想就能打出来的程度。2.2 1001 Sum Problem公式没错却Presentation Error第二题计算1到n的和同样多组输入。很多人一开始用循环累加结果超时改成公式n*(n1)/2后又WA或者PE。这里有两个坑。第一个是数据范围n如果比较大n乘n1会溢出int必须用long long。第二个是输出格式题目要求每组结果后面跟一个空行所以正确写法是#include cstdio int main() { int n; while (scanf(%d, n) ! EOF) { long long ans (long long)n * (n 1) / 2; printf(%lld\n\n, ans); } return 0; }注意printf里是两个换行符如果只写一个\n评测机就会判定为Presentation Error。PE在HDU OJ里是输出格式错误意味着答案数值是对的但空行、空格和题目要求不一致。PE看着离Accepted很近实际同样扣时间而且特别消耗耐心。建议读题时遇到“blank line”“Case x:”“there is a blank line between”这类字眼直接用笔圈出来别等交上去被判了PE再返工。提示PE经常比WA更让人难受因为它意味着你只差一个空行就能过。提交之前逐字对照一行样例输出能省下很多次无谓的提交。2.3 1002 AB Problem II大数加法的字符串模拟这道题开始上强度了两个数可以大到1000位int和long long全部失效。解法是把数字当作字符串处理从低位到高位逐位相加维护进位。#include bits/stdc.h using namespace std; string add(string a, string b) { int i a.size() - 1, j b.size() - 1, carry 0; string res; while (i 0 || j 0 || carry) { int sum carry; if (i 0) sum a[i--] - 0; if (j 0) sum b[j--] - 0; res char(sum % 10 0); carry sum / 10; } reverse(res.begin(), res.end()); return res; } int main() { int t; scanf(%d, t); for (int k 1; k t; k) { string a, b; cin a b; cout Case k : endl; cout a b add(a, b) endl; if (k ! t) cout endl; } return 0; }这段代码的核心逻辑是从末尾开始逐位相加把个位留下十位以上作为进位传给下一位最后翻转字符串。这个加法思路以后会在多个高精度题里反复出现。用Java的人可以选BigInteger直接过但我还是建议至少把C字符串加法自己写一遍因为有的比赛环境不支持Java大数或者题目会要求你实现高精度。这道题的输出格式也是经典每个Case之间要多输出一个空行但最后一个Case后面没有额外空行这个细节值得记住。2.4 从三题提炼出的通用读题习惯做完这三题你应该能总结出一套自己的读题清单。第一输入是多组还是单组多组就上while循环单组千万别写死循环。第二看样例输出里的Case前缀、空行、空格位置这些不是摆设。第三看数据范围int能装多少、long long能装多少、是不是要上高精度做题前先心里有数。这套习惯比会背十道题的答案重要得多。3. 1003到1005算法思维的三个拐点3.1 1003 Max SumDP第一课1003是很多人的第一个动态规划题。题目给一个数列让你找出一段连续子序列使和最大并输出最大和以及这个子序列的左右端点。暴力枚举所有子区间是O(n^2)数据一大就会超时于是要用状态转移的思路。思路是这样用一个变量记录以当前位置结尾的最大连续和如果前面的累加和是负数说明它对后面没有帮助直接丢弃从当前数重新开始否则累加。同时用变量记录最优解的起点和终点。int sum 0, best a[1], start 1, end 1, tmp 1; for (int i 1; i n; i) { if (sum 0) { sum a[i]; tmp i; } else { sum a[i]; } if (sum best) { best sum; start tmp; end i; } }这就是最大子段和的经典写法代码很短但它是“动态规划”这个概念从抽象变成可操作的第一步。后面你还会遇到大量“维护一个状态变量并记录状态转移来源”的题1003练的就是这个能力。题目输出同样要求在两组数据之间空行处理方式参考1001和1002。3.2 1004 Let the Balloon Rise哈希计数的第一次实战这道题会给你很多气球颜色让你统计出现次数最多的颜色。本质是字符串计数C里直接用mapstring, int每读入一个颜色就加一最后遍历map找最大值。也可以把颜色看成字符串数组用sort加相邻比较或手写哈希。这道题的价值是让你第一次认识到可以用数据结构代替手写逻辑。很多新生面对“统计出现次数最多”的第一反应是开两个数组一个存颜色一个存次数每次循环查找代码很啰嗦还没有效率。用map之后逻辑干净这也是后续字符串题、图论建模题的基本功。做完建议顺手把map的遍历、查找、删除这几个操作练熟因为后面很多题都要用。3.3 1005 Number Sequence递推不是硬算这道题对新手是个暴击。递推式是f(1)f(2)1f(n)(Af(n-1)Bf(n-2)) mod 7n可以到一亿以上。你要真开数组硬递推不是超时就是内存爆炸。关键是发现每一项只和前两项有关而对7取模之后前两项的组合状态最多只有7乘7等于49种所以序列一定存在循环节。找到循环节之后把n映射到循环节内的位置即可。比较严谨的写法是在递推过程里记录每个二元组(f(i-1), f(i))第一次出现的位置遇到重复说明循环开始然后根据循环长度计算f(n)。网上有些人直接用n%49的做法能过题但原理上并不严谨因为它默认循环从第1项开始而真实周期未必是49。建议你写的时候用map或数组记录状态位置或者直接上矩阵快速幂。我的矩阵快速幂模板就是从这道题开始记的后来在不少数论题里都用得上。3.4 拐点提醒从1003到1005难度跨度不大但思维跨度很大1003让你接触状态转移1004让你习惯用数据结构1005让你认识到算法不是无脑循环而是要利用数学性质。这三道题如果能独立想清楚后面真正的分水岭题目就能接得住。4. 1008到1010模拟、贪心和剪枝扎堆的实战现场4.1 1008 Elevator状态模拟的细节电梯题本身不难有一个请求序列电梯从0层出发上升一层6秒下降一层4秒每停靠一次5秒按顺序处理所有请求。新手最容易漏的是最开始那次停靠时间以及把“去往下一层”和“停靠”的时间算错。这道题的价值是培养维护当前状态的意识定义一个变量curFloor表示电梯当前楼层每处理一个请求先计算移动时间再加停靠时间然后更新curFloor。代码写起来很短但特别适合拿来纠正粗心。4.2 1009 FatMouse Trade贪心思想入门有一袋猫粮要去换JavaBean每个房间有不同数量的JavaBean和对应的猫粮价格可以按比例换取问最多能换多少。正确答案是把每个房间的性价比也就是JavaBean除以猫粮降序排序优先换性价比高的。这个思想就是贪心里最经典的分数背包对比0-1背包问题它允许拿一部分所以排序后一直取到包空即可。很多人卡在这里原因是试图用动态规划而不是贪心。要注意题目里表示可按相同比例交换的句子它决定了这道题是分数背包而不是01背包这也是读完题要做的第一层判断。贪心不一定总能得到最优解但在这个可分割的设定下它是安全的。以后你还会在活动安排、区间覆盖等题目里反复遇到同一套路1009就是最便宜的入门学费。4.3 1010 Tempter of the BoneDFS加奇偶剪枝1010是这个区间里最有名的一道搜索题。迷宫从S到D墙不能走要求恰好用T步到达而不是最短路径到达。很多人第一反应是BFS求最短路径但这道题要的是恰好T步只能DFS回溯搜索所有可行路径。裸DFS会超时所以必须剪枝。最经典的剪枝是奇偶剪枝。棋盘上相邻两个格子颜色不同从起点到终点哪怕走最短路所需步数和曼哈顿距离的奇偶性也一定相同。如果剩余步数与剩余曼哈顿距离的奇偶性不一致说明无论如何都无法刚好走完直接剪掉。另一个剪枝是剩余步数如果已经小于曼哈顿距离也不可能到达。这道题的DFS回溯框架和剪枝判断是搜索题的关键模板建议独立实现一遍并画出递归树理解一次。bool dfs(int x, int y, int step) { if (x dx y dy step t) return true; if (step t) return false; int dist abs(x - dx) abs(y - dy); if (dist t - step || ((t - step - dist) 1)) return false; // 枚举四个方向标记vis递归回溯 }4.4 同一区间其他值得留名的题除了上面这几道1000到1099里还有不少值得一做的题。我列成一张速查表方便你刷题时对照题号考点一句话提醒1006时钟指针夹角按秒算角度注意浮点精度1007最近点对分治归并排序思想1013数根九余数定理比模拟循环快1016素数环DFS加素数判定1018阶乘位数斯特林公式或log10求和1022栈模拟用栈判断火车进出站序列1023卡特兰数大数版卡特兰高精度乘法1024最大m子段和滚动数组优化DP1025LIS最长上升子序列二分优化1026BFS路径输出BFS记录父节点再回溯输出这张表里的题不用一次全刷完但建议按类型分批做。比如今天专攻搜索类就把1010和1016放一起明天专攻动态规划就把1003和1024放一起。这样比按题号顺序硬刷要高效得多。5. 像老手一样刷完这个区间规则细节与后续价值5.1 评测机不会告诉你的规则HDU OJ的判题结果有AC、PE、WA、TLE、MLE、RE、CE几种。刚上手时CE主要是头文件或语法问题RE往往是数组越界或除零TLE提醒你算法复杂度太高。别被这些缩写吓到每个都点开看一下编译器给出的详细信息慢慢就有感觉。有一个细节特别重要数组要开成全局变量不要放在main函数里。OJ的栈空间有限局部大数组经常直接爆栈变成RE全局变量则没有这个问题。另外清空数组用memset比手写循环快但memset只对0和-1这类值友好别拿它给数组填充1。还有老版本HDU OJ的G环境对long long的格式化输出曾经只认%I64d不认%lld现在基本都支持%lld了但如果你遇到奇怪的输出问题可以留意一下编译器版本。5.2 把代码整理成模板库这个区间刷完之后建议你做一件很朴素但长期受益的事把所有AC代码按类型归档建立自己的模板库。比如输入输出模板、大数四则运算、DFS/BFS框架、常见DP状态设计、排序和二分模板。注意这里的模板不是收藏夹里别人写的代码而是你自己重写、经过验证、能一眼看懂还带注释的代码。准备复试或比赛前翻自己的模板库会比翻题解网站快得多因为你亲手敲过的代码大脑检索起来最熟练。5.3 下一步怎么走1000到1099这个区间本质上是基础能力的铺路。刷完之后可以往两个方向走一个是按专题刷比如图论、数论、字符串、计算几何配合经典算法书把每个专题吃透另一个是开始打虚拟比赛强迫自己在有限时间内完成多道题训练取舍和读题速度。HDU OJ往上还有大量题号更靠后的经典题平台题目量非常充足完全够你从入门练到省赛水平。我自己当年在这个区间也走过弯路先是到处求代码交上去过了就觉得自己会了结果复试上机一紧张连1001的空行都忘了处理。后来我给自己立了个规矩别人的题解可以看但看完思路一定要把浏览器关掉自己在编译器里敲一遍敲不出来就再看再敲直到能独立AC为止。1000到1099这些题代码总量不算大但每一个你亲手踩过的坑都会在某一次考试或比赛里帮你抢回时间。本文还有配套的精品资源点击获取
简介这份打包文件收纳了杭州电子科技大学在线OJ平台1000至1099号区间的多道题目C/C题解共90个文件以62个cpp源文件与16个c源文件为主另附少量Visual C工程调试文件pdb、dsp、opt等压缩包整体仅1.1MB。题目覆盖基础算法、数据结构、数学应用与逻辑推理涉及大数运算、最大子段和、状态压缩动态规划、图论最短路等经典问题难度梯度丰富适合正在刷题备战比赛或系统提升编程能力的同学使用。代码均已标注调试通过可对照题意拆解解题思路学习指针、结构体、递归等C/C特性在真实问题中的应用也能体会如何通过优化降低时间与空间复杂度。资源已有1824人学习下载体积轻量、无需复杂环境即可查看源码是一份便于在线复习和反复揣摩的高性价比OJ代码合集。 如果你在搜索引擎里敲下“杭州电子科技大学在线oj_1000-1099代码”这串字符我猜你大概率是被算法课作业、考研复试上机或者ACM社团招新推到了这里。杭州电子科技大学在线评测系统也就是大家常说的HDU OJ是国内老牌ACM训练平台之一题号从1000开始编号1000到1099这100道题正好是给新人准备的一条完整入门跑道。这篇文章不准备把100道题的原样代码全部堆给你那样既违反OJ刷题的意义也太容易让人看一遍就忘我更想把这个区间里最值得吃透的几类题、最容易踩的坑、每道经典题背后的思路节点讲清楚。如果你刚注册账号不久或者正在准备复试上机这篇应该能帮你少走不少弯路。1. 为什么是1000-1099HDU OJ入门区间的真实定位1.1 题号即难度HDU OJ没有花哨的难度标签老用户基本靠题号判断题目年代和难度。1000是一道AB1001是一道求和1002就变成大数加法1003是最大子段和1005是递推取模。前几十题看着简单其实是在用最简洁的题目逼你把在线评测系统的脾气摸透多组输入、EOF、输出空行、Case前缀、数据范围。这些基本功不过关后面做任何题都会反复吃罚时。很多第一次注册的人会觉得“AB也算题”于是直接跳过前面几题去挑难题做。我的建议是不要跳。1000到1009这几道题价值不在于算法而在于让你在没有心理负担的情况下熟悉提交、编译、看判题结果这几个动作。等你把1001的Presentation Error调通就会记住“输出格式也是答案的一部分”这条铁律。1.2 难度曲线的真实拐点这个区间的难度并不是持续爬坡而是有明显拐点。1000到1009以模拟和基础数学为主属于“看懂题就能写”的阶段。1010开始出现DFS加剪枝1016是素数环回溯搜索1018开始用斯特林公式估阶乘位数1023是卡特兰数1024是最大m子段和的动态规划1025是LIS1026是BFS路径输出。可以说从1000刷到1099等于把基础算法里的模拟、高精度、贪心、搜索、DP、数论、组合数学都过了一遍。很多学校的算法课大纲差不多就是按这个顺序排的。1.3 谁在刷这个区间刷这个区间的基本是三类人。第一类是大一新生算法课老师把HDU OJ的题目当作业布置1000-1099几乎是默认作业段位。第二类是考研党不少院校复试上机会指定HDU OJ作为练习平台很多人会集中把前一千多题刷一遍。第三类是ACM社团新人学长通常会丢一句“先把1000到1099过完再来找我”。所以这个区间在网上的搜索量一直很高二手代码满天飞但真正把它刷出价值的人反而不多原因就在于很多人只是交了代码没有总结。2. 从1000到1002在线评测的第一课是格式不是算法2.1 1000 AB ProblemEOF多组输入模板先看最基础的AB它最大的特点就是多组输入输入数据不知道有多少组一直读到文件末尾为止。很多新生在这里就翻车因为老师上课讲的是单组输入的cin a b遇到多组输入就只处理了一组然后奇怪为什么Wrong Answer。#include cstdio int main() { int a, b; while (scanf(%d%d, a, b) ! EOF) { printf(%d\n, a b); } return 0; }这段代码是HDU OJ刷题生涯里最常复用的模板以后凡是题目描述里出现“Input contains multiple test cases”或“EOF”字样的题都用这个结构开头。用scanf而不是cin主要是效率和习惯问题。OJ上输入量大时scanf和cin的性能差距会很明显建议新人早点习惯scanf/printf的组合。这个模板要练到不用想就能打出来的程度。2.2 1001 Sum Problem公式没错却Presentation Error第二题计算1到n的和同样多组输入。很多人一开始用循环累加结果超时改成公式n*(n1)/2后又WA或者PE。这里有两个坑。第一个是数据范围n如果比较大n乘n1会溢出int必须用long long。第二个是输出格式题目要求每组结果后面跟一个空行所以正确写法是#include cstdio int main() { int n; while (scanf(%d, n) ! EOF) { long long ans (long long)n * (n 1) / 2; printf(%lld\n\n, ans); } return 0; }注意printf里是两个换行符如果只写一个\n评测机就会判定为Presentation Error。PE在HDU OJ里是输出格式错误意味着答案数值是对的但空行、空格和题目要求不一致。PE看着离Accepted很近实际同样扣时间而且特别消耗耐心。建议读题时遇到“blank line”“Case x:”“there is a blank line between”这类字眼直接用笔圈出来别等交上去被判了PE再返工。提示PE经常比WA更让人难受因为它意味着你只差一个空行就能过。提交之前逐字对照一行样例输出能省下很多次无谓的提交。2.3 1002 AB Problem II大数加法的字符串模拟这道题开始上强度了两个数可以大到1000位int和long long全部失效。解法是把数字当作字符串处理从低位到高位逐位相加维护进位。#include bits/stdc.h using namespace std; string add(string a, string b) { int i a.size() - 1, j b.size() - 1, carry 0; string res; while (i 0 || j 0 || carry) { int sum carry; if (i 0) sum a[i--] - 0; if (j 0) sum b[j--] - 0; res char(sum % 10 0); carry sum / 10; } reverse(res.begin(), res.end()); return res; } int main() { int t; scanf(%d, t); for (int k 1; k t; k) { string a, b; cin a b; cout Case k : endl; cout a b add(a, b) endl; if (k ! t) cout endl; } return 0; }这段代码的核心逻辑是从末尾开始逐位相加把个位留下十位以上作为进位传给下一位最后翻转字符串。这个加法思路以后会在多个高精度题里反复出现。用Java的人可以选BigInteger直接过但我还是建议至少把C字符串加法自己写一遍因为有的比赛环境不支持Java大数或者题目会要求你实现高精度。这道题的输出格式也是经典每个Case之间要多输出一个空行但最后一个Case后面没有额外空行这个细节值得记住。2.4 从三题提炼出的通用读题习惯做完这三题你应该能总结出一套自己的读题清单。第一输入是多组还是单组多组就上while循环单组千万别写死循环。第二看样例输出里的Case前缀、空行、空格位置这些不是摆设。第三看数据范围int能装多少、long long能装多少、是不是要上高精度做题前先心里有数。这套习惯比会背十道题的答案重要得多。3. 1003到1005算法思维的三个拐点3.1 1003 Max SumDP第一课1003是很多人的第一个动态规划题。题目给一个数列让你找出一段连续子序列使和最大并输出最大和以及这个子序列的左右端点。暴力枚举所有子区间是O(n^2)数据一大就会超时于是要用状态转移的思路。思路是这样用一个变量记录以当前位置结尾的最大连续和如果前面的累加和是负数说明它对后面没有帮助直接丢弃从当前数重新开始否则累加。同时用变量记录最优解的起点和终点。int sum 0, best a[1], start 1, end 1, tmp 1; for (int i 1; i n; i) { if (sum 0) { sum a[i]; tmp i; } else { sum a[i]; } if (sum best) { best sum; start tmp; end i; } }这就是最大子段和的经典写法代码很短但它是“动态规划”这个概念从抽象变成可操作的第一步。后面你还会遇到大量“维护一个状态变量并记录状态转移来源”的题1003练的就是这个能力。题目输出同样要求在两组数据之间空行处理方式参考1001和1002。3.2 1004 Let the Balloon Rise哈希计数的第一次实战这道题会给你很多气球颜色让你统计出现次数最多的颜色。本质是字符串计数C里直接用mapstring, int每读入一个颜色就加一最后遍历map找最大值。也可以把颜色看成字符串数组用sort加相邻比较或手写哈希。这道题的价值是让你第一次认识到可以用数据结构代替手写逻辑。很多新生面对“统计出现次数最多”的第一反应是开两个数组一个存颜色一个存次数每次循环查找代码很啰嗦还没有效率。用map之后逻辑干净这也是后续字符串题、图论建模题的基本功。做完建议顺手把map的遍历、查找、删除这几个操作练熟因为后面很多题都要用。3.3 1005 Number Sequence递推不是硬算这道题对新手是个暴击。递推式是f(1)f(2)1f(n)(Af(n-1)Bf(n-2)) mod 7n可以到一亿以上。你要真开数组硬递推不是超时就是内存爆炸。关键是发现每一项只和前两项有关而对7取模之后前两项的组合状态最多只有7乘7等于49种所以序列一定存在循环节。找到循环节之后把n映射到循环节内的位置即可。比较严谨的写法是在递推过程里记录每个二元组(f(i-1), f(i))第一次出现的位置遇到重复说明循环开始然后根据循环长度计算f(n)。网上有些人直接用n%49的做法能过题但原理上并不严谨因为它默认循环从第1项开始而真实周期未必是49。建议你写的时候用map或数组记录状态位置或者直接上矩阵快速幂。我的矩阵快速幂模板就是从这道题开始记的后来在不少数论题里都用得上。3.4 拐点提醒从1003到1005难度跨度不大但思维跨度很大1003让你接触状态转移1004让你习惯用数据结构1005让你认识到算法不是无脑循环而是要利用数学性质。这三道题如果能独立想清楚后面真正的分水岭题目就能接得住。4. 1008到1010模拟、贪心和剪枝扎堆的实战现场4.1 1008 Elevator状态模拟的细节电梯题本身不难有一个请求序列电梯从0层出发上升一层6秒下降一层4秒每停靠一次5秒按顺序处理所有请求。新手最容易漏的是最开始那次停靠时间以及把“去往下一层”和“停靠”的时间算错。这道题的价值是培养维护当前状态的意识定义一个变量curFloor表示电梯当前楼层每处理一个请求先计算移动时间再加停靠时间然后更新curFloor。代码写起来很短但特别适合拿来纠正粗心。4.2 1009 FatMouse Trade贪心思想入门有一袋猫粮要去换JavaBean每个房间有不同数量的JavaBean和对应的猫粮价格可以按比例换取问最多能换多少。正确答案是把每个房间的性价比也就是JavaBean除以猫粮降序排序优先换性价比高的。这个思想就是贪心里最经典的分数背包对比0-1背包问题它允许拿一部分所以排序后一直取到包空即可。很多人卡在这里原因是试图用动态规划而不是贪心。要注意题目里表示可按相同比例交换的句子它决定了这道题是分数背包而不是01背包这也是读完题要做的第一层判断。贪心不一定总能得到最优解但在这个可分割的设定下它是安全的。以后你还会在活动安排、区间覆盖等题目里反复遇到同一套路1009就是最便宜的入门学费。4.3 1010 Tempter of the BoneDFS加奇偶剪枝1010是这个区间里最有名的一道搜索题。迷宫从S到D墙不能走要求恰好用T步到达而不是最短路径到达。很多人第一反应是BFS求最短路径但这道题要的是恰好T步只能DFS回溯搜索所有可行路径。裸DFS会超时所以必须剪枝。最经典的剪枝是奇偶剪枝。棋盘上相邻两个格子颜色不同从起点到终点哪怕走最短路所需步数和曼哈顿距离的奇偶性也一定相同。如果剩余步数与剩余曼哈顿距离的奇偶性不一致说明无论如何都无法刚好走完直接剪掉。另一个剪枝是剩余步数如果已经小于曼哈顿距离也不可能到达。这道题的DFS回溯框架和剪枝判断是搜索题的关键模板建议独立实现一遍并画出递归树理解一次。bool dfs(int x, int y, int step) { if (x dx y dy step t) return true; if (step t) return false; int dist abs(x - dx) abs(y - dy); if (dist t - step || ((t - step - dist) 1)) return false; // 枚举四个方向标记vis递归回溯 }4.4 同一区间其他值得留名的题除了上面这几道1000到1099里还有不少值得一做的题。我列成一张速查表方便你刷题时对照题号考点一句话提醒1006时钟指针夹角按秒算角度注意浮点精度1007最近点对分治归并排序思想1013数根九余数定理比模拟循环快1016素数环DFS加素数判定1018阶乘位数斯特林公式或log10求和1022栈模拟用栈判断火车进出站序列1023卡特兰数大数版卡特兰高精度乘法1024最大m子段和滚动数组优化DP1025LIS最长上升子序列二分优化1026BFS路径输出BFS记录父节点再回溯输出这张表里的题不用一次全刷完但建议按类型分批做。比如今天专攻搜索类就把1010和1016放一起明天专攻动态规划就把1003和1024放一起。这样比按题号顺序硬刷要高效得多。5. 像老手一样刷完这个区间规则细节与后续价值5.1 评测机不会告诉你的规则HDU OJ的判题结果有AC、PE、WA、TLE、MLE、RE、CE几种。刚上手时CE主要是头文件或语法问题RE往往是数组越界或除零TLE提醒你算法复杂度太高。别被这些缩写吓到每个都点开看一下编译器给出的详细信息慢慢就有感觉。有一个细节特别重要数组要开成全局变量不要放在main函数里。OJ的栈空间有限局部大数组经常直接爆栈变成RE全局变量则没有这个问题。另外清空数组用memset比手写循环快但memset只对0和-1这类值友好别拿它给数组填充1。还有老版本HDU OJ的G环境对long long的格式化输出曾经只认%I64d不认%lld现在基本都支持%lld了但如果你遇到奇怪的输出问题可以留意一下编译器版本。5.2 把代码整理成模板库这个区间刷完之后建议你做一件很朴素但长期受益的事把所有AC代码按类型归档建立自己的模板库。比如输入输出模板、大数四则运算、DFS/BFS框架、常见DP状态设计、排序和二分模板。注意这里的模板不是收藏夹里别人写的代码而是你自己重写、经过验证、能一眼看懂还带注释的代码。准备复试或比赛前翻自己的模板库会比翻题解网站快得多因为你亲手敲过的代码大脑检索起来最熟练。5.3 下一步怎么走1000到1099这个区间本质上是基础能力的铺路。刷完之后可以往两个方向走一个是按专题刷比如图论、数论、字符串、计算几何配合经典算法书把每个专题吃透另一个是开始打虚拟比赛强迫自己在有限时间内完成多道题训练取舍和读题速度。HDU OJ往上还有大量题号更靠后的经典题平台题目量非常充足完全够你从入门练到省赛水平。我自己当年在这个区间也走过弯路先是到处求代码交上去过了就觉得自己会了结果复试上机一紧张连1001的空行都忘了处理。后来我给自己立了个规矩别人的题解可以看但看完思路一定要把浏览器关掉自己在编译器里敲一遍敲不出来就再看再敲直到能独立AC为止。1000到1099这些题代码总量不算大但每一个你亲手踩过的坑都会在某一次考试或比赛里帮你抢回时间。本文还有配套的精品资源点击获取
