ACM如何入门,ACM竞赛需要学习哪些算法?

时间:2024-11-07 08:13:54

#################成绩##################

大一:2017年4月份”玲珑杯“河南工业大学2017年ACM程序设计大赛暨河南高校邀请赛,获得银奖
2017年5月12日在哈尔滨师范大学参加第十二届黑龙江省大学生程序设计竞赛,获得铜奖。
2017年6月10日在我校参加南阳理工学院举行的第三届程序设计大赛,获得银奖
大二:2017年10月29日在西北工业大学参加第42届ACM国际大学生程序设计竞赛亚洲区域赛(西安),获得铜奖
2018年4月1日参加河南省第九届蓝桥杯—C/C++程序设计竞赛A组,获得第一名。
2018年5月27日参加信阳师范学院举办的河南省第十一届ACM程序设计大赛,获得金奖(第五名)。
大三:2018年9月28日在东北大学秦皇岛分校参加第四届中国大学生程序设计竞赛(秦皇岛),获得铜奖
2018年11月4日在中国石油大学参加第43届ACM国际大学生程序设计竞赛亚洲区域赛(青岛)获得银奖 (该银奖打破了我校ACM-ICPC的历史记录)
2018年11月11日在北京大学参加ACM-ICPC国际大学生程序设计竞赛亚洲区北京站(2018),获得铜奖
2018年11月25日在哈尔滨工业大学(深圳)参加第四届中国大学生程序设计竞赛总决赛,获得铜奖 (我校首次在ACM-CCPC-Final中拿奖)

2019年3月9日在我校参加南阳理工学院举行的第四届程序设计大赛,获得第一名。

2019年5月7日参加黄淮学院举办的河南省第十二届ACM程序设计大赛,获得金奖。(最后两小时连过四题,绝境翻盘)

(图片拍摄于2018年年末)

一年铜两年银,也算运气非常好的了。并且大三参加的4场区域赛也全部拿奖(尤其是2018-ACM-ICPC青岛站中,拿到银奖,破了学校记录,拿到牌子后的下午,又看到IG 3:0拿下英雄联盟S8全球总冠军,那种喜悦已经难以用言语形容)(来到2018-CCPC-final,我们的目标就是冲冲冲,经过发挥的出色,最终挤进前60名,拿到铜牌),对我来说绝对是收获满满,无憾退役。

###################################################

下面这些内容写给那些想参加ACM竞赛的人,前提是自己学校ACM发展的不理想(或者就没有ACM这个东西)。

我校的NYIST-ACM交流群(QQ):48719519 
(2021.11.20更新:适合小白、想参加蓝桥杯,ACM省赛,ACM区域赛,准备面试编程题的同学)

(因为有些同学私信我,只参加省赛需要学到什么程度,参加区域赛需要学哪些算法,只想参加蓝桥杯和准备面试编程题需要学哪些算法,针对这些问题,我更改添加了新的内容,希望可以满足更多的同学的需求)

##################蓝桥杯如何准备2022.10.11更)##################

参加了一下第十三届蓝桥杯,蓝桥杯困难数据难度很大,弱数据依旧是暴力就行,现在这个蓝桥杯我觉得是看得分策略你怎么做,花了时间要是做不出来题目,那真是亏大了。不要死磕困难数据,每道题如果都可以暴力通过弱数据,基本上省二,省三就稳了。冲省一的话,需要在前面的基础上通过一道或两道强数据即可。有些人说蓝桥杯的奖没有什么含金量,我非常排斥这句话,首先蓝桥杯是面向大众的,而ACM注定是一小部分人的比赛。零基础通过一两个月的努力就可以拿到蓝桥杯的省奖。既学习到了很多知识,奖项又可以丰富简历。而ACM周期长见效慢,得奖的门槛很高,含金量也高。蓝桥杯周期短见效快丰富简历的不二之选,ACM是一个周期长难度大,难度与收益成正比的比赛。这两者各有各的特点,大家根据自身情况有目的的进行选择。

下面的文件是之前手写的60道题目的答案与解析,给别人准备蓝桥杯用的,他们经过一个多月的学习也是获得了自己满意的成绩。免费给大家分享出来(零基础也可以看懂)。学完这些题目,你的编程能力绝对上一个台阶。

链接:/s/1AT3QpVAIt0FJw6PU8BCR1Q
提取码:nnnl

##################适合刷题的四个网站##################

虚拟OJVirtual Judge适合有一定题量(100+道)的想参加ACM区域赛和省赛的同学

牛客网牛客网适合小白入门、为编程面试刷题的同学

力扣LeetCode):(为编程面试刷题的同学(待更)

Codeforces(简称CF)Codeforces适合参加蓝桥杯和面试的同学,适合想训练逻辑思维能力的同学(该网站的题目可以有效训练逻辑思维,并且该网站的简单题目不会涉及到算法)

###################牛客网的使用方法######################

小白入门编程推荐:在牛客网首页点击“发现”“竞赛”,然后点击“题库”,所属平台选择”牛客“,难度选择“一星”,推荐先做通过人数多的题目。题量达到50+以上就算是有了基础编程能力

编程面试刷题推荐:在牛客网首页点击“题库”--->“在线编程”,---->“面试高频Top榜单”,先做高频简单题目,有一定基础之后再做中等题目。题目思考10+分钟没有思路就看讨论区,或者搜该题目的****题解,学不会看不懂就先放弃该题目,过段时间再做该题目。算法要求:用到什么算法学什么算法即可,根据遇到的题目去学习算法。该算法学不明白就暂时放弃,过段时间再看。

##################Codeforces的使用方法###################

1.首先右上角注册账号(看不懂英文的可以用Google翻译、有道翻译),记得在邮箱里点击链接才能注册成功。

2.在首页点击最上方目录中的PROBLEMSET,每道题目后面的数字是通过的总人数,你可以完全根据该人数的大小来判断该题目的难度。(15000+——简单)(10000+——普通)(5000+——难)(0-5000——非常难)

3.点击一道题目,你可以看到第二行的第二个SUBMIT是提交,点击之后会入到提交界面,选择对应的语言,C/C++用G++17提交即可

页面就是所有的提交信息,根据自己的名字,找到返回结果(AC or Wa),点击开头的编号,就可以查看代码和后台数据(该网站的一大特色,也可以看其他人的代码)

(注意:该网站的题目数据非常强,暴力往往是不可取的,需要合适的复杂度)

以上适用于小白入门编程题,参加蓝桥杯,准备面试编程题的同学(遇到什么算法就自学什么算法即可,不需要专门刷某个算法专题)

—————————————(分界线)————————————————

以下所有内容主要适用于参加ACM省赛,ACM区域赛的同学

5.该网站的比赛一般是在晚上22:35——24:35,偶尔有下午的比赛,有条件的可以参加。

新手推荐做div.3,

一般推荐做div.2,

参加ACM省赛的同学水平需要达到div.2的C及以上

参加ACM区域赛的同学水平需要达到div.2的D及以上

6.日常训练思维的刷题网站。

##################虚拟OJ的使用方法###################

1.注册/登陆

2.点击第一行的"Contest"——>点击"All"和"All Contests"——>在Title中输入kuangbin带你飞——>在最后一列Owner输入"kuangbin",回车,这些是所有比赛常用的算法,每个算法专题内有简单题,有困难题,根据你对自己的要求做相对应难度的即可(通过人数 约等于 难度)。你可以直接在该专题内做题,提交等。也可以点击Clone,复制一个相同的比赛用于个人训练或者团队训练。

(kuangbin的训练专题内的题目都是经典,难度从低到高)

3.其他很多功能,你可以自己慢慢摸索

该网站的主要用途:用于个人专题训练,查找往年ACM-ICPC/CCPC比赛进行团队模拟训练,需要学习哪些算法,都可以搜索到他人的公开训练赛,进行算法专题训练。

##################算法需要学习哪些(以下都是我的个人见解)###################

建议:以下部分算法分为两个学习阶段(初学,进阶)(初学需要学会算法并去相应的专题刷一定数量的题目即可(入门题做完即可),等到部分算法都完成了初学阶段之后再考虑个别算法的进阶阶段,不是所有算法都要精通,根据你的做题情况,比如你经常在比赛训练赛中遇到动态规划问题,每次都做不出来,那就有必要完成动态规划的进阶,比如你学习了AC自动机算法,除了在专题中就没见过这种题目,那就没有必要完成该算法的进阶)

新算法怎么入门:学习算法不是学习完算法再去做题,而是先去做对应的简单题,遇到不会,去找博客****搜题解,搜算法思想,一定要带着问题去学习算法,看不懂就换一篇博客,记得手动模拟一下代码,理清楚每一行代码的意思,理解代码,背写代码也是有必要的

简单算法(0-7天),一般算法(7-14天)

(快速幂,难度1)(二分,难度1)(贪心,难度2)(大数模拟,难度2)(gcd最大公约数,难度1)(并查集,难度3)(冒泡排序,难度1)(桶排序,难度1)(最小生成树,难度3)(哈希,难度3)(逆元,难度2)(结构体排序,难度2)(优先队列,难度3)(素数筛法,难度2)(线性筛法,难度2)(dfs,难度4)(bfs,难度3)(快排,难度3)(离散化,难度3)(01背包,难度3)(动态规划dp,难度4)(最短路,难度4)(kmp,难度3)(线段树,难度4)(博弈论,难度3)(二分图匹配,难度4)(常用STL:queue,map,set,vecter)

(辛普森积分,计算几何等会用模板即可)

(以上为省赛必备算法,都是基础的,简单的算法,紫色标注的算法有必要进阶

(矩阵快速幂,难度3)(树状数组,难度4)(trie,难度4)(AC自动机,难度5)(网络流,难度5)

(以上为区域赛必备算法,难度适中,红色标注的算法有必要进阶

算法模块:数论,图论,字符串,数据结构,动态规划等等

擅长哪方面的算法就精学哪方面的算法,例如:我最擅长DP,DFS,下面算法都是我额外学的。

(数位dp,难度4)(期望dp,难度3)(状压dp,难度4)(区间dp,难度3)(单调栈,难度4)(数论,难度4)(莫队算法,难度3)(模拟退火,难度3)

队伍里的三个人,尽可能保证每个模块都有人专门负责精学。

有机会的话可以参加牛客的练习赛,小白月赛,和其他高校的同学切磋一下

通过训练赛积累经验,明确队伍分工合作。保证1+1+1>3

################################################

(以下写于2019-01-02:我的整个ACM生涯流程)

我是2016级的学生,从开学后的国庆节开始从零接触ACM。

10月1日-10月7日(学习C语言基础,for,if else,while,scanf,printf的用法,在HDU第11页做一些简单的题目,做个50道左右)
10月份(充分利用课余时间坚持每天做4道题以上,周末翻倍)
(自己思考30分钟还没有思路,就百度搜博客学习别人的代码,看博客看了一天还迷迷糊糊的题目就扔掉不要再纠结了(以后有机会拿出来再做))。
11,12月份陆陆续续接触了一些简单的算法,比如快速幂(难度0),大数(难度1),并查集(难度3),二分(难度2),简单01背包(难度4)等等。(不会的就搜博客,自学即可,学不会的先放一边,过段时间再看)

大一寒假留校学习一些稍难的算法(深搜DFS,广搜BFS,最短路),寒假集训可以留校到春节前一周。(个人认为BFS广搜比DFS深搜好理解,搞不明白DFS深搜递归过程的,可以下载一个 机器人点灯  小游戏,玩到后面你就明白什么是递归了,跟DFS递归是差不多的道理 ,留校时间学习搜索或者最短路(学会一个就OK),学有余力的可以同时学习两个)
大一第二学期3月份:复习一下学过的算法,并深入学习搜索,最短路。
4月份并开始按顺序接触dp,kmp,RMQ,矩阵快速幂树状数组线段树,容斥(难),欧拉函数(难),字典树,网络流,AC自动机,这些算法每个需要1-2周,这段时间可以试着参加自己省份的程序设计竞赛,其他省的也行。(可以出去参加一些简单的比赛,蓝桥杯的c/c++程序设计B组也行,主要是练练手)
日常要在这个网站上Codeforces做做题目,出的非常有区分度,先从A,B题做起,C、D就比较困难了。(练思路)(我感觉有div2,D的水平,区域赛拿个铜是没问题的)
大一暑假:(当然是留校学习啦)
集训时长约50天左右,一般会持续到开学前一周集训才结束(留一周左右时间可以回趟家),暑假有多校联赛(很多的ACMer都会来参加这个比赛),为这一年的亚洲区域赛(ACM国际大学生程序设计竞赛)做准备。多校联赛会在HDUOJ(杭州电子科技大学的HDU Online Judge System)举行,一共10场比赛,每场比赛大约参赛队伍800以上。通过这10场比赛的做题,补题(只补那些通过的人比较多的题目,补力所能及的题目),对实力会有很大的提升。

9月份有各个地方的网络赛,可以打区域赛名额。
10月份-12月份如果有条件并机会的话就可以去试着参加,参加区域赛。

大二开始后就要接触一些更难的算法了,并且以前学过的算法要再学的深一点了,

比如:区间dp,概率dp,dp是需要大量练习的
网络流,有最大流最小割定理等等,(网络流难的是建图)
最短路,树的直径,最近公共祖先等等
数论里的要学的东西就比较多了,比如:容斥,欧拉函数
计算几何也要做一些题练习练习。
各种树,线段树,主席树,树状数组等各种数据结构
矩阵快速幂熟练使用。
博弈论等等。

大二暑假同上(大一暑假)。

大三:一直进行往年的区域赛模拟训练,好好准备区域赛即可!(牛客网上有很多区域赛线上同步赛,不要错过这些训练机会)

在这个网站上(Virtual Judge)可以搜到往年几乎所有的比赛,区域赛模拟训练大约两天一场,(时间9:00-14:00)(一周2-3次)课余时间多多练习Codeforces 、D题。