对ACM新人的建议.doc

《对ACM新人的建议.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、对ACM新人的建议内容介绍>>一、语言是最朿要的基本功无论侧重于什么方面，只要是通过计算机程序去最终实现的竞赛，语言都是大家要过的第一道关。亚洲赛区的比赛支持的语言包括C/C++与JAVA。笔者首先说说JAVA,众所周知，作为面向对象的王牌语言，JAVA在大型工程的组织与安全性方面有着自己独特的优势，但是对于信息学比赛的具体场合，JAVA则显得不那么合适，它对于输入输出流的操作相比于C++要繁杂很多，更为重要的是JAVA程序的运行速度要比C++慢10倍以上，而竞赛中对于JAVA程序的运行时限却往往得不到同等比例的放宽，这无疑对算法设计提出了更高的要求，是相

2、当不利的。其实，笔者并不主张大家在这种场合过多地运用面向对象的程序设计思维,因为对于小程序來说这不旦需要花费更多的时间去编写代码,也会降低程序的执行效率。接着说C和C卄。许多现在参加讲座的同学还在上大一，C的基础知识刚刚学完，还没有接触过C++,其实在赛场上使用纯C的选手还是大有人在的，它们主要是看重了纯C在效率上的优势，所以这部分同学如果时间有限，并不需要急着去学习新的语言，只要提高了自己在算法设计上的造诣，纯c—样能发挥巨大的威力。而C++相对于C,在输入输出流上的封装大大方便了我们的操作，同时降低了出错的可能性，并H能够很好地实现标准流与文件流的切换

3、,方便了调试的工作。如果有些同学比较在意这点,可以尝试C和C++的混编，毕竞仅仅学习C++的流操作还是不花什么时间的。C++的另一个支持来源于标准模版库（STL）,库中提供的对于基本数据结构的统一接口操作和基本算法的实现可以缩减我们编写代码的长度，这可以节省一些时间。但是，与此相对的，使用STL要在效率上做出一些牺牲，对于输入规模很大的题目，有时候必须放弃STL,这意味着我们不能存在“有TSTL就可以不去管基本算法的实现”的想法：另外，熟练和恰当地使用STL必须经过一定时间的积累，准确地了解各种操作的时间复杂度，切忌对STL中不熟悉的部分滥用，因为这具屮蕴

4、涵着许多初学者不易发现的陷阱。通过以上的分析，我们可以看出仅就信息学竞赛而言，对语言的学握并不要求十分全面，但是对于经常用到的部分，必须十分熟练，不允许有半点不清楚的地方，下面我举个真实的例子來说明这个道理一即使是一点很细微的语言障碍，都有可能酿成错误：在去年清华的赛区上，有一个队在做I；题的时候使用了cout和printf的混合输出，山于一个带缓冲一个不带，所以输出一长就混乱了。只是因为当时judgeteam中负责1；题的人眼睛尖，看出答案没错只是顺序不对（答案有一页多，是所有题目中最长的一个输出），又看了看程序发现只是输出问题就给了个Presentat

5、ionerror（格式错）。如果审题的人不是这样而是直接给一个WrongAnswer,相信这个队是很难查到自己错在什么地方的。现在我们转入第二个方面的讨论，基础学科知识的积累。二、以数学为主的基础知识十分重要虽然被定性为程序设计竞赛,但是参赛选手所遇到的问题更多的是没有解决问题的思路，而不是有了思路却死活不能实现，这就是平时积累的基础知识不够。今年World卜'indl的总冠军是波兰华沙大学，其成员出自于数学系而非计算机系，这就是一个鲜活的例子。竞赛屮对于基础学科的涉及主要集屮于数学，此外对于物理、电路等等也可能有一定应用，但是不多。因此，大一的同学也不必

6、为口己还没学数据结构而感到不知从何入乎提高，把数学捡起來吧！下血我來谈谈在竞赛中应用的数学的主要分支。1、离散数学——作为计算机学科的基础,离散数学是竞赛中涉及最多的数学分支，其重中之重又在于图论和组合数学，尤其是图论。图论之所以运用最多是因为它的变化最多，而且可以轻易地结合基本数据结构和许多算法的基木思想，较多用到的知识包扌舌连通性判断、DFS和BFS,关节点和关键路径、欧拉冋路、最小生成树、最短路径、二部图匹配和网络流等等。虽然这部分的比朿很大，但是往往也是竞赛屮的难题所在，如果有初学者对于这部分的某些具体内容暂时感到力不从心，也不必着急，可以慢慢积累

7、。竞赛屮设计的组合计数问题大都需要用组合数学來解决，组合数学屮的知识相比于图论要简单一些,很多知1识对于小学上过奥校的同学來说已经十分熟悉，但是也有一些部分需要先对代数结构屮的群论令初步了解才能进行学习。组合数学在竞赛屮很少以难题的形式出现，但是如果积累不够，任何一道这方面的题目却都有可能成为难题。2、数论——以素数判断和同余为模型构适出來的题目往往需要较多的数论知识來解决,这部分在竞赛屮的比重并不大，但只要來上一道，也足以使知I识不足的人冥思苦想上一阵时间。索数判断和同余最常见的是在以密码学为背景的题日中出现，在运用密码学常识确定大概的过程之后，核心算法

8、往往要涉及数论的内容。3、计算几何——计算几何相比于其它部分來说是