湘潭大学ACM-ICPC新人训练导引
Version 2013
2013.11.8
一、 竞赛介绍
1. ACM-ICPC
ACM/ICPC从1970年开始，已经举办了30多届，其目的旨在使大学生运用计算机来充分展示自己分析问题和解决问题的能力。该竞赛一直受到国际各知名大学的重视，并受到全世界各著名计算机公司的高度关注。可以说，ACM国际大学生程序设计竞赛已成为世界各国大学生最具影响力的国际级计算机类的赛事。
ACM/ICPC 采用组队参赛的形式，由三名队员组成一支队伍参赛。比赛时三名队员只使用一台电脑，但可以打印代码及输出结果等。整个比赛时间为5个小时。比赛题目为8-12 道不等，全英文。比赛是只能携带纸质材料。标准的程序数据输入和输出解答要求。选手们必须根据题目内容设计算法，并完成相应的功能要求。该队程序如果能在规定时间内得出正确的答案视为通过。队伍通过的题目数量多的在比赛中排名越高，题目数相同的则用时越少的排名越高。用时的计算是所有的题目从比赛开始到正确解答的时间之和,比如一个队一共做出5道题,这5道题分别是在10,50,80,140,260分钟正确解答,那么总罚时是10 + 50 + 80 + 140 + 260,但是这是没有考虑错误提交的次数,每一次的错误提交会加罚20分钟。
2014年 ACM-ICPC 赛季将于明年9月份拉开帷幕。明年年亚洲区预选赛在大陆地区一共有5站比赛，地点待定（有可能的地点：上海，北京，南阳，广州，鞍山）。每个赛区需要先通过网络预赛，网络预赛按照学校排名，给予各个参赛学校参赛名额，获得名额的学校可以派队参加现场赛。在区域赛的现场赛成绩突出者可以参加2015年世界总决赛（可能在泰国普吉岛）。按目前的情况，我们区域赛基本上保证7~8队次。区域赛的金，银，铜奖分别为15个,30个，现场赛参赛队伍30%-45个（可能会有微调）。
2. 湖南省大学生程序设计比赛
湖南省大学生程序设计比赛(Hunan Collegiate Programming Contest，简称HNCPC) 由湖南省教育厅主办，湖南省高教学会计算机教育专业委员会协办。大赛每年举办一次。
比赛模仿ACM-ICPC的赛制，今年题目为5道英文，6道中文，其中有三道极水的基础题。省赛的赛题和比赛日益规范，是区域赛前很好的热身机会，同时也是大家争取荣誉的好机会，毕竟省赛比区域赛简单很多。
省赛我们将派4支队伍，一、二、三等奖为参赛队伍的10%，15%，20%。
3. 往年成绩
年份 2007 2008 比赛 32th ACM-ICPC亚洲区域赛-成都站 3th 湖南省大学生程序设计比赛 33th ACM-ICPC亚洲区域赛-合肥站 教练 石跃祥 谢勇 谢勇 队员 黄启友，杨新勤，陈良 易传焜，郑卜之，陈良 胡琨，王东旭，谢斌 获奖 铜奖 二等奖 铜奖 33th ACM-ICPC亚洲区域赛-成都站 4th 湖南省大学生程序设计比赛 34th ACM-ICPC亚洲区域赛-上海站 梁哲伟 谢勇 梁哲伟 谢勇 胡琨，王东旭，谢斌 胡琨，王东旭，谢斌 常青，雷鑫，李阳 胡琨，王东旭，尹苓琳 胡琨，王东旭，尹苓琳 常青，王计，刘元盛 程浩，侯实夫，邓家超 李阳，王东旭，尹苓琳 李龙，潘凡，刘伟 程浩，侯实夫，邓家超 侯实夫，邓家超，唐杰 王计，刘元盛，高路 侯实夫，邓家超，唐杰 袁良骅，马锦，王会会 邓家超，侯实夫，唐杰 王计，刘元盛，高路 铜奖 三等奖 三等奖 银奖 铜奖 铜奖 铜奖 三等奖 三等奖 三等奖 铜奖 铜奖 铜奖 铜奖 一等奖 一等奖 34th ACM-ICPC亚洲区域赛-哈尔滨站 谢勇 34th ACM-ICPC亚洲区域赛-宁波站 2009 34th ACM-ICPC亚洲区域赛-武汉站 谢勇 石跃祥 谢勇 5th 湖南省大学生程序设计比赛 谢勇 石跃祥 35th ACM-ICPC亚洲区域赛-天津站 35th ACM-ICPC亚洲区域赛-杭州站 35th ACM-ICPC亚洲区域赛-成都站 2010 35th ACM-ICPC亚洲区域赛-福州站 谢勇 谢勇 谢勇 谢勇 谢勇 6 湖南省大学生程序设计比赛 th谢勇 谢勇 石跃祥 王国建，刘新星，吉韶峰 一等奖 袁良骅，马锦，王会会 王国建，唐杰，高路 王计，陈一鸣，胡钧 王国建，唐杰，高路 王计，陈一鸣，胡钧 王国建，唐杰，高路 王计，陈一鸣，胡钧 二等奖 银奖 铜奖 银奖 银奖 一等奖（冠军） 一等奖 36th ACM-ICPC亚洲区域赛-大连站 36th ACM-ICPC亚洲区域赛-上海站 36th ACM-ICPC亚洲区域赛-北京站 36th ACM-ICPC亚洲区域赛-成都站 2011 谢勇 谢勇 谢勇 石跃祥 谢勇 石跃祥 7th 湖南省大学生程序设计比赛 谢勇 谢勇 王金胜，向林波，尹旭波 二等奖 黄日强，郑智聪，林伟池 二等奖 胡钧，黄日强，林伟池 胡钧，黄日强，林伟池 胡钧，黄日强，林伟池 熊志成，郭子仟，罗帅 刘盾，钟巧思，陈秋茹 钟逸楠，柳晴，李远科 曾旭东，唐琦，程宇航 胡钧，林伟池，曾旭东 王晨宇，王文，邱浩南 胡钧，林伟池，曾旭东 王晨宇，王文，邱浩南 团体第1 银奖（Rank 16） 铜奖 一等奖 三等奖（兴湘） 三等奖 三等奖 三等奖 银奖（Rank 23） 铜奖 银奖（Rank 20） 铜奖 37th ACM-ICPC亚洲区域赛-杭州站 37th ACM-ICPC亚洲区域赛-成都站 谢勇 谢勇 谢勇 2012 8th 湖南省大学生程序设计比赛 谢勇 石跃祥 谢勇 谢勇 38th ACM-ICPC亚洲区域赛-成都站 谢勇 谢勇 谢勇 谢勇 2013 38th ACM-ICPC亚洲区域赛-南京站 38th ACM-ICPC亚洲区域赛-长沙站 谢勇 9th 湖南省大学生程序设计比赛 谢勇 谢勇 石跃祥 胡钧，林伟池，匡冬平 王晨宇，王文，邱浩南 二等奖 二等奖 李昌洲，钟逸楠，陈书宁 三等奖 柳晴，程宇航，李灏颖 三等奖 二、 训练纪律
1. 严格遵守机房规定，服从老师和教练组安排，主动配合管理工作。 2. 安全重于泰山，节约用水和用电，注意防火防盗。
3. 非集训队队员不允许进入机房。不经允许，不得带同学，朋友等来机房。 4. 爱护机房的电脑，桌椅，空调等设施。
5. 离开机房时关闭电脑，摆放好桌椅。最后离开者一定记得锁门。 6. 注意保持卫生，垃圾需要及时带出机房。
7. 刻苦训练，持之以恒。按时参加队内的训练活动，如不能参加，请事先向教练请假。 8. 严禁在机房打游戏，看电影等无关训练的行为，一经发现，第一次警告，第二次开除。 9. 诚信为本，遵守竞赛规则，比赛期间严禁抄袭代码，上网查找解题报告等作弊行为，一经发现，清除出队，永不录用。
三、 训练建议
1. 个人训练为主，强调自学能力，独立思考。遇到问题，首先独立思考，再查阅资料，善于利用搜索引擎，大部分问题在网络上均可找到答案。强调实践，自己动手敲代码，训练时不要使用模板或别人的代码，提高代码的能力。
2. 在顶尖的ACMer中，很多人走的都不是在OJ猛刷题的路。但是必要的题量是必须的，入门的同学必须经过一段刷水题的阶段，来提高自己的代码能力，200-300的水题量还是很容易的。当然开头会觉得很难，但是这个过程是渐进的，后期越来越快，一天刷20-30道水题完全无难度的。注意不要一味的刷水题过瘾，需要结合学习的算法，有针对性地做专题训练，这样才能保证上水平。低水平重复是没有什么意义的。
3. 三人行必有我师。善于与周围的队员交流，乐于分享自己的学习感悟。团队的进步和个人的进步是相互促进的。善于利用网络资源，比如QQ群等，和全国的ACMer进行交流。
4. 制定详细的学习计划，按部就班，循序渐进地学习，为每个目标设定Deadline。 5. 注重分类与总结。在做够一定类型的题目后，要善于分类，这样有利于理清思路，深入理解。同时注意积累总结，便于以后查阅。建议写个人技术Blog，这样方便整理和存档。
6. 强烈建议以参加 CodeForces ( http://codeforces.com )和
TopCoder
( http://www.topcoder.com/tc )比赛的方式来提高自己的水平。原因如下：
题目质量高，没有防吃蛋、防圆满的题 有官方题解
参赛者不乏来自世界各地的高手，你可以感受他们的节奏，学习他们不同的代码（编
程技巧、思路、算法模板）
可以打探国内各校ACMer的实力，甚至了解他们擅长的题型 熟悉比赛的气氛，正式比赛则不慌不乱
锻炼比赛的策略，知道在比赛该怎么调度自己，怎么安排做题的顺序和时间 有challenge模式，通过cha别人的代码来锻炼自己读（队友）代码的能力 数据赛后公开，了解数据该怎么出，了解什么地方容易有陷阱 7. 其他题库
POJ（http://poj.org/），题目杂而多，网上有很多题目分类和解题报告
ZOJ（ http://acm.zju.edu.cn ），题目杂而多，每月有月赛（ZJU队员原创题目，质量还可以，组队练习不容错过）
HDOJ（ http://acm.hdu.edu.cn ），目前国内的最大的OJ，近几年引入了很多ACM大陆地区赛的题目（好题），还有多校联赛的题目
HUST（ http://acm.hust.edu.cn:8080/judge/toIndex.action ），虚拟Judge，DIY比赛首选 BNU（http//www.bnuoj.com），另外一个虚拟OJ，DIY比赛
SGU( http://acm.sgu.ru )，都是原创题，难度偏大，题目数学味比较浓Timus( http://acm.timus.ru/ )，都是欧洲比赛的题目，质量还不错，但跟亚洲赛区风格不太一致
USACO Contest（http://ace.delos.com/contestgate ），月赛质量不错，OI模式 FZU(http://acm.fzu.edu.cn )，有月赛
CII(http://livearchive.onlinejudge.org/ )，历年所有Regional，Final的题目 UVa(http://uva.onlinejudge.org )，ICPC官方指定OJ，题目非常多
8. OJ题目质量良莠不齐。对于大部分比赛套题来说，总会有签到题，也有故意刁难型的题目，以前有些赛区还流行论文题（结论题）、模板题，这些题目都不具备多少训练价值。以上提到的这些题目我们不太需要关心，大部分参赛者都会做（或者都不会做）。我们训练的目的主要是锻炼自己实实在在的解题能力，一来能在比赛中把握住那些有区分度的题目，二来确实使自己的综合素质有所提升。
9. 阅读大牛的blog是一个很好的学习办法，很多人将自己的学习心得写成博客，相互学习，取长补短。
四、 推荐书籍
1. 《算法竞赛入门经典》 刘汝佳 清华大学出版社 很不错的入门书，建议入门的同学入手。
2. 《算法竞赛入门经典——训练指南》刘汝佳、陈峰 清华大学出版社 入门经典的提高篇，全书主要以题解为主。
3. 《挑战程序设计竞赛》秋叶拓哉 等编，巫泽俊 等译 北京邮电出版社 不错的入门级的教材（建议有语言基础），讲述比较简略，需要配合其他资料。 4. 《ACM国际大学生程序设计竞赛系列丛书》俞勇主编 清华大学出版社 基本等价于上海交通大学的模板库
5. 《算法导论》 科曼(Cormen T.H.) 机械工业出版社
涵盖面非常广，习题也很给力，学习算法的很值得推荐的一本书 6. 《数据结构（C++语言描述）》，维斯（Weiss） 数据结构的经典教材
7. 具体数学Ronald L. Graham, Donald E. Knuth, Oren 机械工业出版社 Knuth的书，锻炼数学思维能力
8. 数论概论（原书第3版）西尔弗曼（Silverman,J.H.）著；孙智伟 等译/2008年05月/机械工业出版社
数论入门的好书
9. 计算几何：算法与应用（第3版）（德）伯格（Berg，M.D.） 等著，邓俊辉 译/2009年08月/清华大学出版社
计算几何经典
10. 程序设计中的组合数学 吴文虎 主编，孙贺 编著/2005年05月/清华大学出版社 组合数学入门书籍
11. 《算法艺术与信息学竞赛》 刘汝佳 清华大学出版社
俗称“黑书”，难度较大，适合有一些基础的同学看，年代比较久了。 12. NOI论文集1999-2009，2012
跟踪OI届的最新知识点和算法，难度比较大
五、 必备知识点
ACM/ICPC涉及的知识非常的多，下面是一些常见的知识点，相关知识点可以在推荐的书籍以及通过搜索引擎查到。其中语言相关是为了更快地编写代码，其他都是和数据结构，算法相关的东西。其中暴力，数据结构，动态规划中的基础部分是每个人必须要掌握的内容，在时间容许的前提下，其他方向尽可能多掌握，至少需要掌握3个或以上。只有全面的队员
才能很好地和人交流，只有有特点的队员才能在团队中闪光，做到1+1+1>3。下面打*的为比较难的知识点。
A. 语言相关
C++ STL的容器vector, list, stack, queue, priority_queue, set, , pair, map C++ STL的算法库algorithm
Java的BigInterger, BigDecimal（用来写高精度计算的题目）
B. 暴力与搜索
回溯，排列，子集遍历 广度优先BFS（单向、双向） 深度优先DFS * 带权优先（A*） * alpha-beta剪枝 * Dancing-Link
C. 数据结构
Hash
线段树，Binary Index Tree 并查集 单调队列 LCA与RMQ * Splay Tree * Treap
* 树链剖分，动态树
D. 动态规划
// 要学会递推实现和记忆化搜索实现 1维，2维，树形，区间，概率，数位，状压 背包
* 单调队列优化，线段树优化，斜率优化，四边形不等式 * 轮廓线DP（插头DP）
E. 图论
拓扑排序，强连通，重连通，欧拉回路 最短路Dijkstra（深刻理解，能作各种变形） 最短路Bellman-Ford（支持负权，能判负环） 最小生成树Prim（深刻理解，能作各种变形） 最小生成树Kruskal（深刻理解，能作各种变形）
二分图匹配（无权的匈牙利，带权的EK）（跟最小覆盖的对偶关系） 树上经典问题（最小支配集，最大独立集，最小覆盖集，最长路等） * 最大流 * 最小费用最大流 * 2-SAT
F. 字符串
字符串Hash，RK算法 KMP，扩展KMP AC自动机
manacher算法求回文串 * 后缀数组，后缀自动机
G. 数论
扩展欧几里德（解方程，求逆元） 筛素数 快速判素数 素因子快速分解 欧拉函数 中国剩余定理 * 离散对数
H. 数值计算
矩阵快速幂 三分求凸函数极值 高斯消元
* 辛普森公式求积分 * FFT
I. 组合数学与博弈
置换群（* Burnside引理，Polya计数） Fibonacci，Catalan，Bell，Stirling数 容斥原理
Bash, Wythoff, Nim Game * SG函数
J. 计算几何
各种基本几何运算（平面变换，点线，线线，线圆） 凸包
扫描线算法 矩形交，矩形并 圆交，圆并 * 半平面交 最近点对
* 旋转卡壳，最远点对
* 基础3D几何（空间点面，空间线面，平移，拉伸，翻转，任意轴旋转） * 3D凸包
* 多面体的体积交，体积并
六、 新人训练计划
1. 入门题集80题，涉及到基础，暴力，贪心，搜索，基础DP，基础数据结构等内容。
1 HangoverPOJ-10032 Financial Management4 BiorhythmsPOJ-10043 I Think I Need a HouseboatPOJ-1005POJ-1006POJ-10075 DNA Sorting6 Who's in the Middle7 Uniform Generator9 ElevatorHDOJ-1157HDOJ-10148 Let the Balloon RiseHDOJ-1004HDOJ-1008HDOJ-103010 Delta-wave 11 Binary Number13 OrdersHDOJ-371112 Backward Digit SumsPOJ-3187POJ-173114 N皇后问题16 Matrix17 SticksHDOJ-255315 Prime Ring ProblemHDOJ-1016POJ-2078HDOJ-145518 Safecracker19 Fire Net20 棋盘问题22 生日蛋糕24 EightHDOJ-1015HDOJ-1045POJ-132121 Lake CountingPOJ-2386POJ-1190POJ-3126POJ-107723 Prime Path25 Holedox Moving26 Alice’s CubePOJ-1324HDOJ-322027 Ancient MessagesHDOJ-383928 Double MazeHDOJ-371329 Tempter of the Bone30 Gnome Tetravex31 PieHDOJ-1010ZOJ-1008POJ-3122POJ-327332 Monthly Expense34 Error Curves36 Gone Fishing33 Binary Tree TraversalsHDOJ-1710HDOJ-3714HDOJ-4442POJ-104235 Physical Examination37 Tian Ji -- The Horse Racing38 C. Main Sequence39 Texas TripHDOJ-1052POJ-3301Codeforces-286C40 Elevator Stopping Plan41 Wireless Network42 食物链43 StarsPOJ-1744POJ-2236POJ-1182POJ-235244 A Simple Problem with Integers45 Is It A Tree?47 Lost CowsPOJ-3468POJ-1308POJ-1984POJ-2182POJ-332146 Navigation Nightmare48 Apple Tree50 Attack49 Boring countingHDOJ-4358HDOJ-4031HDOJ-2046HDOJ-1143POJ-307051 骨牌铺方格53 Fibonacci52 Tri Tiling54 A Simple Math Problem55 Gauss Fibonacci56 PillsHDOJ-1757HDOJ-1588HDOJ-4165HDOJ-3723HDOJ-2068HDOJ-1100HDOJ-2512POJ-116357 Delta Wave58 RPG的错排59 Trees Made to Order60 一卡通大冒险61 The Triangle63 Palindrome65 搬寝室66 滑雪62 Longest Ordered SubsequencePOJ-2533POJ-1159POJ-2247POJ-108864 Humble NumbersHDOJ-142167 Brackets Sequence68 To the MaxPOJ-1141POJ-105069 Greatest Common Increasing Subsequence70 Human Gene FunctionsZOJ-2432POJ-108071 Bone Collector73 Piggy-Bank74
HDOJ-260272 I NEED A OFFER!HDOJ-1203POJ-1384悼念512汶川大地震遇难同胞——珍惜现在，
HDOJ-2191
感恩生活75 RobberiesHDOJ-295576 Cow Exhibition77 Battle Ships79 CoinsPOJ-2184ZOJ-362378 The Fewest CoinsPOJ-3260POJ-174280 Cow ExhibitionPOJ-21842. 2013年11月底（或12月初），会有招新的笔试和机试，测试一下感兴趣同学的基本数学能力和代码能力（不刷人）。
3. 2014年上学期会开一门《ACM程序设计》的全校性选修课，没有修过的请选修。 4. 2014年上学期初（3月份）学校举办湘潭大学程序设计比赛，请务必参加。
5. 2014年5月份会有ACM-ICPC湘潭邀请赛，有10个队的名额，部分优秀新人可以组队参加。 6. 2014年上学期4,5,6月会有月赛，请尽量参加。
7. 必备知识点的内容很多，大家可以按自己节奏制定相关的学习进度，基本上争取2年内完成上面知识点的学习。
8. 平时多寻找志同道合，合得来的同学一起学习。注意多交流讨论，相互学习和比较，为未来寻找合适的队友做好准备。
七、 加入湘潭大学ACM集训队
集训队将于2014年暑假成立，名额上限为30人。 满足以下条件者，可以申请加入湘潭大学ACM集训队。 1. 获得Regional铜奖及以上的同学
2. Codeforces（2014年比赛场次10场以上）第三高积分1600+以上的同学 3. Topcoder（2014年比赛场次10场以上）第三高积分1400+以上的同学 4. 通过暑假前的“2+1”选拔赛的同学
A. 暑假前进行，具体时间，地点待定。个人赛，每次3小时，5-6题
B. 第1、2场取2013级和非2013级（2012，2011）各前5名, 第3场取剩余名额人数 C. 第3场中，在至少做出一题的同学中，非2013级的女生和2013级男生题数+1，2013级女生题数+1且总罚时为0.
D. 比赛不重复排名（已入选的不计算排名），不累计成绩。
E. 第3场如果无剩余名额，不进行；如果条件1,2,3的申请人员超过10人，前两场对应减少录取名额数。
因篇幅问题不能全部显示，请点此查看更多更全内容