一些ACM资料

一些ACM资料,开始准备~~

1 关于ACM图书

数据结构

数据结构:C语言版

【题名】
数据结构:C语言版

【作者】
严蔚敏,吴伟民编著

【关键词】
数据结构 TP311.12

【SS号】
10204299

【目录】
数据结构:C语言版/严蔚敏,吴伟民编著.–北京:清华大 学出版社,1997.4.–334页;26CM.–7-302-02368-9:RMB 22

经典的入门书籍,我就多说了。即使大家不会PASCAL,这本书也很值得一看。推荐给初学的朋友阅读

正在看的一本书,呵呵

数据结构题集:C语言版

【题名】
数据结构题集:C语言版

【作者】
严蔚敏,吴伟民编著

【关键词】
数据结构 高等学校 习题 TP311.12-44

【SS号】
10204322

【目录】
数据结构题集:C语言版/严蔚敏,吴伟民编著.–北京:清 华大学出版社,1999.–234页;26CM.–7-302-03314-5:R MB16

上面一本书的配套练习。

数据结构技术

【题名】
数据结构技术

【作者】
王本颜,方蕴昌编著

【关键词】
数据结构 TP31

【SS号】
10170100

【目录】
数据结构技术/王本颜,方蕴昌编著.–北京:清华大学出 版社,1988.4.–410页;26CM

这本书的内容比较丰富,适合有一定基础的朋友阅读(建议写读上面两本书)。

算法分析与设计
计算机算法导引

【题名】
计算机算法导引

【作者】
卢开澄等编著

【关键词】
电子计算机 计算方法 TP301.6

【SS号】
10011118

【目录】
计算机算法导引/卢开澄等编著.–2版.–北京:清华大学 出版社,1996.11.–321页;26CM.–本书是在"组合数学C 算法与分析"下册的基础改写的.–7-302-02277-1:RMB21

这本书内容比较丰富,虽然有的章节和竞赛关系不大(例如FFT),但是比较适合初学者阅读。

计算机算法基础

【题名】
计算机算法基础

【作者】
邹海明,余祥宣[著]

【关键词】
电子计算机 算法理论 TP301.6

【SS号】
10205417

【目录】
计算机算法基础/邹海明,余祥宣[著].–武汉:华中理工 大学出版社,1985.–257页;26CM.–7-5609-0552-8:RMB 16.80

虽然比较难懂,但内容却很不错,有它的过人之处 推荐给有一定基础的朋友阅读。 
相关理论:组合数学,图论,计算几何

组合数学引论

【题名】
组合数学引论

【作者】
孙淑玲,许胤龙编著

【关键词】
组合数学 概论 O157

【SS号】
10188793

【目录】
组合数学引论/孙淑玲,许胤龙编著.–合肥:中国科技大 学出版社,1999.2.–330页:图;20CM.–7-312-01035-0 :RMB11

很不错的书,内容丰富,而且实用,推荐给所有朋友阅读,不过初学的朋友看起来可能会吃力一点。

图论及其应用

【题名】
图论及其应用

【作者】
卢开澄,卢华明著

【关键词】
图论 O157.5

【SS号】
10011055

【目录】
图论及其应用/卢开澄,卢华明著.–2版.–北京:清华大 学社出版社,1995.–223页;26CM.–7-302-01817-0:RMB 10

入门时阅读的书,很实用!它的语言比较通俗,推荐给初学的朋友阅读,但同时涉及到的东西相当多,因此也推荐给有一定基础的朋友。

网络算法与复杂性理论

【题名】
网络算法与复杂性理论

【作者】
谢政,李建平[著]

【关键词】
图论算法 复杂性理论 研究生 教材 O157.5

【SS号】
10188825

【目录】
网络算法与复杂性理论/谢政,李建平[著].–长沙:国防 科技大学出版社,1995.5.–368页:图表;20CM.–李建平 (1965~ ),国防科技大学应用数学系讲师,硕士.–7-8102 4-330-6:RMB15

本书内容很丰富,结构和语言比较正式,推荐给有一定基础且对图论有兴趣的朋友阅读。里面不少内容超出了竞赛范围,不过很多方法倒是很有启发性的。例如第二最短路问题。在我读这本书的时候,竞赛从未考过,但是上次的USACO US OPEN就出了一道求前k最短路的题目。

计算几何:算法分析与设计

【题名】
计算几何:算法分析与设计

【作者】
周培德著

【关键词】
算法分析 电子计算机 算法设计 TP301.6

【SS号】
10192623

【目录】
计算几何:算法分析与设计/周培德著.–北京:清华大学出 版社,2000.3.–14,286页;26CM.–(中国计算机学会学术 著作丛书).–7-302-03801-5:RMB29

我找到的唯一的计算几何书籍,但是质量极高,强烈推荐!不过要读懂却并不容易,所以只推荐给有一定基础的朋友阅读。

数学建模
数学建模的理论与实践

【题名】
数学建模的理论与实践

【作者】
吴翊等编著

【关键词】
数学模型 O141.4

【SS号】
10188817

【目录】
数学建模的理论与实践/吴翊等编著.–长沙:国防科技大 学出版社,1999.–370页;20CM.–7-81024-571-6:RMB17

大家对数学建模可能不大熟悉,所以虽然这本书不是很难,但是这里只推荐给有一定组合数学和图论基础的朋友阅读。

数学建模的理论与实践

【题名】
数学模型基础

【作者】
王树禾编著

【关键词】
数学 模型论 O141.4

【SS号】
10188784

【目录】
数学模型基础/王树禾编著.–合肥:中国科学技术大学出 版社,1996.5.–315页;20CM.–7-312-00746-5:RMB8

本书的组织方式比较合理,大家读起来可能会比较轻松,不过仍是推荐给有一定理论基础的朋友阅读。

竞赛专门书籍
实用算法的分析与程序设计

【题名】
实用算法的分析与程序设计

【作者】
吴文虎,王建德编著

【关键词】
电子计算机 竞赛 中学 教学参考资料 G634.67

【SS号】
10205419

【目录】
实用算法的分析与程序设计/吴文虎,王建德编著.–北京 :电子工业出版社,1998.1.–349页:图;26CM.–国际信 息学奥林匹克竞赛指导.–7-5053-4402-1:RMB28

  这个需要我介绍吗?必读书籍,但是很多朋友都没买到。现在有电子版了,还不快看看:)

ACM国际大学生程序设计竞赛试题与解析(一)

【题名】
ACM国际大学生程序设计竞赛试题与解析(一)

【作者】
吴文虎

【SS号】
10110104

【目录】
ACM国际大学生程序设计竞赛试题与解析(一)/吴文虎.—:清华大学出版社,1998.12.—159页;CM.–RMB

ACM总决赛91-93年的题解。强烈推荐!!

国际大学生程序设计竞赛试题解析

【题名】
国际大学生程序设计竞赛试题解析

【作者】
王建德,柴晓路编著

【关键词】
程序设计 竞赛题 高等学校 TP31-44

【SS号】
10204658

【目录】
国际大学生程序设计竞赛试题解析/王建德,柴晓路编著. –上海:复旦大学出版社,1999.–285页;26CM.–7-309 -02141-X:RMB25

ACM总决赛96-98年的题解。强烈推荐!!

1993-1996美国计算机程序设计竞赛试题与解析

【题名】
1993-1996美国计算机程序设计竞赛试题与解析

【作者】
吴文虎

【SS号】
10206232

【目录】
1993-1996美国计算机程序设计竞赛试题与解析/吴文虎.—:清华大学出版社,1999.1.—138页;CM.–RMB

有趣的USACO题目+简明的解答,学习不久但很想见见竞赛题的朋友必读!

国际、国内青少年信息学(暨计算机)竞赛试题解析

【题名】
国际、国内青少年信息学(暨计算机)竞赛试题解析

【作者】
吴文虎,王建德编著

【关键词】
电子计算机 竞赛题 解题 中学 G634.67

【SS号】
10010595

【目录】
国际、国内青少年信息学(暨计算机)竞赛试题解析/吴文虎 ,王建德编著.–北京:电子工业出版社,1994.6.–190页 ;26CM.–吴文虎,中国计算机学会普及委员会主任,国际信 息学奥林匹克中国队总教练,北京计算机奥林匹克学校校长 ,清华大学计算机科学与技术系教授.–7-5053-2392-X:RM B14

NOI92-93,IOI92-93,CTSC92-93题目与解析,虽然题目比较老,但是很有启发性!推荐给有一定基础的饿朋友阅读。

关于ACM

ACM国际大学生程序设计大赛介绍

一、ACM竞赛介绍及规则
    ACM/ICPC(国际大学生程序设计竞赛)是由ACM(Association for Computing Machinery,美国计算机协会)组织的年度性竞赛,始于1970年,是全球大学生计算机程序能力竞赛活动中最有影响的一项赛事。ACM/ICPC采用赛区选拔的方式产生参加世界决赛学校的资格,2001年,来自全球超过25个地区1141所大学的2362支队伍参加了第26届ACM/ICPC的赛区竞赛。在2002年3月,来自世界各地的约60支队伍,200多名选手参加了夏威夷总决赛的角逐。可以说,ACM国际大学生程序设计竞赛是参赛选手展示计算机才华的广阔舞台,是著名大学计算机教育成果的直接体现,是信息企业与世界顶尖计算机人才对话的最好机会。在过去十几年中,世界著名信息企业APPLE、AT&T、MICROSOFT和IBM分别担任了竞赛的赞助商。中国大陆高校从1996年开始参加ACM/ICPC亚洲预赛,前五届ACM/ICPC亚洲区选拔赛在上海设有赛区,由上海大学主办。2002年,第六届ACM/ICPC亚洲预赛将该在北京设赛区,由清华大学主办。本次竞赛将于2002年10月在清华园拉开帷幕,预计将有超过60所国内外著名大学的上百支队伍参加本次竞赛(这也是北京工业大学首次参加此项赛事)。
    ACM竞赛规定,教练是参赛队伍所代表学校的正式教师,每支队伍最多由三名参赛队员组成,每支队伍中至少有两名参赛队员必须是未取得学士学位或同等学历的学生,取得学士学位超过两年,或进行研究生学习超过两年的学生不符合参赛队员的资格,任何参加过两次决赛的学生不得参加地区预赛或者世界决赛。
竞赛中至少命题6题,至多命题10题,比赛时间为5个小时,参赛队员可以携带诸如书、手册、程序清单等参考资料,试题的解答提交裁判称为运行,每一次运行会被判为正确或者错误,判决结果会及时通知参赛队伍,正确解答中等数量及中等数量以上试题的队伍会根据解题数目进行排名,解题数在中等数量以下的队伍会得到确认但不会进行排名,在决定获奖和参加世界决赛的队伍时,如果多支队伍解题数量相同,则根据总用时加上惩罚时间进行排名,总用时和惩罚时间由每道解答正确的试题的用时加上惩罚时间而成。每道试题用时将从竞赛开始到试题解答被判定为正确为止,期间每一次错误的运行将被加罚20分钟时间,未正确解答的试题不记时,地区预赛可以使用的语言包括C/C++和Java,每支队伍使用一台计算机,所有队伍使用计算机的规格配置完全相同。(竞赛具体的软件环境可能根据赞助商的变化而变)

二、关于竞赛的题型分析
    Hal Burch通过在1999年春季的分析得出了这样的结论,竞赛的程序设计一般只有16种类型,它们分别是:
Dynamic Programming (动态规划)
Greedy (贪心算法)
Complete Search (穷举搜索)
Flood Fill (不知该如何翻译)
Shortest Path (最短路径)
Recursive Search Techniques (回溯搜索技术)
Minimum Spanning Tree (最小生成树)
Knapsack (背包问题)
Computational Geometry (计算几何学)
Network Flow (网络流)
Eulerian Path (欧拉回路)
Two-Dimensional Convex Hull (不知如何翻译)
BigNums (大数问题)
Heuristic Search (启发式搜索)
Approximate Search (近似搜索)
Ad Hoc Problems (杂题)
很少有人能真正掌握这其中绝大部分的方法,而对于一些包含了这些方法组合与循环的具有挑战性的综合问题,多数选手都无能为力,因为竞赛中的很多试题都需要选手当场作出分析,而不是套用固定的解题格式,这是竞赛的困难所在,也是它的魅力所在。

三、竞赛准备
    ACM竞赛不要求使用某一种特定的语言,所以各个队伍可以根据语言的特点和自己的特长选择,如果对语言的原理语法和特点均能做到成竹于胸、滥熟于心,在比赛的过程中就可以大大缩短调试的时间,从而获得优势。
    然而编程之道就如武学之道,语言只是各门各派的武功招式,算法和数据结构则好比内功心法和武学原理。内力深厚,任何招式到了手上都能够化腐朽为神奇;掌握了武学原理,更能做到无招胜有招。选手在竞赛中最重要的素质,正体现于对算法和数据结构的掌握和理解上,通过对经典问题的分析,掌握各种算法的应用范围和数据结构的作用与具体实现,是每个选手在平时学习中的重点所在。

四、竞赛策略
    临近比赛,在实力上已经难有质的提高,这时我们不妨将注意力转移到竞赛技巧方面,做不成武学道师也学个韦小宝。在ACM竞赛中,一般来说能成功解决半数或以上题目的队伍已经是相当优秀的,解决所有问题近乎天方夜潭,也就是说无论你的实力如何,都还有很大的改进余地,这其中比较重要的就是竞赛的策略。
(1)分工的问题:
    团队的配合十分重要,三个队员之间的合理分工可以大大改进解题的效率,根据队员的不同特点,不同的队伍可以采用不同的分配方式,其间一些细节的处理需要三个人有很好的默契。
(2)算法的选择:
    在所有可行的算法当中,我们选择的应该是最可行的方法,而不是最高明的方法,这是竞赛与解决问题的一个重要区别,按照熟悉的程度由高到低选择一个算法,通过计算算法的时间和空间复杂度(在必要的情况下)和特殊的测试数据找出一切使该算法不成立的理由,如果找不到就确定该算法并选用相应的数据结构。在确定思路的时候注意比较常见的思维方式分析,比如逆向的分析,对称的分析等等。
(3)程序的编写:
    最好首先编写输入和输出的部分,然后逐步细化,一个部分一个部分地填充调试,其间通过适量的注释来刻画程序的逻辑结构和特殊的技巧。在完成全部代码后用一般的测试数据验证代码的正确性,然后处理特殊的情况和边界问题,试图尽可能地找出错误的情况并加以改正。关于程序的优化主要考虑的是最坏情况下所用的时间是否满足要求,优化的程度以题目要求为准,足够即可,尽量避免使用指针和动态分配,在空间允许的情况下一律采用静态分配。
(4)调试中的问题:
    调试中会遇到的许多问题需要在事前有所准备并定出总体设计,当然具体的情况还要临场分析,考虑的方面包括程序中的BUG,算法的正确性和数据结构的合理性,什么时候该放弃这个问题,什么时候该返回到先前放弃的问题,是否需要做到或已经做到足够的优化等等。所有关于调试的输入输出都不要删除,将它们注释起来即可。
(5)竞赛中的杂题处理
    在竞赛中有时会出现一些新颖的题型,解决它们的算法很难归到经典的算法中去,每个这类的题都有自己鲜明的特点,对于它们根本没有一般的解法。对于这样的挑战,一个新颖的数据结构或一套特殊的循环或判断常常是必须的。解决这种问题的关键在于仔细地阅读题目的叙述,灵感经常来自于将叙述的逻辑条理整理得十分清楚之后,同样,对这类题的优化也是需要的,至少需要避免过多的循环嵌套。

五、编程与竞赛
    学习编程并不是为了参加竞赛,竞赛对于多数选手的意义还是在于参与,以及在备战过程中对自己的锻炼和提高。在这一点上,ACM竞赛和其它一系列竞赛是一样的,只是它的影响力和规模大些罢了,所以笔者希望对编程有兴趣的同学都能够关注竞赛,即使不参加,通过了解竞赛中涉及的编程知识达到课内很难达到的高度,这对每个人都是有益无害的。