ACM培训计划与相关书籍_acm培训书籍

ACM培训计划与相关书籍

书籍

入门三本

《数据结构与算法》（傅清祥，王晓东编著，我所见过的最好的算法教材）

程序设计导引及在线实践  作者: 李文新

ACM程序设计培训教程 吴昊

 

 

基础提高

算法艺术与信息学竞赛第二版 刘汝佳

算法设计与分析  王晓东

算法设计与试验题解王晓东

科曼：《算法导论》

组合数学第三版 冯舜玺 译

计算几何－算法设计与分析周培德

国际信息学奥林匹克竞赛指导——实用算法的分析与程序设计　吴文虎 王建德

网络算法与复杂性理论  谢政 李建平

《Concrete Mathematics --- A Foundation For Computer Science》 Ronald L. Graham ， Donald E. Knuth ， Oren Patashnik《具体数学》（能买到中文版最好）

《计算机程序设计艺术》三卷  Knuth

组合数学的算法与程序设计

《程序设计中的组合数学》吴文虎

图论的算法与程序设计

图、网络与算法

国际大学生程序设计竞赛辅导教程 郭嵩山 崔昊

《ACM国际大学生程序设计竞赛试题与解析》全部册（吴文虎著，清华大学出版社）

C算法．第1卷，基础、数据结构、排序和搜索（第三版）

C算法(第2卷图算法第3版中文版)译者:周良忠 (美国)塞奇威克著 

国际大学生程序设计竞赛例题解四本  郭嵩山

 

 

训练计划

http://acm.ecust.edu.cn/training/articles/

 

先做几组难度最低的题，这些题都来自浙大(ZJU)、北大（PKU)和同济(TOJ)的网站。

 

有些题的解法几乎一眼可以看出，但对C,C++基本语句的熟悉还是很有好处的。练习这些题还有以下目的：

 

1. 了解竞赛题的形式

 

2. 熟悉如何在训练系统中提交做对的题目

 

      请所有的新队员认真完成以下各题。如果做题遇到困难，如题意难以理解、不知如何着手或不知错在哪里，不要气馁，可以请教别的队员，也可请教教练。我们会尽力帮助你完成这几组中每一道题。但不要复制别人的程序，即便参考了别人的程序，也要亲自再完成一遍。而且不建议过多参考别人程序，这样会消弱训练的效果，也减少了思考的乐趣。

 

      有些队员可能觉得某些题太简单，但我们还是建议将它们都做掉。因为题目虽然简单，但是再简单的题目都不能保证一次做对，而做错题的各种原因如题意理解错误，格式错误等你都会碰到。了解这些原因对减少错误率很有好处。

 

做题前请了解一些规范：

 

1.  main函数应为int型，最后return 0 ，即：

 

int main()

 

{

 

...

 

   return 0;

 

}

 

这样做是因为避免有些编译器报错。

 

2. 为了便于核对，请在代码开头加上可以表明题目的注释，如：

 

    //ZJU1001; /*PKU1002 */等

 

 

 

Group 0:热身

 

再次提醒：做对后别忘提交到训练系统.

编号    来源    题号    标题    评注

 

 

    三道都是A+B，而且有样例程序。请自己做一遍，不要拷。

0.1     ZJU     1001    A+B Problem

0.2     PKU     1000    A+B Problem

0.3     TOJ     1000    熟悉一下OnlineJudge的环境

 

Group 1:起步

 

    以下是一些TOJ上的题目，作为起步练习很不错。题目是中文的，但其它形式和比赛题型一样。要注意输出格式。有些题目对格式交待不是很清楚，但这并不是说你可以随意增加空格和空行。遇到这种情况，根据样例输出自行判断。一般行尾没有多余空格。

编号    来源    题号    标题    评注

1.1     TOJ     1001    排版题.输出排列成菱形的字母      

1.2     TOJ     1003    排版题.输出三角形的字符      

1.3     TOJ     1006    敲七     

1.4     TOJ     1007    Step.如何得到输入数据的结束

     

1.5     TOJ     1008    扬辉三角

     

1.6     TOJ     1009    蛇行矩阵   

 

可以直接在2维数组中填数.

 

(直接推出每个位置数字的公式和递推公式也可以，但效果并不比前一种方法更有效，而且难度较大）

1.7     TOJ     1015    行编辑器    简单的字符串处理

1.8     TOJ     1019    输入三个自然数  

 

Group 2:英文题（1）

 

     以下是ZJU上的题目，ZJU的题都是英文的，有些题难度可能不比上面一组高。但对新队员来说，理解题意本身可能是个难点。 

编号    来源    题号    标题    评注

2.1     ZJU     1048    Financial Management

    只比A+B难一点

2.2     ZJU     1045    HangOver    这一道和下面两道都是简单的计算

2.3     ZJU     1049    I Think I need Iboat    

2.4     ZJU     1813    Biker's TripOdometer    

2.5     ZJU     1057    Undercut     

2.6     ZJU     1113    u Calculate e   没有输入，但要注意格式

2.7     ZJU     1151    Word Reversal   简单的字符串处理

2.8     ZJU     1195    Blowing Fuses   别看题有些长，但其实很简单

2.9     ZJU     1755    Clay Bully  

2.10    ZJU     1760    Doubles      

 

Group 3:英文题（2）

 

    下面这些题可能稍微难一些，但与上面一组难度上并没有本质区别。只要仔细想想，应当不难做出。

编号    来源    题号    标题    评注

3.1     ZJU     1489    2^x mod n = 1    

3.2     ZJU     1712    Skew Binary      

3.3     ZJU     1016    Parencodings     

3.4     ZJU     1350    The Drunk Jailer     

3.5     ZJU     1051    A New GrowthIndustry   这三题可能比较繁琐，做的时候要仔细

3.6     ZJU     1178    Booklet PrintingBook

3.7     ZJU     1078    Palindrom Numbers

 

Group 4:TOJ前20题中剩余题

 

    TOJ前20题都是基础题，在第一组练习中已经做了一部分，剩下的这一部分难度肯定比第一组大，但与上一组难度差不多。有几道题涉及更知识，在这依旧被剔除，留着以后做。

编号    来源    题号    标题    评注

4.1     TOJ     1005    母牛生小牛 类似Fibonacci数列，但有区别

4.2     TOJ     1012    约瑟夫问题  

4.3     TOJ     1013    去尾问题     

4.4     TOJ     1014    阶乘结果末尾有多少零？ 这两题涉及到一些数学推导，可能难度较大

4.5     TOJ     1016    请求N！左边第二位的数字

4.6     TOJ     1018    编制一个乘法运算的程序

     

4.7     TOJ     1020    字符串编辑

 

 

 

 

Group 5:基础题继续练习

 

再补充一些适于基本功练习的题目，供大家继续打好C(C++)与语言基础。

 

有些题目需要一些数学推算，但都不会超出你们的知识范围。

编号    来源    题号    标题    评注

5.1     ZJU     1763    A Simple Question ofChemistry 极简单

5.2     ZJU     1915    Above Average

    极简单

5.3     ZJU     2104    Let the Balloon Rise   极简单

5.4     ZJU     2201    No Brainer 极简单

5.5     ZJU     2208    To and Fro 极简单，只要读懂题

5.6     ZJU     1797    Least CommonMultiple

    想一想如何有效率地求最大公约数和最小公倍数

5.7     ZJU     1629    Counting Triangles  

5.8     ZJU     2015    Number Sequence     注意数列的周期性

5.9     ZJU     1657    Goldbach'sConjecture    

5.10    ZJU     1871    Steps    

5.11    ZJU     1858    Soundex    

5.12    ZJU     1622    Switch  

5.13    ZJU     1160    Biorhythms  

5.14    TOJ     1022    数制转换    要注意如何读入数据

5.15    TOJ     1010    数素数

    注意质数判定的效率

 

Group 6 高精度运算练习

 

高精度运算也是基本功之一。

 

以下各题都牵涉到高精度运算,许多涉及数制转换。但也需注意其它方面。

 

做题时注意模块化。做完这些题后，你会发现很多功能可以重用。

6.1     ZJU     1272    Numerically Speaking   有样例程序

6.2     ZJU     1292    Integer Inquiry     高精度加法

6.3     ZJU     1205    Martian Addition

    高精度加法，但不是十进制

6.4     ZJU     1073    Round and Round WeGo   高精度乘法

6.5     ZJU     1086    Octal Fractions     高精和数制转换

6.6     ZJU     1154    Niven Numbers

    高精和数制转换，注意，长度题目中未明确给定。如果设固定长数组，先设50.如果运行时溢出再往上加。

6.7     ZJU     1210    Reciprocals     高精度除法，同时注意输出格式要求

6.8     ZJU     1962    How Many Fibs?

    高精度加法,以及比较

6.9     ZJU     2017    Simple Arithmetics 涉高精加，减，乘，且格式处理较繁

6.10    ZJU     2241    Fractran    表示一个大数不仅可以用各位数，也可以用它的各因子。这题就是一例。

                 

 

 

 

Group 6: 模拟类题目专项练习（下）

 

所谓模拟类题目，就是那些题目详细描述了完成某一过程的步骤，你只须严格按照要求模拟这一过程即可。

 

这类题目通常不需要很复杂的算法设计，但有些题十分繁琐，稍不小心就会出错。另外，对题意的准确把握也是关键，特别是这些步骤的细节方面，一定要完全搞清楚，不能自己乱猜。

 

下面的一些模拟类题目都是比较繁琐的，大家做它们时一定要细心，且有足够的耐心。

 

 

编号    来源    题号    标题    评注

6.1     ZJU     1072    MicroprocessorSimulation    

6.2     ZJU     1208    Roll the Die!    

6.3     ZJU     1710    The Snail    

6.4     ZJU     1723    Board Silly      

6.5     ZJU     1737    Unreliable Message

     

6.6     ZJU     1824    Maze Traversal  

6.7     ZJU     1834    AutoFish

     

6.8     ZJU     1862    Mine Sweeper

     

6.9     ZJU     2240   

 

Run Length Encoding

     

 

 

 

Group 7: 新一组练习

 

这一组题目较综合，难度不一。(题目下载）

编号    来源    题号    标题    评注

7.1     ZJU     1068

    P,MTHBGWB    

7.2     ZJU     1146

    LC-Display  

7.3     ZJU     1243

    URLs

     

7.4     ZJU     1115

    Digital Roots    

7.5     ZJU     1180

    Self Numbers     

7.6     ZJU     1337

    Pi  

7.7     ZJU     1312

    Prime Cuts

     

7.8     ZJU     1326

    M*A*S*H

    建议用链表做

7.9     ZJU     1494

    Climbing Worm    

7.10    ZJU     1577

    GCD & LCM    

7.11    ZJU     2122    A Flea on aChessboard

     

7.12    ZJU     1628

    Diamond      

7.13    ZJU     1630

    Die      

7.14    ZJU     1517

    Grandpa's Rubik Cube

     

7.15    ZJU     1161    Gone Fishing    （新加）贪心经典，可以后再做

                 

 

Group 8: 字符串处理

 

 

编号    来源    题号    标题    评注

8.1     ZJU     1099

    HTML     

8.2     ZJU     1318

    Table   样例数据

8.3     ZJU     1116    A Well-FormedProblem    

8.4     ZJU     1324    Unix ls     用C语言的用scanf读数据

8.5     ZJU     1295    Reverse Text     

8.6     ZJU     1392    The Hardest ProblemEver     

8.7     ZJU     1325    Palindromes      

8.8     ZJU     1404    Oil Pipeline     

8.9     ZJU     1884    WERTYU  

                 

 

 

 

 

Group 9:

 

 

编号    来源    题号    标题    评注

9.1     ZJU     2388    Beat the Spread!     

9.2     ZJU     2376    Ants    努力得猜吧

9.3     ZJU     2358    Sum of Factorials   注意0的阶乘

9.4     ZJU     2345    Gold Coins  

9.5     ZJU     2321    Filling Out the Team    

9.6     ZJU     2397    Tian Ji -- The HorseRacing     经典贪心

9.7     ZJU     2316    MatrixMultiplication   线性代数，加组合数学

9.8     ZJU     2301    Color the Ball 离散化坐标

9.9     ZJU     2330    A^B == B^A?     高数题

9.10    ZJU     2329    AB Circle    

9.11    ZJU     2313    Chinese Girls'Amusement     

                 

                 

                 

 

 

Group 10:

 

 

 

编号    来源    题号    标题    评注

10.1    ZJU     2417    Lowest Bit  

10.2    ZJU     2405    SpecializedFour-Digit Numbers  

10.3    ZJU     2481    Unique AscendingArray  

10.4    ZJU     2478    Encoding     

10.5    ZJU     2421    Recaman's Sequence  

10.6    ZJU     2416    Open the Lock

     

10.7    ZJU     2482    IP Address  

10.8    ZJU     2401    Zipper  

10.9    ZJU     2480    Simplest Task inWindows     

10.10   ZJU     2478    Total Amount     

 

10.11   ZJU     2256    Mincost     贪心

10.12   ZJU     2258    Number Sequence II 构造

                 

                 

 

 

 

     

 

 

 

 

 

 

Group 11: 搜索初步

 

深度优先搜索和广度优先搜索是属于常用的搜索技术。前者用到递归，后者涉及队列。

 

深度优先搜索对于解决某些问题并不一定是最好的，但很容易实现，有时也十分有效，它的难点在于如何剪枝优化。出现在递归初步中的题目可以算是深搜的一种。

 

广度优先搜索技术的结构相对固定，但节点的判重也是个难点。由于时间效率的原因，广度优先搜索运用得更为广泛。

 

下面是关于它们的一些练习。

编号    来源    题号    标题     

11.0    ZJU     2416    Open the Lock

    广度优先。（样例程序）

11.1    ZJU     1091    Knight Moves    最简单的广度优先搜索问题，但包括了这类方法的所有要素。

11.2    ZJU     1005    Jugs    典型的广度优先

11.3    ZJU     1649    Rescue 广度优先在迷宫问题中的应用

11.4    ZJU     1002    Fire Net    这些都是可以运用深度优先的题目。有些需要很好的剪枝。

11.5    ZJU     1003    Crashing Balloon

11.6    ZJU     1004    Anagrams by Stack

 

 

 

 

 

Group 12: 深度优先搜索

 

下面是关于深度优先搜索（DFS）的一些练习。

编号    来源    题号    标题     

12.0    PKU     1256    Anagram

    生成不重复排列

12.1    ZJU     1711    Sum It Up   生成不重复组合

12.2    ZJU     2412    Farm Irrigation     初步,有的需要剪枝

12.3    ZJU     1694    Shredding Company

12.4    ZJU     1457    Prime Ring Problem

12.5    ZJU     1204    Additive equations

12.6    ZJU     2192    T-shirt Gumbo   进阶,有序搜索与剪枝

12.7    ZJU     1909    Square

12.8    ZJU     1987    Vase Collection

12.9    ZJU     1937    Addition Chains

12.10   ZJU     1984    Genetic Code

12.11   ZJU     2110    Tempter of the Bone

12.12   ZJU     1179    Finding Rectangles 难题,需要很好搜索策略和剪枝技巧

12.13   ZJU     1411    Anniversary

12.14   ZJU     1008    Gnome Tetravex

12.15   ZJU     1499    Increasing Sequences

 

Group 13: 广度优先搜索

 

下面是关于广度优先搜索（BFS）的一些练习。

编号    来源    题号    标题     

13.0    ZJU     1438    Asteroids! 三维迷宫，想想如何控制方向

13.1    ZJU     2050    Flip Game   可以尝试一下位运算

13.2    ZJU     2081    Mission Impossible 可以用BFS+DFS

13.3    ZJU     1310    Robot   进阶,稍难一点

13.4    ZJU     1671    Walking Ant

13.5    ZJU     1940   

 

Dungeon Master

13.6    ZJU     1103    Hike on a Graph

13.7    ZJU     1358    Moving ObjectRecognition

13.8    ZJU     1217    Eight   难题,注意状态的表示与哈希

13.9    ZJU     1227    Free Candies

13.10   ZJU     1505    Solitaire

13.11   ZJU     1361    Holedox Moving

 

 

 

Group 14: 图--遍历(GraphTraversal)、传递闭包（Transitive Closure）

 

 

编号    来源    题号    标题     

14.0    ZJU     1221    Risk    用BFS也可以解决最短路径问题

14.1    ZJU     2165    Red and Black   基于网格的连通性分析

14.2    ZJU     1589    Professor John 传递闭包，也可以用DFS

14.3    ZJU     1085    Alien Security  

                 

 

Group 15: 图--拓扑排序（TopologicalSort）、关节点（Articulation Point）

 

 

编号    来源    题号    标题     

15.0    ZJU     1060    Sorting It All Out  

15.1    ZJU     1119    SPF      

15.2    ZJU     1311    Network      

                 

 

Group 16: 图--最小生成树（MinimumSpanning Tree）

 

 

编号    来源    题号    标题     

16.0    ZJU     1406    Jungle Roads     

16.1    ZJU     1203    Swordfish    

16.2    ZJU     1542    Network      

16.3    ZJU     1586    QS Network 要注意节点权值

16.4    ZJU     1372    Networking 要注意重复边

16.5    ZJU     1914    Arctic Network 想想为什么可以用最小生成树?

16.6    ZJU     2158    Truck History   想想如何转化为最小生成树?

16.7    ZJU     2048    High Ways   基于连通分量的最小生成树

16.8    ZJU     1718    Building a SpaceStation     

16.9    PKU     1258    Agri-Net     

                 

 

Group 17: 图--最短路径（ShortestPath）

 

 

编号    来源    题号    标题     

17.0    ZJU     1053    FDNY to the Rescue!      

17.1    ZJU     1609    Equivalence      

17.2    ZJU     1082    StockbrokerGrapevine    

17.3    ZJU     1655    Transport Goods     边权值有些特别

17.4    ZJU     1092    Arbitrage    

17.5    ZJU     1967    Fiber Network   想想如何利用Floyd三重循环?

17.6    ZJU     1456    Minimum TransportCost 有些难度的最短路径题

17.7    ZJU     2008    Invitation Cards    带最小堆的Dijkstra

17.8    ZJU     1765    Which Way Do I Go? 综合题，比较复杂

17.9    ZJU     1232    Adventure of SuperMario     

 

 

 

Group 18: 图--回路问题（EulerPath & Hamilton Tour）

 

 

编号    来源    题号    标题     

18.0    ZJU     1105    FatMouse's Tour      

18.1    ZJU     2016    Play on Words   可转化为判定欧拉路的存在性

18.2    ZJU     1130    Ouroboros Snake     可以转化为欧拉路

18.3    SCU     1286    First Love 可以转化为欧拉路

                 

 

Group 19: 图--二部图匹配（BipartiteMatching）

 

 

编号    来源    题号    标题     

19.0    ZJU     1140    Courses      

19.1    ZJU     1137    Girls and Boys  

19.2    ZJU     1157    A Plug for UNIX      

19.3    ZJU     1364    Machine Schedule     

19.4    ZJU     1197    Sorting Slides  

19.5    ZJU     1525    Air Raid     

19.6    ZJU     1059    What's In a Name     

19.7    ZJU     1516    Uncle Tom'sInherited Land  

19.8    ZJU     1654    Place the Robots     

19.9    ZJU     1509    Family  

                 

 

Group 20: 图--网络流（NetworkFlow）

 

 

编号    来源    题号    标题     

20.0    PKU     1273    Drainage Ditches    典型的网络最大流问题

20.1    ZJU     1734    Power Network   可转化为网络最大流问题

                 

 

Group 21: 图--差分约束（DifferenceConstraints）

 

 

编号    来源    题号    标题     

21.0    ZJU     1260    King     

21.1    ZJU     1420    Cashier Employment  

21.2    ZJU     1455    Schedule Problem     

21.3    ZJU     1508    Intervals    

                 

 

Group 22: 图--其它

 

 

编号    来源    题号    标题     

22.0    ZJU     1015    Fishing Net     弦图判定

22.1    ZJU     1492    Maximum Clique

 

求最大团，经典NP hard

22.2    ZJU     1576    Marriage is Stable 稳定婚姻，延迟认可算法