ACM大学生程序设计竞赛在线题库最新精选题解（赵端阳）解析

在线OJ题库部分解析

非常感谢本书作者和编审人员，后悔没有早点看到此书，相见恨晚！在此推荐一波希望更多像我一样的小白能从中受益受益。

本书介绍：ACM大学生程序设计竞赛在线题库最新精选题解 本书OJ入口：HDOJ、ZOJ

说实话我觉得新手确实需要一份刷题单，带解析那种书。我个人也是新手才开这本书的题。我觉得写完读别人代码有很大提升，但是看题解大多数oj并不支持阅读其他人ac代码，而且很难找到优秀的代码。这本书给的代码让我学会很多奇技淫巧 。 这本书题单大多不错而且基本难度递增，本文主要为了指出书中部分不当之处。（仅为个人意见）

提示：本书为当前最新版（2019年7月出版）

本章基本水题，但是对新生来说必不可少，可以增强信心 ，可以把基本功打牢，比如sum总是忘初始化0，输出格式不对，二分边界总写错等等常见bug（虽然我也总wa在奇奇怪怪的点

HDOJ1056-HangOver：此题推出公式应该没什么问题，掌握浮点输出应该不会错。值的注意的是int/int还是int，所以以后有double时吧所有整型常数都变成xx.0形式。 并不推荐，可以参考下题练习：PATL3-013非常弹的球题解。

HDOJ1735-字数统计:此题出的有点烂，但是没刷过模拟题的可以试试，实际上有两种情况题解没有考虑到，应该是出题人的锅，可以改进一下算法，参见HDOJ1735-字符统计题解，不必要再用一遍for循环记录空白数，直接第一次读入时用index记录最后一行最后有字的位置即可。

ZJU1058-Currency Exchange：并不推荐。

ZJU1067-Color Me Less：并不推荐。

ZJU1078-Palindrom Numbers:强烈建议新手不看书写一遍，然后看书题解，再独立写一遍。,简单的回文判断和进制转换至少不能超过3分钟写完，简单题都要调试半天的话那比赛中难题会更卡。

ZJU1090-The Circumference of the Circle:不建议写，思维题。

ZJU1095-Humble Numbers:丑数，建议看书后能独立完成，毕竟赛场过不了的题打表是基本操作。

ZJU1105-FatMouse’s Tour:题意较怪，可以一试，不过书中代码有坑，大多数测评机c++已经不支持gets（），书中代码用C(gcc 6.5.0)编译可以AC。此外书中%dist应为印刷错误，应该是%d。参见ZJU1105-FatMouse’s Tour题解

ZJU1151-Word Reversal：简单题，新手建议写写。

ZJU1154-Niven Numbers:水题，建议新手看书后独立完成。

本章算是正式入门第一步，模拟题需要考虑的特殊情况较多，比赛一个特殊点过不了都算wa，所需要的代码能力要求较高。写模拟可以训练补充漏洞以及造数据能力。可以学一下acm对拍数据。

HDOJ1035-Robot Motion：模拟题，新手可以一试。

HDOJ猜数字：暴力循环1000-9999即可。新手随便写写。

HDOJGrey Area：书中印错一处，图2-1应为图2-2。鉴于没有源码参考发篇题解：HDOJGrey Area题解

HDOJ-Scaring the brid：可以用深搜但没必要，数据很小，建议按书上做法枚举所有状态，最多210，尝试一下状态压缩做法。另外本题有一个坑点即judge函数的s从0开始，因为有测试数据是所有稻草人位置占了整个图，这样0个也可以过。

HDOJ-ArcSoft’s Office Rearrangement：思维题，但是值得试试。

ZJU1003-Crashing Balloon：因数分解，递归做法。建议独立写写。

ZJU1006-Do the Untwist：凯撒密码，很水，看心情写~

ZJU1016-Parencodings：建议独立完成，看完题解可以再试试。

ZJU1039-Number Game：本题出的很突兀，可以顺便学一下博弈论的sg函数。本题还需要记忆化搜索和状压。建议写完第六章回过头来补这个题。

ZJU1042-W’s Cipher：还是凯撒密码，稍微复杂点，可以试试。

ZJU1051-A New Growth Industry：纯模拟，可以练手。

ZJU1056-The Worm Turns：本章第一道大型模拟题，可以试试，但是赛场说实话基础不牢还是没信心开这种大型模拟的。

ZJU1057-Undercut：并不推荐，很无聊的题。

ZJU1073-Round and Round We Go：循环数，很有意思。可以模拟试一遍然后写后面数学做法。膜北大大佬，硬是把模拟题写成数学题。%%%

ZJU1088-System Overload：约瑟夫环，不要模拟了，太水了，推一下后面公式然后写递归做法，书上for循环版本也行，但建议再试试递归。不过本题有个坑点是1号楼永远先断，所以序号建议自己推下。

ZJU1098-Simple Computers：学了计组可以试试本题。

ZJU1144-Robbery：纯模拟，可以试试。

ZJU1160-Biorhythms：同余定理，建议模拟试一遍后学学中国剩余定理，网上讲的感觉好复杂，实际就是两数加最小公倍数同余 a%m=b%m表示成a≡b(mod m）。本题中设 x≡p(mod 23);x≡e(mod 28);x≡i(mod 33);这样推出 p+=23满足（p-e)%28=0时p满足前两个方程,以此类推。

本章前后关联性不大，建议跳过本章从第四章开始。如果你刷PAT那当我没说，高校机试确实有很麻烦的处理字符串问题。

本章不做说明。

本章题并不多，建议全部写一遍，熟练掌握高精乘即可。

HDOJ2940-Hex Factorial: 高精阶乘，保存结果打表即可。原书程序可以优化一下，详见HDOJ2940高精度阶乘优化版。

ZJU1205-Martian Addition: 进制20的高精度乘法。本章没什么好说的，可以参考洛谷高精度与模拟题单。

ZJU1210-Reciprocals: 建议独立完成。不过书上代码是假的，样例都过不了还ac?。思路没问题，但是去掉末尾0后精度long long远远不够，还需要大整数模拟。参考题解：ZJU1210-Reciprocals题解。

ZJU1962-How Many Fibs?：斐波那契大整数模拟。打表判断，书上思路很好倒着存补‘0’然后用strcmp比较。当然也可以用int型数组存结果然后自己写个比较函数。本题也建议独立完成。

本章旨在熟悉基本的STL，本章题量仍很少，不熟悉STL的同学可以边学边写，熟练的就直接跳过本章。

HDOJ3682-To Be an Dream Architect: 给各个点编号即可，不断加入vector中然后去重，书上代码可以理解为给x轴赋权值n2,给y权值n,给z赋权值1，相当于独立编号。还不懂的同学建议百度一下哈希是什么。

ZJU1004-Anagrams by Stack: 本题出在本章难度显得略高，但递归一定是入门最需要克服的坎。本题dfs便是不断搜索的过程，初学递归往往难点之一是不知道递归的参数是什么，会递归但不会写递归。我也是学了很久才渐渐熟练会写递归。参数往往是每次前进一个状态的变化的量，更简单的找出其中参数是找到最终需要用来判断边界的量，每次传递下一个状态的参数即可。

ZJU1061-Web Navigation: 用到stack的简单模拟，不熟悉的试试stack用法，熟悉跳过即可。

ZJU1062-Trees Made to Order：了解组合数学应该是能看明白题解的，组合数学著名的三个数列：Fibonacci、Stirling、Catalan。建议不懂的小白学下组合数学，机器学习绕不过组合数学的。本题用到卡特兰数，不懂具体怎么分析是看不懂题解在说什么的，觉得难的同学可以先跳过本题，学完9章再回过头看其他博客学习卡特兰数用递归写。虽然网上确实没有适合新手的组合数学题解

ZJU1094-Matrix Chain Multiplication：还以为是动态规划，结果是简单递归。递归思路不难，就是每次把括号里两个矩阵算出相乘次数再转化成新矩阵，每次跳出括号不断累加。不过书上STL这个思路也很巧妙，相当于直接算成括号匹配了，用栈实现，本题类似逆波兰数，可以递归建树O（nlogn）也可以用堆栈实现O（n）算法。

ZJU1097-Code the Tree：说实话我也看不懂这个标程怎么实现的。但思路就是不把它当成树建图，而是当作无向连通图来存。然后不断输出最小的单节点，至于每次选中最小的点就用priority_queue实现，最小堆能在O(1)时间内求出最小数。本题值得一写。

ZJU1156-Unscrambling Images四叉树的递归，题目有点费解，看一遍很难明白题目在说啥。大致意思就是第一块输入压缩的四叉树编号， 第二个输入对应位置的颜色号。

刷完本章可以说算是入门半只脚了，本章建议新手全写一遍，打好基本功。 搜索的复杂度较高，所以难点不在于递归而在于剪枝，务必注意本章的各种剪枝操作。

HDOJ1010-Tempter of the Bone：很典型的深搜加剪枝题，广搜只能得到最短路所以不行（不明白为什么的同学建议这里开始学简单的数据结构知识），奇偶剪枝也不难，写上总没坏处 。

HDOJ1016-Prime Ring Problem：同样用奇偶判别剪枝，因为数字序列从1开始，如果是奇数个连续的数，就,一定会凑出一个至少和大于4的偶数。

HDOJ1175-连连看：建议本题bfs和dfs都做一遍，虽然书上没有剪枝，但实际上本题可以简单剪枝一下，即转弯两次后如果和终点不在一条线上那就没有必要往下试了。可以试一下这个剪枝，只需要一个判断条件return就行。另外bfs和dfs是基本功，像本题这种难度，至少半小时之内写完改完bug然后AC.如果感觉不熟练多写几遍，当然dfs写法有很多，可以像书上for外标记点，for内判断，也可以for外return判断边界，for内到下一层标记等等，多敲敲就能手熟（真肌肉记忆

HDOJ1241-Oil Deposits：很经典（老） 的题，值得一试。

HDOJ1242-Rescue：本题思路比较巧妙，反向搜索。另外注意如果是求最短路类型的题，dfs的复杂度虽然理论上和没有优化的bfs一样，但因为有回溯，所以时间一般是不用优先队列的bfs时间的两倍，虽然dfs好写，但其实带优先队列priority_queue的bfs也没有那么难，多练就熟悉了。dfs和bfs时间复杂度O(n2),而最小堆优化的bfs是O(nlogn)，比赛求最短路能用bfs就不要用dfs。

HDOJ1312-Red and Black：没有剪枝，和那道非常经典的油田题差不多，书上只给了dfs的代码，仍建议用bfs再写一遍。

HDOJ1539-Shredding Company：dfs,书上题解是标记空格位置然后迭代，递归每个起点即可。不过要注意的一点是题目说的是原数字不能有前导零，但是分割的数字是可以有前导零的。 参考最后一个样例：

即可以分为1,1,0,4或1,1,04。所以没必要特判0能不能作为起点。

HDOJ2266-How Many Equations Can You Find：和上题类似，递归标记分隔变成加减号而已。同样分隔的数字可以有前导零，没必要特判。

HDOJ2952-Counting Sheep：这题应该出在前面，简单的连通块，相信如果刷完前面的题，那本道用dfs或bfs写都不会超过5分钟，有木有感觉进步很大（笑）。

HDOJ4403-A very hard Aoshu problem：比之前题稍难，思路就是枚举等号位置然后分别对两边进行搜索。本题的预处理很巧妙：

这么判断是是错的，这样n为负值还会继续遍历下去导致回溯无法结束。应该在dfs（cur+1）后继续返回。还是不懂的话请参考：HDOJ1627-Krypton Factor。

HDOJ2553-N皇后问题：著名回溯算法八皇后问题。网上讲解很多不赘述。

HDOJ4228-Flooring Tiles：本题转换问题思路很巧，拼出m种不同矩形所需方块n满足n有2* m或者2* m-1个约数即可。但题解最后好像写错了。求出最小反素数n，使约数个数为2* m或者2* m-1。本题剪枝操作也很绝，各种剪枝卡时间。

HDOJ4499-Cannon：八皇后问题变体。唯一不同是判断当前的棋子是否合法的判断条件变了。如果你理解八皇后问题那本题也不难。

HDOJ4536-XCOM Enemy Unknown：原理不难，就是题目要求很琐碎。单纯每次搜索帮助哪个国家，但是对其他国家影响和恢复现场比较麻烦，模拟题刷多了应该不会怯场。

HDOJ4770-Lights Against Dudely：和上题类似，仍是暴搜模拟题。

HDOJ5004-KAMI：还是模拟题，功力浅薄，写不下去。

HDOJ5355-Cake：解法意想不到，算是数学题了吧。可以参考：hdu5355 思维+爆搜。

HDOJ5723-Abandoned country：问题转化太巧妙了，第一问求最小花费显然时最小生成树，而第二问求最大预期，期望值=任意两点路径之和/路径总数。而路径总数是定值 = n ∗ ( n − 1 ) / 2 =n*(n-1)/2 =n∗(n−1)/2，而任意两边边权不一样，最小生成树是唯一的，期望值唯一，求边的总和不从点考虑，而从边考虑，因为树不存在环，所以一条边左边点到右边点必然经过此边，对于每条边的总和，就是左边点数乘右边点数乘边权。问题变成递归求叶子节点个数。

HDOJ5887-Herbs Gathering：01背包，递归写法。先贪心排序然后各种剪枝。没有更好的思路这里不做评价。

本章作为了解基础图论算法题已经足够。由于本人能力有限，本章给不出更好思路，具体参考书中解析。

HDOJ2962-Trucking：队列优化的Bellman-Ford，二分高度每次计算。虽然此算法经常被卡，但非图论选手了解已经够了。

HDOJ3018-Ant Trip：欧拉回路是可以一笔画完的，用查并集维护这个回路的连通图即可。

ZJU1060-Sorting It All Out：拓扑排序算法，难写。

ZJU1186-Street Directions：将图中的所有桥拆为两条反向的单向边，Tarjan算法求强联通分量。

ZJU1197-Sorting Slides：二分图匹配求关键边。模板题，书上用的prim算法，网上博客很多，不提。

ZJU1203-Swordfish：最小生成树算法，kruskal稀疏图，prim稠密图。

ZJU1221-Risk：Floyd打表，没啥好说的，之前第六章就写过。

ZJU1232-Adventure of Super Mario：遇到类似题型好多了，最短路加一个可以跳过的操作，更像是一个DP题。

ZJU1542-Network：还是最小生成树。。。

ZJU1935-XYZZY：由于有负权边，所以用SPFA求最短路。

ZJU2797-106 miles to Chicago：还是最短路算法，只不过路径权值不再是加而是乘。

Efficient Codes：不会，不留坑。

ZJU3010-The Lamp Game：不留坑+1。

不做评价。

博主只了解简单的组合排列算法，只看了刘汝佳紫书第10章数学概念初步，能力不足，不做说明。

2021.6.6记 本书除3,11,12章外可以短期内作为新手入门学习试题（请无视博主8个月才更完 ）。博主从新手时期也是刷着本书一路走来，从开始的递归写几小时还一直wa，到现在有了思路基本一遍ac；从当初写代码不知道从何下手，到如今能清晰冷静分析思路实现。 虽然因为实验课设等等原因拖了很久学完，但现在也勉勉强强算入门了。不过由于个人原因刚入门就得说再见了。尽管最后什么荣誉也没得到，但我并不后悔这份没有结果的努力。