【8A文】Acm竞赛常用算法与数据结构.ppt

《【8A文】Acm竞赛常用算法与数据结构.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、1常用算法&数据结构浙江大学微软技术俱乐部彭鹏ACM竞赛22、竞赛中常见的16种题型1、ACM/ICPC简介4、竞赛中基本的数据结构与算法5、ZOJ入门3、时空复杂度的分析3ACMAssociationforComputingMachinery美国计算机学会ICPCInternationalCollegiateProgrammingContest国际大学生程序设计竞赛ACM/ICPC简介4ACMACM(AssociationforComputingMachinery)成立于计算机诞生次年，是目前计算机学界中历史最悠久、最具权威性的组织，是推进信息技术专业

2、人员和学生提高技巧的主要力量。ACM通过提供前沿技术信息和从理论到实践的转化，为其全球7.5万名成员服务，并已经成为信息科技领域的一个基本信息来源。5ICPCACM主办的国际大学生程序设计竞赛(InternationalCollegiateProgrammingContest)，简称ACM/ICPC，自从1977年开始至今已经连续举办28届。其宗旨是提供一个让大学生向IT界展示自己分析问题和解决问题的能力的绝好机会，并成为一个有效的途径，让下一代IT天才可以接触到其日后工作中将要用到的各种软件。自1998年IBM成为该项竞赛的赞助商以来，大赛规模不断扩大

3、。去年有71个国家1582所大学派出4109支队伍参加了30个赛点的分区赛，其中78支队伍参加今年4月在上海香格里拉酒店举办的世界总决赛。现在，ACM/ICPC已成为世界各国大学生中最具影响力的国际计算机赛事。6ICPC竞赛规则三人组队在4~6小时编写C/C++或Java程序解决6~10道题完成题目数多的队伍优胜完成题目数一样的队伍,罚时少的优胜7ICPClogAproblemAthoughtAsolutionAballoon8中国各高校ACM开展情况清华大学上海交通大学中山大学复旦大学北京大学南京大学浙江大学9浙江大学ACM集训队选拔标准根据校内程序设

4、计竞赛的结果，现拟定集训队具体选拔标准如下：1.曾参加过去年暑假集训的队员自愿入围；未参加过集训，但满足下列条件者自愿入围：2.对ACMICPC活动有极大热情，视练习题如游戏；并且3.校内程序设计竞赛前5名；或者4.校内程序设计竞赛第6-9名，并且7月1日前在ZOJ通过至少100题；或者5.校内程序设计竞赛第10-15名，并且7月1日前在ZOJ通过至少150题；或者6.7月1日前在ZOJ通过至少200题。10如何建立一支强队个人的能力理论(几何,数论,动态规划,图论等)技术(编程)队员能力上的互补某论坛，一无聊男yy的中国“梦之队”钱文杰（？）反应奇快，

5、擅长随机化，贪心，NOI贪心王刘汝佳or吴嘉之见多识广，做过的题必别人见过的题多赵爽上海交大的“割题手”11Leader/Coordinato(协调比赛进程)Reader(发现题目隐讳的涵义)Thinker(逻辑能力强,收集其他队员意见)Programmer/Debugger(反应快/稳,细心)Helper(协助比赛,查错,验证数据等)一支强队需要的角色12参考书籍主要参考书籍《C++Primer》《C++标准程序库》《算法导论》《算法艺术与信息学竞赛》《组合数学》《计算几何》？？历届国家集训队论文13网络资源http://acm.zju.edu.cnh

6、ttp://acm.timus.ruhttp://acm.sgu.ruhttp://ace.delos.com/usacogatehttp://www.google.comhttp://www.oibh.org/bbs/index.php14时空复杂度的分析时间复杂度的分析空间复杂度的分析15函数增长和运行时间引用刘汝佳《序列和字符串》16常见题型DynamicProgramming(动态规划)Greedy(贪心)CompleteSearch(穷举)FloodFill(种子填充)17常见题型ShortestPath(最短路径)RecursiveSearc

7、hTechniques(回溯）MinimumSpanningTree（最小生成树）Knapsack（背包）18常见题型ComputationalGeometry(计算几何)NetworkFlow(网络流)EulerianPath(欧拉回路)Two-DimensionalConvexHull(二维凸包)19常见题型BigNums(大数)HeuristicSearch(启发式搜索)ApproximateSearch(近似搜索)AdHocProblems(杂题)2021枚举法又叫穷举法，它利用了计算机计算速度快且准确的特点，是最为朴素和有效的一种算法。不是办法

8、的办法但有时却是最好的办法22PizzaAnyone?（ZOJ1219）题目大意