ACM 杂谈

华师ACM年历

11月-12月

新生赛网络赛、新生赛现场决赛

新生赛是唯一一次的个人赛且中文题目的,其余标准赛制相同–三人团队,英文题目。

3-4月

华师校赛初赛、校赛现场决赛

5月

广东省省赛

选拔6-8支队伍参加,会优先大一学生,往届大一一般有3个左右名额

8月-9月

开始进行亚洲区域赛的网络赛,一般会有6-9个赛区,每个赛区都有一场网络赛,时间一定是周末,每周一场偶尔两场。这决定了我们能否参加这个区域的亚洲赛。排名只看每个学校最好的队伍,在所有学校中(约400个)需要排名前80。一般来说就是所有队伍(约2000支)中的前200名。

10月-11月

ICPC+CCPC各个赛区的比赛,往届一般能拿到4-6个名额,大二同学可以争取到2个,出战亚洲赛,积累经验。大三大四的有经验,目标夺牌。

(轮回——)

OJ

OJ平台相当多,除了广为人知的HDOJ,POJ外,下面讲几个我熟悉的:

http://www.51nod.com  初学者建议在51nod刷水题(0级-2级),锻炼编码能力,大神可以直接参加每月的算法马拉松~

https://vjudge.net  暑假的多校联训在vjudge上进行,难度与亚洲区域赛相当,当作亚洲赛前训练再好不过。 某些专题题集也是相当的不错~

http://codeforces.com 俄国OJ,里面有按星级的往年各赛区的题目集,一般两星就是校赛难度,三星省赛,四星区域赛~专题也是相当的完善,计算几何就几百道题)))。有实力的dalao可以每周打contest冲Rating。据说Rating1800+区域赛就能拿奖(?).

打ACM有什么好处?

这是新ACMer最常问的问题,光是“打一下”ACM基本没有太多好处,应该问”把大量专注时间花在ACM上面有什么好处“。好处有很多,具体来说:

  1. 很多
  2. 竟在不言中
  3. 很多
  4. 夏虫不可语冰
  5. 还有很多

在下希望新ACMer先不要带功利的眼光看ACM,否则一时的失利有可能让你状态大受影响甚至半途而废。ACM是一个学习曲线比较陡峭的比赛,所谓强者刷题速度快-能刷更多题-更强-正反馈;弱者刷题速度慢-刷题少/不想刷-仍然弱-负反馈。所以关键是你趁早动手专注于此,比别人更快一步进入“陡峭坡”。

提升实力

一开始先刷水题,熟悉编码惯用套路,把上面的“基本操作”弄熟悉,然后可以进军在各大OJ上刷题,题量超200之后大多套路都应见过一些,一些领域的板题也应该见过,就算自己写不出至少也在看过题解之后自己码过一遍,这个时候可以进入专题练习,在vjudge和codeforce上刷专题,在理解的同时积累自己的模板。如果你把某专题也刷的666了,可以看一下相关论文,看看一些最新的算法理论成果,毕竟每年ICPC都会出点论文题,我比较弱,看的是往年国家集训队论文,dalao们有高见可以推荐推荐。如果你这个阶段都666了,那我也没什么好说了–因为我也没到那个境界hhh。

习惯

好的习惯很重要,不过习惯好不好这一点应该因人而异。我认为的话:

  • “AC了再睡”:养成做题习惯,我是每天晚上睡觉前做一题,如果半小时内AC了那就再做一题,AC了再睡,实在不行看题解自己码一遍。
  • “独立思考“:这一点是我的弱项,每次做题急于求成,不懂很快看题解,没有自己的思考,下次同类题还是gg,dalao们在这点上做的比我好多了,他们遇到题不会的时候,也不会很急于把题目做出来,可能每隔一段时间又拿出来想一次,总有一天想通了,之后这一类型的题目基本上也就没有什么问题了。
  • “做有意义的题”:水题在你刷了一定量的题后不宜做太多,应该做你最近主攻的专题知识点相关题目,只做自己会的,很难有所提升。
  • “团队配合”:每周抽空一起刷套题,只用一台电脑,互相加深理解慢慢磨合,在赛场上才能做到“会做的都AC”。否则时间紧的时候为了抢键盘大打出手也不是没见过)

关于模板

比赛场上模板很重要,比赛时某些题目你有自己的对应模板能节约非常多的时间。但是需要强调一点,是要“自己的模板”,别人的模板总结的再好也是别人的,要慢慢转化为自己的板。只有别人的板,某种意义上说,这是你没有搞明白的一种表现,而ICPC极少出线板题,一般都需要针对实际问题对模板进行修改,如果是别人的板,修改起来将极其麻烦。即使自己整理了模板,以后遇到直接抄,也会导致自己忘记了具体方法,所以平时练习尽量少依赖模板。

一般dalao都有自己的一套总结,我自己的杂板比较多,比较乱,就不拿出来让dalao笑话了,下面介绍dalao的模板。

师兄oykfzyj板kuangbin板  灰常全~。

专题版的话

jerrybond的计算几何模板用起来很舒服

eecrazyoyk师兄的图论也很666

关于比赛

比赛场上不同阶段:

  • 热身赛请用各种姿势调戏评测姬,深入了解评测姬的身体状况,如一秒能跑多少循环,是否有long double或__int128;RE,MLE等能否正确返回,printf和cout关闭同步哪一个更快一些等。键盘请多敲一下–部分程序猿dalao离开了自己的机械键盘速度就大幅下降。
  • 早餐吃好,比赛期间发的食物不是给你比赛时吃的,除非你已经放弃了。
  • ICPC比赛之前会将每题的时限告诉你,可以根据题目时限判断水题,确定做题策略。
  • 简单题的一血相当难,需要打代码是顺便就在脑内编译运行结果打完编译一下没问题立刻就交,测试样例的时间都没有,如果是为了牌,就没有必要抢一血,问问当当测试的时间总比20分钟一次的罚时要少。
  • 交完一题立刻直接提交去打印,换人上机。为什么?因为评测姬也会累啊))
  • 开始半小时后就可以看榜来决定做题顺序,先做多人做出来的,必须啊。
  • 抗压–你座位的八个方向总有清北上交等的强队,比赛时看着他们突突突地AC气球一个接一个挂起来自己这边还是while(1){return WA;},那个气啊,嘴唇都给你咬破–明确一下,你要拿牌并不需要打赢他们,打赢的是其他–参赛的60%,或是30%,10%….
  • 最后一小时封榜之后临危不乱,一般根据2个小时金牌区解题数=5个小时铜牌区解题数来判断自己队伍在哪个位置,调整策略。
  • 最后关头实在做不出来可以试试大力出奇迹–莫队暴力跑一波,xjb剪枝强行提交,想法算法复杂度超时也上一波,说不定数据弱呢,嘿嘿嘿。

小细节:

  • 有想法后顺便把时间空间效率考虑进去–你说码半天TLE了才发现要改进等于推倒重来那多尴尬。
  • 初始化–被坑过好多次后才学乖的我,,,都是泪。
  • 提交时多花两秒钟确定题号和文件路径–一旦因为这个出错,损失时间很可能不止一个小时。
  • 二位数组行列下标弄反–赛后花3小时才debug出来的我眼泪留下来。
  • 怎么写都超时,最后看别人的代码:打表。数学题:一言不合打个表。
  • n=10^18 ?找规律走你。
  • 输入输出挂,方见恨晚。
  • 每道题请有两个人读过,因为读错题意直接错失AC,哭瞎。
  • 数组越界,题目n是1e6,但是题目里可以有相加减的就要2e6(睁眼瞎)1e6是有7个数哒!和10-16号有7天一样!
  • 先用scanf(),再用gets()会读入回车,用输入挂的时候注意一下。
  • 除了个别java极其有利的情况(例如字符串处理,大数运算),不建议使用java,真的慢出shi….
  • 系统函数参数是int还是double很关键。类型转换也是大坑~
  • 精度问题= =、

大粗节:

  • 学校报销事宜–基本没有赛区花费低于5k,不报销,gg
  • 赶飞机–某队队员离飞机起飞90分钟才开始从华师到机场(约60mins车程)结果..gg
  • 肠胃/水土不服:总会有的,即使你不乱吃,肠胃不好很影响状态,gg
  • 看清楚规则:由于不知而被取消资格,gg
  • 据说,赛前去找同学相聚的以及喝拿铁的人gg概率+99%。

“ACM无用论”

之前见过有些人会说这个竞赛“没有创新”,“做重复的工作”,“没有出路”,“以后根本用不着”。有些人每天面对追求创新的“科研”,看到一个题目都是别人已经解决的问题的竞赛,必然会觉得这是在做”重复的工作“,这是可以理解的,但实际上ACM对你的算法设计与思考能力都有极大的提升,这是大部分“创新科研”需要具备的素质,当然如果一开始就确定要搞研究当然一早进实验室跟导师看书看论文更实在。至于“没有出路”、“以后用不着”的说法,可以说大部分的商业程序代码确实很少涉及到高效算法和一些特殊的数据结构,这是实际情况,因为并不是所有的公司的产品都是理论性很强的产品,就像造山寨手机的人不需要懂太多芯片设计等方面的知识,只要会把大公司制造的手机芯片拼装起来,然后装一个外壳就可以了。“高效算法和一些特殊的数据结构”已经由IBM、微软等大公司解决了,制造成了一些类库、应用服务器、数据库服务器之类的“零件”,商业程序开发者只要读懂这些零件的说明书(文档),然后把这些零件按照需要拼装起来就可以了。这我们一般戏称为“搬砖”,以后如果只做搬砖工作,算法上的似乎确实用不着。

题型

ACM比赛题目类型如下:

  • 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 (杂题)

知识点

算法思想:

(1)“基本操作”:STL、枚举、贪心、递归、分治、递推、模拟、构造、位运算、常数优化;

(2)动态规划:最长公共子序列、最长上升序列、背包九讲(0/1、完全、依赖、分组、泛化物品)、四边形不等式优化、斜率优化、单调队列(1D\1D)、数据结构优化(线段树优化、堆优化、左偏树优化)、树形DP、自动机DP、数位DP、状态压缩DP、插头DP、广义插头(最小表示);

(3)搜索:DFS,BFS,记忆化搜索,优化与剪枝,双广,A*,IDA*,跳舞链。

数据结构:

(1)简单数据结构:链表,栈和队列,串,树和二叉树,图,排序与检索

(2)树形结构:线段树,树状数组,字典树,伸展树,左偏树,动态树,lca&rmq,划分 树,SBT。

(3)字符串:kmp,AC自动机,后缀数组,最小表示法。

(4)其他:并查集,散列表,块状链表,双向链表。

图论:

(1)最短路:dijkstra,bellman-ford(spfa优化),floyd,heap+dijkstra ,差分约束,第K最短路;

(2)生成树:prim,kruskal, 度限制最小生成树, 最优比率生成树, 次小生成树, 最小树形图,生成树的计数,树的划分,树的枚举;

(3)匹配问题:二分图的最大匹配 (匈牙利算法),KM,2-SAT,同构;

(4)网络流:最大流,最小费用最大流,最小割模型、网络流规约;

(5)其他:拓扑排序,双连通分量,强连通分支及其缩点,图的割边与割点,无向图、有向图的最小环,欧拉路径,哈密顿路径,平面图,分层图思想,偶图。

数学:

(1)数论:素数和整除问题,进位制,同余模算术,整数因子分解,GCD,扩展欧几里得,求解模线性方程,中国余数定理,元素的幂,RSA公钥加密;

(2)组合数学:加法和乘法原理,排列组合,递推关系和母函数,容斥原理,抽屉原理,置换群与Polya定理,MoBius反演,偏序关系理论;

(3)计算方法:二分法求解单调函数相关知识,三分法求解单峰(单谷)的极值,矩阵法,迭代逼近,高斯消元法,随机化算法,0/1分数规划;

(4)高精度问题扩展:求倒数,求乘幂,求开方,求对数,二分快速方法,对指函数,三角函数,数值计算的优化;

(5)其他:博弈论,线性规划,整数规划,概率问题,多项式与快速傅里叶,数学思想与方法的综合运用(构造,猜想,归纳法,反证法)。

计算几何:

(1) 判断线段相交,判断直线相交,判断点是否在多边形内;

(2)凸多边形面积&重心计算,求外接圆与内接圆;

(3)求凸包,最近点对问题,最远点对问题;

(4) 点集或图形集合的最小覆盖圆,点集或图形集合的最小覆盖矩形;

(5) 矩形的交与并(扫描法);

(6)三角剖分,费尔马点的计算,Pick定理;

(7)常用几何公式。

别被那么多的知识点所吓倒,相信自己某知识点做两题就能理解了~并且ACM是团队比赛,每个人擅长其中一部分即可

(看心情持续更新)