近半年我学习了:树和图,DFS,BFS,二分查找,二分答案,DP(背包,线性),堆,最短路,ST表(倍增),单调栈和单调队列,离散化,逻辑运算,STL unique , 前缀和&差分 , 双指针 , DP(区间,环形) , 全排列STL , 时间复杂度**,log,位运算,离散化,倍增.
我将花一些时间在这个清闲的暑假对它们进行整理,为今年的CSP-S做准备.
一.树和图
树有唯一的根节点.(无前驱节点)
一些概念/定义(树):
完全二叉树:叶子节点只会出现在最下层和次下层,且最下层的叶子节点集中在树的左部
满二叉树:一颗深度为k且有2k−12^k-12k−1个节点的二叉树称为满二叉树.
度:一个节点的子树个数是这个节点的度.
层次:一棵树的根节点的层次为一,根节点的子节点在层次二,依次类推.
深度:一棵树所有节点的层次最大值称为这棵树的深度.
树的遍历:
1.先序遍历:124356
2.中序遍历:421563
3.后序:426531
4.层序遍历:123456
一些概念或定义(图):
有向图:边有指定方向的图
无向图:边无指定方向的图
连通:若从顶点a到顶点b之间有路径,则称它们连通
连通图:在无向图中,如果任意一对节点都连通,则称这个图为连通图.
强连通图(有向图):在有向图中,若对于每一对顶点a和b间,都存在一条从a到b的路径和一条从b到a的路径,在称此图为强连通图
基图:将有向图所有有向边替换成无向边,则称此图为基图
弱连通图(有向图):如果一个有向图的基图是连通图,则有向图是弱连通图
二.DFS和BFS
PartPartPart OneOneOne:深度优先搜索(DFS)
顾名思义:"深度优先"的搜索,用一句话来概括就是:"不撞南墙不回头"
深搜别后的远离其实是穷举,将所有的可能全部列举.
这种方式会使得它写出的程序有百分百的准确率,但是同样的,它的效率很慢.
这会导致它只能在n小于等于15的时候运作.在15到20的区间范围内或许可以通过优化通过题目,但是再大,就能考虑使用它了.
以有障碍物的迷宫为例,DFS会按着一个方向一直前进,直到有障碍物遮挡,导致不再能继续前进,才会退回上一步,继续前进.(回溯)
实践:迷宫之判定
代码:
本来不准备放代码的.但想说明一下为什么不去出vis的标记(也就是进行回溯)
如果说需要统计迷宫的全部通关路径数,那么确实需要进行回溯,但如果只判断是否能走通的话, 就可以不进行回溯.
这道题目就需要进行回溯了:迷宫之最少花费时间
这道题需要在回溯的基础上加以改动:走迷宫(注意左上右下的顺序)
经典题目:八皇后
曾经我好像还出过八皇后的题解,但现在好像全忘光了😭
我不会告诉你我现在正一边看C语言修仙一边愉悦的打代码
比较不一样的:数水坑 这是DFS的另一种提醒.搜索连通块.
然后是:数水坑 需要动用一些小巧思,但不难
(本来还挑题做的,现在就纯顺着往下写,看完一章写一题.我宣布!C语言修仙是我看过最轻松的小说.主要是专业对口.上次看一本物竞相关的小说给看死了.一十四州肯定学过C,感觉很专业)
C++好棒!马上要上数学课...作业一笔未动....
然后:细胞
这本书真的想教会我面向对象和面向过程的区别...
新题型:组合的输出
我的生活:睡觉,打代码,饭,小说,WHK,散打
这题很古怪.
我已经过了,但是对于代码本身为何这么些还是有疑问.
比如为什么DFS(递归)中需要有变量l的存在,程序才会输出正确的答案?
看这个:(这是在没有变量l的时候程序的输出的一部分)
可以发现在"1 2 5"输出后,程序有输出了"1 3 2".但之前其实已经输出了"1 2 3".这是不对的.
只有在有了变量l后,在输出"1 2 5"时,l会变成5,出发i==n的条件,才会再返回上一层.
和上一题类似的:选数 这道题其实与上一道题差不多.就加了一个素数判断.
在我坚持不懈的阅读过后,这本C语言修仙终于触及了我不会的,有关c++的东西了.
我不到啊,它上一秒还在死循环debug,下一秒就开始状态压缩了....
"用深度优先遍历了一个迷宫"嗯,学编程人类的加密语言
又是棋盘:黑白棋盘 这题很奇怪,我尝试了一下,又WA又TLE的...
明白了.看代码,(这个是写错的代码):
其实,黑棋盘这题是不需要回溯的.DFS一次就会把所有的黑棋遍历到.
所以正确的代码是这样的:
话说这题还挺诡异的,又是多测,又是行列乱搞...
( •̀ ω •́ )y!新题型:厕所管理员
这题从理论上而言有两种方式.这是第一种:
(这一种是根据前几题的做法得来的)但是这一题有别的更为简单的做法,长这样:
好爽,快速打代码有一种飙车的感觉.上方的代码是01DFS.
题目:分开午休 依稀记得这道题好像很有意思
很古怪啊...我记忆出问题了?
记忆出问题了...这题很普通.
题目:爆米花 这题好像不难,但是很烦.
其实也不是很烦,还好.
又是不同类型的题目:食堂管理员
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
闲话
好诡异好诡异好诡异......
我要上数学课了,作业一笔没动.祝我好运.
C语言修仙看到结尾了.一团乱麻,感觉我漏了什么.
我肯定漏看了一些章节.或许这就是看盗版小说的代价.第一次看到这种题材的小说,结果却看的这么云里雾里.....好生气.再也不敢了.
怎么说呢,这本书我个人认为还是写的很好的.但是似乎没有很火.我估计是因为开头几章太专业了.估计没接触过编程的应该很难强撑着看完.....后面虽然没有完全看懂,但已经感觉很刀了.....
我要上数学课了.下一本打算看小明是怎么死的.
不过以"Hello world."作为一个隐藏的伏笔还是很令人意想不到的.
程序员/学习编程的人们用这句话唤醒计算机的新生.而你的存在本身就意味着我的新生.
应该是这种感觉.
Lo问我为什么看星星。
我觉得银河和代码是同一种东西，这也是一种回答。 (选自C语言修仙)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
好的,然后也是开始看小明是怎么死的了.
食堂管理员还可以,也不难.
一道不知道什么题型什么难度的题:暴力破解攻击.
"你是超级黑客"这题也是无敌了.
感觉手不太好使.就像早上起来拿不住笔一样
这题不难,挺简单的.
老熟人:【搜索】【回溯】八皇后 图书馆有空调.好舒服.
本题存一下八皇后的位置即可.
依稀记得有点复杂的题目:小码君喝牛奶.好像有九十多行代码. 不想写...好烦.打算搁置一下.
先看下一题:拼图助手 看题面疑似跟八皇后有关
有意思:
代码好相出bug了.
这道题很古怪.打算放一下.
重新看小码君喝牛奶
做完了之后有一个很重要的感想:信竞有一个很重要的能力,就是细心,你可能就因一个边界问题就会少30分,从S1掉到S2.从华二掉到曹二.所以一定要细心.
这道题本人觉得挺难的.先说难点:
1.它的代码比较长(虽然可以通过一些手段来减短),很容易写错.
2.如果没有进行适当标记,它会死循环.
3.最后在输出的时候需要考虑0.
这道题的代码长这样:
上文提到的难点都是我错掉的点,这道题我调了一个多小时(虽然说比起一些绿题或者蓝题,这道题的时间不算很长,不过作者给这道题的原先估计时间其实是半小时_)
再来提下我错的点:
1.一开始我是没有加cun数组的,所以导致一直在死循环,还找不出问题.
2.交了cun数组后,本身的代码是需要改动的,所以导致我加了cun数组之后,代码其实还是有问题的
3.提交的时候wa了几个点,后来才发现,最后输出的时候需要考虑0
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
闲话:
从此,我的人生蜩螗沸羹.(选自小明是怎么死的)
我有点死了.谁能来解释一下?纯爱突然变大乱炖
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
打个岔,因为某种原因,暂时不弄DFS的板块了,先看时间复杂度,双指针,前缀和与差分,离散化和位运算.
三.时间复杂度
举个例子,比如说使用DFS的时候,它有一个必要条件就是n ≤\le≤ 15,若果说n=1000,想必你不会使用DFS,但这只是基于你的经验,那么在使用一个不熟悉的算法时,如何去判断这个算法的效率呢.所以我们需要时间复杂度的理论去估计一个程序的运算量.
比如说这个程序:
一共进行了n次a[i]++的运算,时间复杂度为O(n)O(n)O(n)
再比如这个程序:
它一共进行了n+(n-1)+(n-2)+(n-3)+.....+1=12(n2+n)\displaystyle \frac{1}{2}(n^2+n)21 (n2+n)次操作,时间复杂度记为O(n2)O(n^2)O(n2)
一些关于大OOO时间复杂度表示的约定:
1.括号中不含常数.
2.当输入规模需要多个变量表示时,大OOO符号里可以有多项
3.当程序的运算量与n无关时,时间复杂度为O(1)O(1)O(1)
4.当大OOO符号里有logbalog_balogb a时,如果b为常熟,将起省略
然后是一些与log有关的时间复杂度.
这个代码的时间复杂度为O(logn)O(log n)O(logn)
再看这个:
这个代码会做n+n2+n3...+1n+\displaystyle \frac{n}{2}+\displaystyle \frac{n}{3}...+1n+2n +3n ...+1次时间复杂度为O(1)O(1)O(1)的运算.
这里需要知道一个重要结论:调和级数,也就是:
1+12+13+...+1n=O(logn)1+\displaystyle \frac{1}{2}+\displaystyle \frac{1}{3}+...+\displaystyle \frac{1}{n}=O(logn)1+21 +31 +...+n1 =O(logn)
那么将这个结论带到上面的代码中,那么它的时间复杂度就是:O(nlogn)O(nlogn)O(nlogn)
还有这个代码:
长得有点像莫不知名DFS题目的一段代码.
时间复杂度为O(n2)O(n^2)O(n2)
这段代码可以看作是在枚举一个长度为n的数组vis的情况,vis[i]有0,1两种情况.
那么一共有n2n^2n2种情况.
另外还有这个代码:
代码中橙色的那个是取n的全排列.
n的全排列有n!n!n!种.
那么这个代码的时间复杂度就是O(n!n)O(n!n)O(n!n)
可以发现,算法的时间复杂度越低,算法的运行效率就越高.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
好想做梦啊,做一个饱含千秋的大梦.
然后就不要再醒来了.
毕竟,"只此浮生是梦中".
或许也可以是一个无忧无虑的欢快梦.
都说"死后自会长眠".
但怎么能肯定呢...
还不如乘活着的时候多睡一会儿.
寒梦闻旧声音,遥知故人来(选自十世禅)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
一般来说,时间复杂度不超过O(108)O(10^8)O(108)的代码可以在1s内运行完毕.
四.双指针法
这里顺便提一下,由于本人只有20天的时间把这个知识点总结完,所以可能会选择一些重点算法去总结,比较小众的就会忽略不计.目前暂定加粗的那些算法.
简单题:
题目一:有序表的合并
对于这道题,其实可以发现,有一个比较重要的条件:即a,b均按不降序排序.
对于有序序列其实可能会想到二分,但是这题并不适用,不管是从时间复杂度的角度,还是从题目完成来看,都不适用.
因为n ≤107\le10^7≤107 而一次二分的时间复杂度好像是O(logn)O(logn)O(logn),太大了.
又因这里有两个序列,进而考虑双指针.
这里的双指针使用是:在序列A中有一个指针i,在序列B中有一个指针j,它们的限制是:保持Ai<=BjA_i<=B_jAi <=Bj .
由于A,B序列是不降序排序,所以当i增大时,j不会减小.
大概思路是从小到大枚举i,在这个for循环里嵌套一个while循环,用来增加j.
虽然这是一个嵌套循环,但可以发现,这个j只会增加到m,且每一次循环j都会增加1,所以这个代码的时间复杂度应该是O(n+m)O(n+m)O(n+m)
分析下来似乎不难.但实际上,这题很难.算是我见过最恶心的黄题.
首先,这道题目是多测.这意味着你需要清空你的一些使用过的数组(这个地方本来是不该错的,可能是太久没做多测了,但还是希望下次能细心一点)
其次,需要仔细阅读题目的数据范围和提示.(再次重申:信竞一定要细心!细心!细心!)
这道题中的AiA_iAi 和BiB_iBi 都是≤264\le2^{64}≤264,这意味着你需要开unsigned long long
其次看提示,这提示需要快速读入的,意味着你的scanf里面需要些"%llu"而不是"%d".
题目二:A-B数对
从双指针的角度来看这道题目,可以发现数列的顺序不影响答案,所以可以进行排序(不降序),想要求出Ai−Aj=CA_i-A_j=CAi −Aj =C的个数.
将这个式子转化一下,变成:Ai−Aj≥cA_i-A_j \ge cAi −Aj ≥c
跟上一题有着差不多的思路,从小到大逐个枚举i,再围护一个下标j,使得j是最大的,满足Ai−Aj≥cA_i-A_j \ge cAi −Aj ≥c这个不等式的数组下标
可以发现因为已经排过序的缘故,当i增大时,j不可能减小.
然后因为可能会有重复数字的缘故,我们需要一个数组XXX,XiX_iXi 表示在对于AiA_iAi ,在它之前有多少个与它相同的数字.可知Xi=Xi−1∗[Ai=Ai−1]+1X_i=X_{i-1}*[A_i=A_{i-1}]+1Xi =Xi−1 ∗[Ai =Ai−1 ]+1
本题在理解上一道题目的基础上不是很难,不过A-B感觉有点绕是真的.
题目三:逛画展
与前两题有所不同,这道题目是一个较为传统的区间问题.是不能进行排序的.
还是从双指针的角度去入手,,常见的想法是枚举其中的一个端点,设法求出另一个端点.
对于本题来说,可以枚举端点l,能够发现,在端点l增加时,端点r是不会减少的.
大概框架已经构造完毕,唯一的问题是如何去维护区间[l,r]中所包含的数.
这个问题并不难想.可以使用桶来维护.为每个数字x开一个桶CxC_xCx ,表示这个数字x在当前区间中出现的次数.在端点移动时,可以使用O(1)O(1)O(1)来维护这个桶.
可以再维护一个变量w,表示有多少个数字的C不为空.当w=n时,就代表这个区间是符合要求的.这题不难.
题目四:最大子段和
小总结:双指针法本质上是使用队列围护一个符合条件的区间.右指针相当于入队.左指针相当于出队.(选自深入浅出)
题目五:最大子段和这道题的做法,我参考了深入浅出程序设计竞赛(进阶篇)中的做法.代码如下:
这个做法我觉得很巧妙,它的时间复杂度是线性的,且空间用的也极少.
我必须说的是,一开始我并没有想到它的正解.我使用了前缀和,但是它的时间复杂度达到了O(n2)O(n^2)O(n2).只能获得40pts.
我转而去想双指针的解法,于是就写出了这样的代码:
是的,这个代码不但臃肿,且也只能获得40pts.
原因在于它双层循环的while循环的第二个判断条件:q[n]−q[j]]≥0q[n]-q[j]]\ge0q[n]−q[j]]≥0.
对于某些特殊的测试点,可能存在a[j]≥0a[j]\ge0a[j]≥0但是不满足刚刚那个条件的情况.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
我好像突然发现了一个华点:对于很多算法,它的本质就是两个字:枚举.像DP,DFS,BFS,最短路... 包括双指针.区别只是在于它们有的只是简单的枚举,而有的是复杂的枚举.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
看过我写的代码,相信你们就会觉得上面的代码精妙绝伦了.写那个代码的人,TA的左手肯定被图灵牵过,右手肯定被冯诺依曼吻过.
然后来着重解释一下上面的代码:
它的fff其实原本是一个数组,fif_ifi 代表以iii为右端点的全部区间和的最大值.
对于每一个fif_ifi ,它有两种选择,第一种是在有aia_iai 的基础上,加上fi−1f_{i-1}fi−1 ,第二种则是不加,只考虑aia_iai .
最后用一个answeransweranswer来取所有fif_ifi 的最大值即可.隐约感觉这道题不该是橙题.
本来打算刷一点题就跑路的,结果被上一题打击到了.所以就再写一点双指针相关的题目.
从橙题开始刷,刷七题左右.
题目六:连续的自然数 这道题感觉蛮简单的,那我刚刚是做到盗版橙题了?
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
好喜欢"寒梦闻旧声,遥知故人来."这句话.
我的头发最近掉了好多啊,这不合理啊...
我最近明明在放假啊...
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题目七:Easy Version 这题好怪啊,感觉不像双指针的题目.
题目负一: Cow Lineup S这题作者写不了,有离散化啊bro
题目八:Diamond Collector S 这道题有一点思考难度.难点在于所有的钻石需要放在两个展示柜中展示..作者想到的第一个思路是做两次双指针,去两次的最大值,但是事实证明,这种思路其实是行不通的.这是代码:
这种写法是行不通的,只能获得70pts.
因为两个最大的区间可能小于另外两个不是特别大的区间相加.此为hack数据(WangYinxiAlex提供)
注意到:4(2,5,6,7)+1(任意)是小于3(2,4,5)+3(6,7,9)的.
所以这题真正的解法应该是只进行一遍双指针.记录下每个左指针的右指针.然后把能加的加上,去看最大的数值.
代码如下:
这里好像需要优化(n为5e4,注意到双层for循环直接上的话可能会超时,所以第二层循环需要从i开始)
题目负二:Haybale Feast G这个做不了,需要线段树.
题目九:完美字符串 水黄.
猫猫你再不带我出去玩,我就成人机了.
题目十:极差
五.DP
参考Elmerr的算法之动态规划总结.
题目一:最长上升子序列 这道题是线性DP的板子题.
但有几个需要注意的点:首先需要注意的是对于DP数组的定义.
须知,dp[i]应当表示的是"以a[i]为结尾的最长上升子序列".
这个定义影响很大:首先你的答案就不是dp[n],因为整个序列的最长上升子序列不一定是"以a[n]为结尾的最长上升子序列.
其次就初始化来讲,dp[i[就不是0,而是1,因为最长上升子序列至少为1.
题目二:最长括号匹配
六.最短路
这是我比较熟悉的一个算法.最短路分为单源最短路和多元最短路.
单源最短路
七.BFS广度优先搜索
可以与深度优先搜索一起看,但终究是不太一样的算法.
与深搜全面但笨拙的"一条路走到黑"不同,广搜主攻最短路相关的题目.看到一些关于"最小","最少"之类的字眼可以考虑BFS.
这跟广搜的实现方式有很大的关系.
以题目一做一个例子.
题目一:迷宫
前面说过,广度优先搜索就是用来做最短路相关的题目的.
这道题它就是一个例子.
深搜的模块也做到过相似的题目.
道理差不多,但是BFS把DFS的函数变成了一个while + 队列.
从起点开始,上下左右进行遍历,如果可以走通的话,将其放入队列即可.
也就是说,广搜的版图是逐渐扩大的,差不多是这样:
题目二:奇怪的电梯
