acmicpc程序设计方法与实践

1、ACMACM/ICPC程序设计方法与实践ACM International Collegiate Programming Contest1关于ACM/ICPCMissionThe ACM International Collegiate Programming Contest (ICPC) provides college students with opportunities to interact with students from other universities and to sharpen and demonstrate their problem-solving, progr

2、amming, and teamwork skills. The contest provides a platform for ACM, industry, and academia to encourage and focus public attention on the next generation of computing professionals as they pursue excellence. (from the ICPC Policies and Procedures)关于ACM/ICPCIntroductionThe contest is a two-tiered c

3、ompetition among teams of students representing institutions of higher education. Teams first compete in Regional Contests, held around the world from October to November each year. The winning team from each Regional Contest advances to the ACM International Collegiate Programming Contest World Fin

4、als that is typically held in March. Additional high-ranking teams may be invited to the World Finals as Wild Card teams. These rules are subject to change.关于ACM/ICPCTeam RequirementsTeams qualify to advance to the World Finals through Regional Contests. Only one team from a given institution may ad

5、vance to the World Finals. Team members will be provided free one-year memberships in ACM at On-Site Registration. No team member on the qualifying team may have competed as a contestant in two previous World Finals.关于ACM/ICPCConduct of the FinalsEight or more problems have been posed in recent Worl

6、d Finals.Problems will be posed in English. During the contest, all communications from contest officials to contestants will be in English. Each team may identify an interpreter for translating questions posed by contestants to contest officials. Contestants may bring electronic natural language tr

7、anslators provided that they do not support math operations. Solutions to problems submitted for judging are called runs. Each run is judged as accepted or rejected, and the team is notified of the results. Rejected runs will be marked as follows: run-time error time-limit exceeded wrong answer pres

8、entation error Notification of accepted runs will be suspended at the appropriate time to keep the final results secret. A general announcement to that effect will be made during the contest. Notification of rejected runs will continue until the end of the contest. A contestant may submit a claim of

9、 ambiguity or error in a problem statement by submitting a clarification request. If the Judges agree that an ambiguity or error exists, a clarification will be issued to all contestants. While the contest is scheduled to last five hours, the Finals Director has the authority to lengthen the contest

10、 in the event of unforeseen difficulties. Should the Contest duration be altered, every attempt will be made to notify contestants in a timely and uniform manner. 关于ACM/ICPCScoring of the World FinalsThe World Finals Judges are solely responsible for determining the correctness of submitted runs. In

11、 consultation with the World Finals Judges, the Director of Judging is responsible for determining the winners of the World Finals. They are empowered to adjust for or adjudicate unforeseen events and conditions. Their decisions are final. Teams are ranked according to the most problems solved. Team

12、s placing in the first twelve places who solve the same number of problems are ranked first by least total time and, if need be, by the earliest time of submittal of the last accepted run. The total time is the sum of the time consumed for each problem solved. The time consumed for a solved problem

13、is the time elapsed from the beginning of the contest to the submittal of the first accepted run plus 20 penalty minutes for every previously rejected run for that problem. There is no time consumed for a problem that is not solved.关于ACM/ICPCComputing EnvironmentThe World Finals programming language

14、 tools include Java, and C/C+.Each team will be provided with a single computer and a calculator. All teams will have equivalent computing equipment.Contestants may not bring any printed materials or machine-readable versions of software or data to the Contest Area. Contestants may not bring their o

15、wn computers, computer terminals, calculators, or other electronic devices to the Contest Area.ACM/ICPC的历史1977, Atlanta, Georgia1978, Detroit, Michigan1979, Dayton, Ohio1980, Kansas City, Missouri2005, Shanghai, Pudong2006, San Antonio2007, Tokyo 2008, Banff2009, Stockholm2010, HarbinACM/ICPC的历史.the

16、 RESULTS are in from Orlando!The 2000 World ChampionsThe St. Petersburg State University ACM/ICPC的历史.the RESULTS are in from Vancouver!The 2001 World ChampionsThe St. Petersburg State University - twice in a row!ACM/ICPC的历史.the RESULTS are in from Honolulu!The 2002 World ChampionsShanghai JiaoTong U

17、niversity! ACM/ICPC的历史.the RESULTS are in from Beverly Hills!The 2003 World Champions:Warsaw University! ACM/ICPC的历史.the RESULTS are in from Prague!The 2004 World Champions:St Petersburg Institute of Fine Mechanics and Optics ACM/ICPC的历史.the RESULTS are in from Pudong!The 2005 World Champions:Shangh

18、ai Jiao Tong University ACM/ICPC的历史.the RESULTS are in from San Antonio!The 2006 World Champions:Saratov State University ACM/ICPC的历史.the RESULTS are in from Tokyo!The 2007 World Champions:Warsaw University ACM/ICPC的历史.the RESULTS are in from Banff!The 2008 World Champions:St. Petersburg University

19、of IT, Mechanics and OpticsACM/ICPC的历史.the RESULTS are in from Stockholm!The 2009 World Champions:St. Petersburg University of IT, Mechanics and OpticsACM/ICPC的历史.the RESULTS are in from Harbin!The 2010 World Champions:Shanghai Jiaotong takes first place20ACM/ICPC的历史Place Name Solved Time 1St. Peter

20、sburg University of IT, Mechanics and Optics811872Massachusetts Institute of Technology79973Izhevsk State Technical University710084Lviv National University710105Moscow State University711656Tsinghua University713477Stanford University713548University of Zagreb714049University of Waterloo7159710Petr

21、ozavodsk State University681911St. Petersburg State University682612Belarusian State University68572008年Banff World Finals比赛结果ACM/ICPC的历史PlaceNameSolved1St. Petersburg State University of IT, Mechanics and Optics92Tsinghua University93St. Petersburg State University84Saratov State University85Univer

22、sity of Oxford76Zhejiang University77Massachusetts Institute of Technology78Altai State Technical University79University of Warsaw710University of Waterloo611I. Javakhishvili Tbilisi State University612Carnegie Mellon University613South China University of Technology614Sharif University of Technolog

23、y614Seoul National University614Fudan University614Moscow State University614National Taiwan University614Shanghai Jiaotong University62009年Stockholm World Finals比赛结果ACM/ICPC的历史2010年Harbin World Finals比赛结果PlaceNameSolvedTime1Shanghai Jiaotong University77782Moscow State University79403National Taiwa

24、n University67794Taras Shevchenko Kiev National University69285Petrozavodsk State University69856Tsinghua University69987Saratov State University610108University of Warsaw610429St. Petersburg State University6104210Zhongshan (Sun Yat-sen) University6104911Fudan University6111412KTH - Royal Institute

25、 of Technology6126513Ural State University61312ACM/ICPC的特点比赛形式的特点持续时间长5个小时竞争激烈，压力大以放气球的形式公布各队解题数强调解题的准确性和解题的速度以解题数排名，解题数相同的以解题时间排名提交错误将导致罚时强调团队协作三人一组，共同使用一台计算机ACM/ICPC的特点题目的特点题目以英语作为陈述语言只涉及算法设计，不涉及具体技术一般仅使用标准输入/输出题目表现为真实世界中的具体问题评测的特点一般不限制解题的方法，采用黑箱测试测试数据一般不会超出给定的范围对时间、空间要求较高，尤其是对时间要求较高ACM/ICPC的特点编程语

26、言JavaJava语言在比赛中容易处于不利的地位，因为Java对输入输出流的处理相比C/C+要复杂得多，而且Java程序的运行效率通常会低于C和C+的程序，而比赛对Java程序的时限通常并不给予等比例的放宽。CC语言看似“原始”，但在比赛中使用纯C语言的选手还是大有人在，这主要是由于C语言在效率上的优势。因此，只要努力提高自己在算法方面的造诣，即使只使用C语言，也一样能发挥巨大的威力。C+C+相对于Java和纯C语言，在输入输出流上的支持更为强大，可以方便地在标准流和文件流之间切换，方便了调试的工作。另外，C+的STL提供了基本数据结构和基本算法方面的强大支持，可以缩减编码的长度，提高编码的效

27、率，但相对地，使用STL往往要付出效率上的代价，而且很可能使不熟悉STL的使用者陷入不易发现的陷阱。ACM/ICPC的特点基础知识鉴于ACM/ICPC赛题的特点，对选手除了在编码、数据结构、算法方面有较高的要求外，以数学为主的基础知识也非常重要。2007年的总冠军Warsaw就是出自数学系，而不是计算机系。1、离散数学作为计算机学科的基础，离散数学是竞赛中涉及最多的数学分支，其重中之重又在于图论和组合数学。2、数论以素数判断和同余为模型构造出来的题目（最常见的是以密码学为背景的题目）往往需要较多的数论知识来解决。3、计算几何线段相交的判断、多边形面积的计算、内点外点的判断、凸包等等。4、线性代

28、数对线性代数的应用都是围绕矩阵展开的，一些表面上是模拟的题目往往可以借助于矩阵来找到更好的算法。5、初等数学与解析几何最基础的数学知识。ACMer语录浙大OJ：其实，世上本没有ACM，AC的人多了，也便有了！闲得无聊，AC两道再说！我不是天才！但我相信:努力可以超越天才！为了ACM努力当炮灰！好好学习，天天AC！在这里我们创造了一个朝代，后来的所有不能超过我们的人都应该瞻仰我们的成绩!ACMer语录北大OJ总感觉生活中还缺少点什么，那就是另一道题！做题如逆水行舟，不进则退！每日一AC！苏格拉底说： AC是一种习惯！ACMer语录其他各高校OJ：何以解忧,唯有AC! 一起努力一起加油共同进步让A

29、C来的更猛烈些吧！将AC进行到底！AC总有它的必要 ACC总有它的原因 WR总有它的痛楚！编程就像谱写一首乐曲轻松而自然！月亮慢慢的爬上山头, 我悄悄的爬进你的草窝, 你突然跳起来大吼, 小丫,又来AC！AC漫漫其修远兮吾将上下而求索！ACM/ICPC的解题技巧读题时要抓住问题的抽象模型算法设计是关键不必过多考虑输入的异常不要只关注到题目给出的测试数据，要考虑到所有可能的测试情况有时可以预分配好所需数据空间以简化代码可能会比使用STL更简单打表法经常是不被禁止的ACM/ICPC的解题技巧分析第一次上机题交换问题三数排序问题阶乘累加ACM/ICPC的解题技巧命令行的使用（以Windows为例）命

30、令行的启动常用命令行命令CD、DIR、COPY、DEL、RENTYPE、MORE、FIND、FC命令行使用技巧重复执行命令复制与粘贴重定向与管道ACM/ICPC的解题技巧打表排错制作测试数据自动化测试常用算法设计策略穷举分治动态规划贪心回溯限界剪枝推理推理法举例最大公约数问题m和n的最大公约数等于n和m%n的最大公约数。海盗分金问题海盗按编号顺序提出分金方案；若投票结果，有不少于半数同意，则通过；否则，提方案的海盗被开除，由下一名海盗继续提出方案；补充几个常用算法并查集（等价类问题）并查集问题是指集中于集合的查找和合并操作的问题并查集问题以采用森林方式表示集合的实现较为有效。每棵树表示一个集合

31、，以树根代表集合。查找一个元素属于哪一个集合，即查找该元素所在子树的根结点。合并两个集合，可以通过简单地合并两棵树来实现。补充几个常用算法并查集（等价类问题）例一：最小生成树的Kruskal算法先将每个顶点视为一个独立的点集；排序所有的边；依次扫描每一条边，如果边的两个顶点在同一个点集中，则舍弃该边，否则，输出该边，并合并这两个点集。这里需要对一组点集进行查询和合并操作。补充几个常用算法并查集（等价类问题）例二：团伙问题在某城市里住着n个人，任何两个认识的人不是朋友就是敌人，而且满足：1、我朋友的朋友是我的朋友；2、我敌人的敌人是我的朋友；所有是朋友的人组成一个团伙。输入为n个人的m条信息（即

32、某两个人是朋友，或某两个人是敌人），请计算出这个城市最多可能有多少个团伙。补充几个常用算法并查集（等价类问题）实现技巧将每个集合用一棵树来表示，全部集合构成一个森林。用父链结构表示一棵树（一个集合），以根结点的序号或指针作为该集合的标识。查询一个元素所属的集合， 只需沿父链寻根即可。合并两个集合，只需将一个集合的根结点并为另一个集合的根结点的子结点即可。在合并时，可考虑合并的顺序，以尽可能减少树的深度。补充几个常用算法图的匹配问题对一个无向图G=(V, E)，匹配是指一个边的集合，其中任意两条边没有公共顶点。完美匹配是指所有顶点都有匹配的匹配。最大匹配是指具有最大边数的匹配。极大匹配是指不能再

33、增加边数的匹配。补充几个常用算法图的匹配问题非常稠密图中的完美匹配设无向图G=(V, E)，其中|V|=2n，且每个顶点的度不小于n。可以先用贪心法构造一个极大匹配M，M中含有m条边。若mn，则对M进行扩展，扩展方法如下：由于M是极大非完美匹配，因此必存在顶点v1和v2不属于M，且不属于E。则v1和v2至少向外发出2n条各不相同的边，且这些边都指向M覆盖的顶点。由于 M中的边数小于n，而从v1和v2发出并指向M的边数不少于2n条，所以至少有一条边与来自v1和v2的三条边相连，例如：, , 。通过从M中删除，加入, ，可以得到一个更大的匹配。u1v2u2v1u1v2u2v143补充几个常用算法图

34、的匹配问题偶图匹配对无向图G=(V, E, U)，V和U是两个不相交的顶点集合，E是连接V和U的边的集合，称为偶图。在偶图上寻找一个最大匹配。对于一个给定的匹配M，定义交互路径P为从V中顶点v出发到达U中顶点u的路径，其中v和u都不在匹配M中，P上的边是由E-M和M中的边交互构成的。将M中属于P的边用P上属于E-M的边替换可以得到一个更大的匹配。交互路径定理：一个匹配是最大的，当且仅当不存在交互路径。可以先用贪心法得到一个极大匹配，然后反复搜索交互路径，并相应扩展匹配，直到找不到交互路径为止。123456ABCDEF偶图45123456ABCDEF极大匹配46123456ABCDEF交互路径4

35、7123456ABCDEF利用交互路径对极大匹配进行扩展48123456ABCDEF交互路径49123456ABCDEF对极大匹配进行扩展50补充几个常用算法最大流问题设有一个有向连通图G(V, A), 在V中指定一点称为发点s, 和另一点称为收点t, 其余的称为中间点. 弧(arc)集A中每条弧(i,j) 上有非负数cij 称为这弧的容量, 记容量集为c= cij, 称这样的图为一个网络. 记为G=(V,A,c). (注：当(i,j)不是弧时 cij=0.)。在弧集A上的弧(i,j) 定义一非负数fij，称为弧(i,j)上的流量，流量的集合f=fij称为网络的一个流。满足下列条件的流称为可行

36、流：1. 容量限制条件， 所有的弧的流量fij不大于弧的容量cij。2. 平衡条件，对所有的中间点，流入的流量和等于流出的流量和; 发点流出的总流量F等于流进收点的总流量F。最大流问题就是求总流量F最大的可行流。svutw5/54/33/33/27/34/27/76/51/15/54/36/3注释：容量/流量52补充几个常用算法最大流问题当一弧的流量等于弧的容量时，称该弧为饱和弧。当一弧的流量小于弧的容量时，称该弧为不饱和弧。流量等于零的弧称为零流弧。流量大于零的弧称为非零流弧。若W是一条从发点到收点的有向道(walk)，规定从发点到收点的方向为道的方向。道上与W的方向相同的弧叫前向弧，道W上

37、的前向弧的全体记为A+, 道上与W的方向相反的叫后向弧. 后向弧的全体记为A-。svutw5/54/33/33/27/34/27/76/51/15/54/36/3注释：容量/流量54补充几个常用算法最大流问题设f 是一个可行流，W是发点到收点的一条有向道，如果W满足下列条件，称之为关于可行流f的一条可增广道：1. 每条前向弧是非饱和弧；2. 每条后向弧是非零流弧；沿着可增广道可以调整道上弧的流量，使得道上的每条前向弧增加一流量d，每条后向弧减少同一流量d，使得所得的流仍是可行流，但使总流量F增加d。 例如可取对于这样得到的可行流，该道不再是可增广道了。可行流f*是最大流当且仅当不存在关于f*的

38、可增广道。svutw5/54/33/33/27/34/27/76/51/15/54/36/3注释：容量/流量56svutw5/54/33/33/27/54/47/76/51/15/54/16/5注释：容量/流量57模拟题型举例贪吃蛇问题在一个m*n的网格空间上，有一条起始长度为t的贪吃蛇，并以每单位时间移动长度1的速度前进。在网格上分布着一些果实，当贪吃蛇经过果实时，就会吃掉果实，并且长度增加1，即在下一个单位时间蛇头前进而蛇尾不动。玩家用方向键控制蛇头的前进方向，如果蛇头撞到墙或自己的身体，游戏结束。起始时蛇的方向是水平的，蛇头在左，蛇尾在右。输入为蛇的起始位置、果实的位置和玩家的操作序列（

39、时间、方向）。要求输出游戏结束时蛇的长度。59模拟题举例Chutes and LaddersA popular board game for children is called Chutes and Ladders. The board has squares which are numbered from 1 to 100, and players have counters which start on the theoretical square 0. The players take turns at throwing a die with the numbers 1 to 6 on

40、 it, and each moves his or her counter forward the number of squares corresponding to the number on the die (the square they reach is found by adding the die number to the square number their counter is on). The first person to reach square 100 is the winner. The interest is caused by the fact that

41、pairs of squares are connected together by ladders (which connect a lower-numbered square to a higher-numbered square) and chutes (which run from high to low). If a counter lands on the start of a chute or ladder (i.e., this is the square reached after throwing the die), then the counter is moved to

42、 the corresponding square at the end of the chute or ladder. Note that landing on the end square of a ladder or a chute has no effect, only the start square counts. Furthermore, there are some squares such that if a players counter lands on them, then the player must either miss the next turn, or im

43、mediately throw the die again for another turn, depending on what is written on the board. A miss-a-turn or extra-turn square is never the start or end of a ladder or chute. If a player is on square 95 or higher, then a die throw which takes them past 100 must be ignored - thus a player on square 99

44、 must ignore all throws which are not 1.A popular board game for children is called Chutes and Ladders. The board has squares which are numbered from 1 to 100, and players have counters which start on the theoretical square 0. The players take turns at throwing a die with the numbers 1 to 6 on it, a

45、nd each moves his or her counter forward the number of squares corresponding to the number on the die (the square they reach is found by adding the die number to the square number their counter is on). The first person to reach square 100 is the winner. The interest is caused by the fact that pairs

46、of squares are connected together by ladders (which connect a lower-numbered square to a higher-numbered square) and chutes (which run from high to low). If a counter lands on the start of a chute or ladder (i.e., this is the square reached after throwing the die), then the counter is moved to the c

47、orresponding square at the end of the chute or ladder. Note that landing on the end square of a ladder or a chute has no effect, only the start square counts. Furthermore, there are some squares such that if a players counter lands on them, then the player must either miss the next turn, or immediat

48、ely throw the die again for another turn, depending on what is written on the board. A miss-a-turn or extra-turn square is never the start or end of a ladder or chute. If a player is on square 95 or higher, then a die throw which takes them past 100 must be ignored - thus a player on square 99 must

49、ignore all throws which are not 1. 61Input will start with a set of less than 1000 die throws which you must use for all games, starting each new game with the first player throwing the first number in the set, the next player throwing the second number, and so on. This set of die throws will simply

50、 be a list of random numbers between 1 and 6, separated by single spaces, with not more than 80 characters on each line. It will be terminated by the number 0. After this set of die throws, there will be one or more game sets. Each game set is in three parts. The first part is a line containing a si

51、ngle number giving the number of players in the game. This will be more than 1 and less than 6. Then the board is described, in two parts. The first part lists the ladders and the chutes on the board, each ladder or chute being defined on a single line. Each is given by two numbers, from 1 to 99,sep

52、arated by one or more spaces. The first number gives the start square, and the second number gives the end square; so it is a ladder if the first number is less than the second number, and a chute if the order is the other way. The chute/ladder definitions are terminated by a line containing two 0s.

53、 The second part of the board description gives the lose-a-turn/extra-turn squares, if there are any. These are single numbers, one per line, defining the squares. If the number is negative, its positive counterpart is a lose-a-turn square; if positive, it represents an extra-turn square. (For examp

54、le, -16 means that square 16 on the board is a lose-a-turn square, while a 25 means that players landing on square 25 must immediately roll again.) The end of this set of descriptions, and of the game description, is given by a single 0. The end of all the game descriptions is given by a game with t

55、he number of players equal to 0. 62Output must be one line for each game in the input, giving the number of the player who wins the game. Every game will determine a winner in fewer throws than those given at the start of the data. Sample Input3 6 3 2 5 1 3 4 2 3 1 2 026 9599 10 0-398023 996 900 000

56、Sample Output2263浅谈ACM/ICPC的题目风格和近几年题目的发展作者：王颖文章来源：ACM组委会点击数：126更新时间：2008-10-9ACM ICPC的比赛形式一般是五个小时八个题目，综合考察选手的数学能力、算法能力、coding能力和debug能力，还有团队配合能力。数学方面主要强调组合数学、图论和数论这三个方面的能力；而算法的覆盖范围很广，涉及了大部分经典的算法，和少量较前沿的算法。由于每道题目都需要通过所有的测试数据才能得分，并且需要精确解，这限制了Approximation algorithm在一些NP-hard的题目中的运用，从而使得搜索和剪枝策略对于NP-ha

57、rd的题目非常重要。Final的题目和Regional题目的比较ACM ICPC官方的正式比赛可分为World Final和Regional Contest两种。Final的题目更加正统和严谨，强调算法的综合运用，一个题目往往需要几种算法的结合。从这几年的final的题目看，final加大了题目的代码量，对代码能力的要求有所增强。而Regional的题目则更加灵活，同时每个赛区也有自己的出题风格。欧洲赛区的题目以高质量出名，对算法和数学的强调甚至超过了World Final；美国的赛区较多模拟题，强调代码量。而亚洲则介于两者之间，同时由于每年都有一些新的赛区，所以并没有很固定的模式。下面浅谈一

58、下近几年ACM ICPC的题目的覆盖面。一些常规的算法和题型没什么好讲的，下面主要侧重一些新颖的知识点或题型，或是一些较前沿的内容。数学的新题型除了一些基本的组合数学和组合数论的问题，近年来概率和Combinatorial Game Theory的题目逐渐增多。很多有趣的题目都是以Markov Process为背景，需要用到一些相关的知识。去年国内杭州赛区的一个很有趣的题目是，给出一个字符集（比如A,B,C）和一个字符串T（比如ACBBCAC），现在从一个空串S开始，每次等概率的添加A,B,C中的一个字符，直到T是S的一个子串。问得到的字符串S的长度的期望。这是一个典型的Markov Process，其解可以用生成函数很优美的算出来。一个更有趣的版本是，假如还有另一个字串R，当S中出现T或者R就终止，问终止在T和R的概率各是多少。这个问题在Graham, Knuth, 和Patashnik合著的Concrete Mathematics里面有详细的分析，并有着一个优美的结论。Game theory方面，主要是经典的combinatorial game theory而比较少Zero-sum game和Nash equilibrium