锐客网

  1. 首页 > 睿知 > it技术 > >

ACM节课课程总结

决定选课的过程 ACM课程就这样结束了，坚持一下就熬过来了。起初了解到这个课程，问了学长和其他同学对这个课程的看法，都是说难，花时间多，容易挂科什么的。我选课的心不断动摇着，十分纠结。纠结的原因就是，我本身是想着去学东西的，又害怕挂课所以犹豫不定。别人说的情况，对于你自己身上就不一定一样了，你自己都没经历又凭什么去否定呢？因为这次的特殊情况，迟迟还没到往常退课的时间，所以有跟着学习一段时间让自己去判断是否要去退课。对于我来说，在大一才开始接触电脑的我，电脑一些常规的东西都不懂，是真真正正的小白。所以跟着老师一开始学习的递归，贪心算法这段时间，虽然课上有些听不懂，但是课下还是能琢磨出来的。在第六周真正迎来对于是否选择这门课程的的“命运转折点”，补退选开始，因为这个时候老师已经教到了动态规划，一开始接触这个东西，说实话对于我来说是很懵逼的，根本不知道到底是怎么回事。再加上有好多人都退课了，在这个氛围下，我就十分纠结了，最后我还是战胜了自己，我想学知识，不想”混日子“。
对于有犹豫不定的，如果你是想着提升自己，那就不要怕难，怕挂科。你不一定有过人的天赋，但是你选择了这门课，就一定会有收获的。想学到知识，哪里有不花时间的？对于这门课来说全是新知识所以才会觉得难。因为你要上课花时间去接受，下课还要花很多时间去理解，还要花时间能熟悉并且运用。如果想着提升自己那就不要再犹豫了。
课程学习的模块 1.递归算法
基本思想：层层分解，大问题------>一个或者多个小问题；
关键：
递归定义：问题向边界条件转化的规则。
终止条件：所描述问题的最简单情况。
步骤：
1.分析问题，寻找递归。
2.设置边界，控制递归，找出终止条件。
3.设计函数，确定参数。
2.贪心算法
基本思想：层层分解，寻找最优解。
关键：寻找贪心标准，寻找局部最优解。
步骤;
1.判断是否符合贪心策略。
2.寻找贪心标准，寻找局部最优解。
3.设计函数，确定参数。
3.动态规划
一、具有的特征
1.问题具有多阶段性决策的特征
2.每一阶段有相应的“状态变量”。
3.不同决策导致下一阶段不同的状态
4.多个阶段的最优解的递归，子问题与原问题有同结构。
阶段：按空间或时间顺序对问题的求解划分阶段。
状态：不同事物有不同性质，用不同的状态来刻画。
决策：对每个阶段做出某种选择性的操作。
状态转移方程：用数学公式描述与阶段相关的状态间的演变规律。
二、解题步骤
1.是否具有动态规划特征。
2.分阶段
3.建立状态转移方程。
4.找边界条件。
5.将已知边界条件带入。
6.递推求解。
4.背包问题和区间dp属于动态规划
区间dp常见模型
第一种模型就是大区间分成最优小区间求解
第二种模型就是根据要求可以把区间分成[i+1,k-1][k+1,j]情况
第三种模型就是只考虑左右边界情况的模型
背包问题分为：01背包问题，完全背包问题，多重背包问题，分组背包问题。
01背包就是最基本的背包问题，特征就是每种物品仅有一件，可以选择放还是不放。代码第二重循环就是从大到小。这种例题就多了去。
完全背包题就是升级版01背包，它的特征就是每种物品可以无限件使用。代码第二重循环恰恰相反是从小到大。
多重背包问题。可以通过条件转换，化为多重背包，01背包。
分组背包问题，每组物品有若干种策略，选本组的某一件，或者一件不选。第一重循环所有组k组，第二重循环从大到小，第三重循环是所属k组里的i。
5.二分，三分算法
通俗的说，其实二分是针对一个单调函数，在这个函数的一个区间中查找，每次取区间的中点去判断，然后根据大小把区间变成原来的一半。
如果说二分针对的是单调函数，那么三分针对的是双调函数
三分是求这样先增后减或者是先减后增的函数的极值的。
具体步骤就是：对于区间 （L，R），先求出 1/3 处的 M1 和 2/3 处的 M2，然后比较 M1 和 M2 处的大小，如果 M1 处的值大于 M2 处的值，那么极值一定在（M1，R）这个区间范围内，否则一定在 （L，M2）这个范围内。
6.数论
1.素数的杨氏筛法（求素因子，求什么因子和等等之类与素数有关的题）
2.整数唯一分解定理（经典题就是A^B，关于分解整数之类的题）
3.最大公约数，最小公倍数，快速幂，欧几里德算法，模运算，费马小定理（这些都是最基础的数论知识为下面的数论的推导做铺垫）
4.欧拉定理（费马升级），裴蜀定理，扩张欧几里得定理
4.逆元(欧几里得求法，线性递推/倒推求法）
5.容斥定理
6.欧拉函数（容斥求欧拉函数）
7.扩展欧拉定理
8.线性同余方程组
9.中国剩余定理
7.树状数组，线段树
1.两者在复杂度上同级, 但是树状数组的常数明显优于线段树, 其编程复杂度也远小于线段树.
2.树状数组的作用被线段树完全涵盖, 凡是可以使用树状数组解决的问题, 使用线段树一定可以解决, 但是线段树能够解决的问题树状数组未必能够解决.
3.树状数组的突出特点是其编程的极端简洁性, 使用lowbit技术可以在很短的几步操作中完成树状数组的核心操作，其代码效率远高于线段树。
8.单调队列
队列中的元素其对应在原来的列表中的顺序必须是单调递增的。
队列中元素的大小必须是单调递增/减/甚至是自定义也可以
单调队列与普通队列不一样的地方就在于单调队列既可以从队首出队，也可以从队尾出队。
单调队列有许多作用：
比如可以求出一个数组内第一个大于等于一个数x的数
也可以通过维护单调性，解决一些区间内最小或最大的问题
10.补充材料
目前打CF网站的收获 打codeforces比赛加起来准确来说已经有十三场了，因为有一场出为标题不计分了，但是做结束的比赛题目也做了好几轮。刚开始接触这个网站的时候，看见全英文马上感觉头就很大，因为我英语不好。第一次比赛是div3的难度，因为是水题，题目很简单但是因为第一次打，脑子里总是想着出题，题目没看清就开始写代码，而且脑子没有总体想一下代码的写法，代码就是一个简单的符号问题搞了半天一个多小时才出题a题最后结束也才出两题。打比赛是对学习的知识输出能力的评价，也要通过打比赛发现自己的不足，学习比赛自己未涉及的知识点。总的来说比赛是用来提升自己的。回想前几场刚开始比赛会涉及的的问题。对于我来说吧，因人而异。我最初遇到的最主要问题就是太过急躁，比赛过程中心态太差。还有就是不知道出题的人的出题目的。因此就可以形象的把我比作一只急躁的无头苍蝇。所有在比赛的时候知道题目的解法，但是代码老是写不对，代码漏洞百出。脑子总是纠结不就是这个意识吗？怎么会错？而不是静心思考。所以说心急吃不了热豆腐。我一开始就意识到自己的问题，每次比赛一着急就告诉自己先静心。比赛过后题目看大佬的博客看他们是怎么想问题的，他们的思考路线是怎么走的，总结abc题目的主要特点。我目前得出前面abc的题目就是思维题思考方向就是找特殊点，基本大部分题目就是有每个例子有相同或者相似的地方。有了思考方向第一次打比赛div3的a题目都花一个小时多的时间变成了现在div3快的时候十分钟，div2快的时候a题目二十分钟。比赛这几场我出过div2c题目三次，虽然给了我鼓励但是都是数学推导的题目，代码都是输出一个式子。div2c题目其他类型的题目还没出过呢。重要的是提高解题逻辑思维能力，代码是死的可以学，可以记忆但是思维是活的，要不断加强。网站的题解看不懂可以看大佬博客的写的博客。参考他的思考过程和代码很重要。后来遇到的问题就是分数一直掉老想着分数的问题，比赛就是因为这个原因老是着急，着急的频率就会上升。动不动就要花时间去冷静。比赛不够投入就算有能力出题，也总是出不了。
我自己感觉最重要就是要找到自己的解题方向，比赛时要全身心投入，补题目最重要。补题思考三个问题，遇到这种题目的思考方向是什么？，我解这个题目的知识点欠缺在哪里？我下次比赛要怎么做?
课程学习的收获 首先思维得到了锻炼，老师讲的题目难度对于我来说都很大的，我有经常上课后卡在某一题目，课后想好几个小时各种演示推导。动态规划的题目，一开始也是怎么想都很难想明白。通过各个题目堆出来的，慢慢对它有了感觉，实话实说我还是没怎么搞明白，半知半解吧。最最烧脑的就是数论的题目，从题目推导公式，代码的实现还要注意精度，时间，开还是闭范围等等。打比赛对自己的思维也是一种锻炼。所以说这个课程思维量很大，思维能得到锻炼。对以后自己思考问题，就会有较多的方向去思考。
【ACM节课课程总结】其次，提高自己的自主学习能力和拓展自己的知识面。老师上课讲的有些听懂了但是一写就废，有些听不懂还得自己去查资料思考，还有老师出的题目有些还是有上课没有讲的知识点，还有打CF比赛补题目时所遇到的知识点，所以大部分是在边做题边学习，自主学习的量还是蛮大的。在没有参加这个课程之前，我只知道c++那些超级基础的知识，如果没有参加这个课程我可能还停留在冒泡排序，双重循环等等这些层面。之前根本不知道这些CF，牛客，Atcoder这些比赛网站，连网站都不知道更别说去打比赛提升自己了。
然后提高了自己学习专注度。平常每天都会有较多的剩余时间，没选这个课程之前，没事情干就会去刷刷短视屏和玩玩游戏，根本不会去想着学习。没结课之前，几乎没有碰过了。剩余时间都是在做老师发的题目，每天至少把晚上的时间投入三到四个小时，有时候投入四个小时多直接做到十一点多，因为有时候做着做着根本不会注意到时间所以有时候就会到十一多才反应过来。后来由于因为要打比赛，基本都是十点半开始，要花两到两个半的时间去打比赛，所以后来每天晚上不仅要熬夜，而且花的时间都是很多。
最后养成一种总结的习惯。这个非常感谢老师叫我们每周写总结博客，还评等级。每次老师公布博客等级，我会去看其他同学评的等级比我高的博客，看他们是怎么样总结，下次总结的时候多注意。有时候看了其他同学的总结博客是有不同的感触的，有时候发现和他们有相同的地方，有时候自己没有发现的问题，但是发现自己身上存在相同的问题。打比赛和做题的时候经常会自己想这个题目的特点，虽然每周只写一次总结博客，其实每次打比赛和做题目自己都会思考，其实就像每次在做小总结。这种习惯的养成我感到很庆幸，很感谢老师。
课程学习的感想 从起初的犹豫不决到下定决心到课程的学习到课程的结束，仿佛感觉就在昨日刚发生的一样。在学习的过程中因为本身是比较喜欢玩的，一直学习一直学习如果把时间拿来玩耍了那就没时间完成作业了在此期间，有过焦虑，有过退却，有过不耐烦，有过迷茫，都坚持下来了但是在这些背后有理解掌握知识点之后的幸喜和成就感也不是都是“痛苦和折磨”。就像打游戏你是一直开心的吗，如果你游戏一直输玩游戏还会开心吗？任何事情都要两面性在于你是如何去看待的，过程中的种种需要自生经历之后才会有自己的感想。
首先对于这个课程学习对于我来说，因人而异，因为我是大一才接触这个，不像其他人，有的小学生，初中生是真的强，CF分数2000的大有人在。对于这个课程确实是有难度的，对我来说全是新知识，实话实说老师教的内容掌握的不是怎么好，但是对那些知识却有了认识，你有没有发现对于自己有过认识的知识点，下次遇到更容易掌握呢？其次花的时间确实是很多的，你基本要拿出自己所有的课余时间，有时候花了时间，却不一定掌握得了。虽然花时间多但是总比你花在游戏和其他玩乐的时间更有意义吧。这个课程时间花下去确实是会有很大收获的。

    推荐阅读


    上一篇：暑假集训小记

    下一篇：图论|周报（从1月7号起）