ACM课程结课总结_20200523课程总结

上了一学期的ACM课，跟着费老师真的学到了不少东西，感觉自己的思维变得开阔了，能解出一些自己以前看都看不懂的题，收获满满。下面是我对这学期所学知识点的一点简单的总结和我认为需要注意的一些东西。

最开始学习的递归算法说白了就是自己调用自己。运用从尾到头，从下到上的思维过程，能够用比较少的代码实现很复杂的问题，通过层层调用，从后往前运算直到运算到边界或结束条件，往后的数据就全部都出来了。
递归算法有两点需要注意：
1.注意递归的边界条件（结束条件）
2.递归公式
我认为最典型的例题就是pell数列和斐波那契数列了，记得当时做这个题的时候总是超时或者是运行错误，主要就是没注意好上面的两条
但是由于它需要层层实现，所以运行效率比较低，在后面的学习中使用的频率也比较低。为了提升效率，有时候会用到记忆化搜索，就是记录一些状态的答案，就可以减少重复搜索量，但是一个搜索结果必须可以建立在同类型问题的结果上，类似于后面学的动态规划的解决方法，区别在于记忆化搜索时倒着做的递归式动态规划

后面的贪心算法跟递归算法比起来就相对复杂一些了，使用频率可以说是相当高，我在打CF比赛时基本每场都用得到，能解决很多问题。贪心算法采用自顶向下的思维方式，每一步都做出选择，每一步都选择当前位置的最优解。
用贪心算法解题实际上需要考虑以下两点内容：
1.需要判断该题是否适合贪心策略解决
2.怎样选择贪心策略
最近看信息学奥赛提高篇，看到这样一个例子
在一个n*m的方格阵中，每一格子赋予一个值（权值），规定每次移动只能向上或者向右。现试找一条路径，使其从左下角至右上角所经过的权值之和最大。

这个题用贪心的方法求解时路径为1->3->4->6
用DP求解则是1->2->10->6
显然这个题就不适合用贪心算法求解，用贪心的方法解出来得到的并不是最优解，所以在解题时判断贪心是否适用就显得十分重要了。

之后学的分治算法，顾名思义就是把较大规模的问题分解成较小规模的问题，通过对较小规模问题的求解达到整个问题的求解，像方程求解等问题，分治算法在控制结果范围方面就格外好用。
大致步骤就是：分解->解决->合并
但是要想应用分治算法，首先要保证：
1.所需求解的大问题与分解的小问题具有相同的模式
2.子问题能够单独求解，且子问题间没有相关性
3.具有终止条件（当问题较小时可以直接求解）
其实还需要子问题合并成原问题的过程不能太过复杂，否则就没有起到简化过程的效果了。
比较广泛应用的我觉得还有快速排序了，能比普通排序快数倍，虽然写起来有点麻烦，但是提速效果杠杠的。

emmmm说完分治算法，接下来就是最难搞的动态规划了，说到这里我就头大，这里真的对我来说太有难度了。动态规划实际上是将总过程分成若干个互相联系的阶段，在它的每一阶段都需要做出决策，从而使整个过程达到最好的活动效果。它与贪心不同的地方是它的各个阶段决策的选举不是任意确定的，它依赖于当前的状态，又影响以后的发展。无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略，即构建最优子结构，此为动态规划的最优化原理。其次还要注意动态规划的无后效性原理，即某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。
关于动态规划，我觉得寻找最长上升子序列这种题目算是最简单的一种了，虽然当时学起来也是很费劲，花了几个早上把代码硬生生背下来了，但是背下来之后就理解了，之后再做这样的题就舒服多了。
动态规划的一般套路：
1.把问题分解成子问题
2.也就是DP最最最重要的部分，就是找状态转移方程和边界条件（边界值），这就是我永远迈不过去的坎。
动态规划其实就是把每一步的结果都保留下来，这样就可以防止重复计算，减小时间复杂度。
DP的知识点非常丰富，像区间DP，有点类似于分治算法，就是通过求解一段区间上的最优解。主要是通过合并小区间的 最优解进而得出整个大区间上最优解的dp算法，主要运用三层循环嵌套来解决问题。

算法之外，这学期还简单学了数据结构，包括stack，queue和vector等，不过我学的数据结构非常的菜，只停留在理解功能，能够简单运用阶段，稍微有一点点难度的题我就做不出来了，最短路与最小生成树学的时候我就理解的不多，做题量也不多，能做出的题就纯粹靠缘分。并查集用于处理集合之间的关系，即动态地维护和处理集合元素之间复杂的关系，我觉得这部分内容应用的还比较广泛通过初始化，寻找根节点编号&&压缩路径，合并两个集合，判断元素是否属于同一集合来合并两个元素各自所属的集合，在树中应用的很多。

数论的东西很多很杂，但是自从学了数论之后，我发现很多知识在codeforces比赛中都用得到，很多方法很巧妙，省时省力，我也通过数论了解到了打表这个方法，我觉得简直不要太好用，找不到规律的时候，打表真的可以提供一股神奇的力量。不过做数论题的时候，我还是经常思路局限，总是尝试暴力解决，过不了的时候才会动脑去思考其他解决途径。

其实这学期学的内容非常多，我这里只写了一些我认为重要的或者我经常学不懂的地方简单写了一下。下面是我学ACM时候的一些感受。

大概是从上学期11月左右吧，我开始接触ACM，觉得搞ACM是一件很酷的事情，开始自己在没事的时候偶而刷刷题。那时候的周末会有学长学姐来给我们上课，虽然会上一上午的课，但对于刚接触程序竞赛的我来说感觉很新鲜很有趣。我会提前半个小时到教室占位置，坐在二三排认真记笔记，学的不亦乐乎。那时候上课的人还很多，当时还听学长学姐们说到最后也就剩一二十个人，觉得蛮不可思议，心里却还是自信满满的想着，如果只剩一二十人，我也会是那1/20。刚开始是在信息学奥赛的一个测评网站刷题，题很简单，几分钟就能做出一个题，练手速的同时感觉很有成就感。但是新鲜感毕竟只是新鲜感，很快我的热情就减了大半。
题开始变得有点难度，经常卡在某一测试点死活过不去，课也开始听的迷迷糊糊，跟不上节奏也不愿课下复习，我的生活跟ACM唯一的交集就只剩偶而抽出的少得可怜的时间来刷一刷信息学奥赛的题。大概十二月中旬吧，突然说要收信息学奥赛的截图。那段时间有点慌了神，基本除了很重要的课以外的其他时间都在刷题，虽然效率很低，但好歹一直坚持刷题到交截图的那个晚上。
那一天之后，我把ACM暂时放了放，生活放松了很多，但却有点空虚。几天后，大概十二月底，听说要举办ACM新生赛，我挺激动的。预备赛时我出了三个题，本来还挺满意，侧眼一看，我侧后方的同学桌前贴了起码五六个气球，信心瞬间被压垮了，一中午都很紧张，也没有午休好，紧张兮兮的就上了赛场。被幸运之神眷顾了，下午即使我的精神不算太好，但忙活了一下午也算取得了令人满意的成绩。
新生赛过后，因为临近期末，ACM也没有多余的任务，我又把ACM往后放了放。期末结束的前一天，任务下来了。我深深的烦躁，又不忍放弃。慢慢的，在寒假里，一个接一个的任务，我眼睁睁看着群聊人数不停的减少，自己在硬着头皮咬牙坚持，功夫不负有心人，一个寒假的时间，我学会了几种简单的算法。我很开心看到了自己的进步，觉得自己的努力没有白费。
学期开始，我顺着选修了ACM课。其实当时心理有一点点害怕，毕竟很早之前就听说过费老师的严厉，害怕自己挂科，也听学长学姐说到过ACM的压力，但还是试着学下来了。经过一学期的接触，我发现费老师真的是一位特别好的老师，能大学里碰到这样一位认真负责的老师真的是我的荣幸。费老师会跟着我们一起学习，认真备课，也会教我们努力尝试新事物。记得有一次打完比赛十二点多，费老师在群里放了一个我们比赛数据的表，当时已经接近凌晨一点，费老师在背后陪我们一起比赛，其实心理是特别感动的。费老师会给我们讲很多励志的话，鼓励我们一直向前。
因为寒假学习了部分知识，所以刚开始的学习比较轻松。贪心算法学起来不难，但是做题有时候会没有思路，这也算是我学算法的第一个小坎吧。我觉得对我来说最难的部分就是动态规划了，要么就是找不到状态转移方程，要么就是临界值不会写，还有各种各样奇奇怪怪的问题反复在我身上上演，把我弄得焦头烂额。好在刷题刷的到一定数量了，其实大致套路也总结出来了一些，虽然我到现在为止做DP题仍然很慢很费时间，但是认真思考还是能有一些思路了，或者有些时候题虽然没读懂，但是能写出来代码了。记得当时听学长学姐和老师都曾说过，要把所有的经历都放在ACM上才能学好，当时的我并没有把这个当回事，现在想想当时真是天真。堕落几天可能就已经跟不上节奏了，每一周都有新的任务，每个任务都需要新的知识点，新的思维方式，不停做题才能跟上别人的脚步。
其实说到这门课，不得不提的就是codeforces了，这个网站真的有点折磨人，主要是他的比赛时间总是在半夜，每次打完之后都会让我的大脑很兴奋，每次打完比赛都得到两三点才睡得着。不过，codeforces确实增长了我的比赛经验，掉分涨分又掉分的经历让我明白无需在意一时得失，学到东西才是最重要的，打了接近20场，我比赛时的心情也从紧张兮兮变得放松了很多，出题速度和出题数目的增长让我明显的感觉到了自己的进步，让我对ACM有坚持下去的欲望，更有信心坚持走下去。虽然我现在的CF成绩还是非常烂，但是我相信，只要我坚持着走下去，总有一天我会把分数打上去。

记得当时学期刚开始的时候，每天的课都很满，上网课一天下来感觉比正常上课还要累。晚上还要做ACM的作业，经常忙一个晚上甚至一个题都做不出来，很心累。学期中间的时候又有一阵子很懒散，天天啥都想干就是不想学习，那一阵子作业做得也不多，很堕落，后来课慢慢减少，这种情况才好转了些。ACM容不得偷懒，我会在接下来的日子努力克服我这学期的这种懒散，抽出时间多参加比赛，找出自己的不足，增加经验，更好的为省赛做准备。
其实我觉得我能走到现在，硬着头皮坚持到现在，也挺不容易的。ACM并不是一条好走的路。我也曾经无数次想过放弃，曾经被各位大佬压得喘不过气，为几个一直做不出来的题暗自烦恼睡不着觉。我经常感觉自己被碾压的站不起身，ACM里大佬太多太多，优秀的人也还在不停地努力，这就逼着我不停前进。我庆幸我接触到了ACM，让我的大一变得充实而有意义。我渴望能在这条路上走得更远，我也相信自己一定能坚持下去！
我一直坚持着的一个目标也是想冲进省赛，我渴望能拿到一枚奖牌，即使是铜牌，对我来说也是非常不容易的，非常珍贵的。我想给自己的努力一个交代。现在的疫情状态，省赛也是遥遥无期,这样可以给我更多的准备时间，我能够学到更多知识，以更好的状态向省赛冲去！

I will keep on fighting！