梦的开始

这个博客的初衷

这个博客一开始是记录我在竞赛中的点点滴滴的成长。

一步一步地向前迈进的我，希望在看到这个博客的时候，知道自己走了多远，看到自己每一天都干了什么，学到了什么，直到我的IO生涯的结束。

因为竞赛，我对于程序编写有一定的熟练程度，并且会比还没有学的人有更多算法的思想，但是有的时候这也限制了我的思维，和学习。

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

前言

​ 发现我又咕咕了一篇早就应该写的博客,唉,真是的;

​ 强联通分量常用于缩点,重建图去跑其他算法;

入门

​ 强联通分量存在于有向图,简单的概念即有向图中一个块中的点可以彼此到达,这个块被称为分量,而两点彼此能到到达称为强联通,那么强联通分量的概念就出来了;

​ 同样用的时间戳(dfn)与返祖标记(low)这个概念,如果不知道,请看本博客中的点双边双;

前言

​ 单调队列并不是太难的东西,不应其应用到的题目困难而觉得单调队列困难.

​ 我第一次遇见单调队列时是在学图论时,遇到了Island这道题(见基环树专题),当时的我对单调队列一无所知,而对其优化更是懵,所以当时就懵着将题解半抄半写地打了出来,但还是不懂.现在来看,单论单调队列,它是不难的,难的是与其他算法的结合;

必备知识

​ 树链剖分,最大权独立集(即没有上司的舞会(树上DP)),矩阵乘法;

D-DP

模版简述

​ 模板

​ 关于动态DP,其实是关于一类动态修改点权的问题,但是很难去处理;

​ 我们平常的DP经常是离线DP,而当在线时,就会出现事故;

​ D-DP是关于求最大权独立集的,支持动态修改点值,其思想即DP的通项递推式改为矩阵乘的形式进行递推,而树上问题就可以使用树链剖分提前处理出区间矩阵乘;

折半搜索(meet in the middle)

​ 我们经常会遇见一些暴力枚举的题目,但是由于时间复杂度太过庞大不得不放弃.

​ 由于子树分支是指数性增长,所以我们考虑将其折半优化;

前言

​ 这个知识点曾经在模拟赛中出现过,所以这里稍微提一下;

​ 讲的很浅显,但是不要D讲者;

入门

​ dfs搜索树是指数性增长,如果将指数减少一半,就将会有量的飞跃,所以在遇见暴力枚举太大时,我们可以考虑这种算法;

关于爆搜

​ (这还用说,讲者太菜了)

​ 爆搜通常是没有思路时一个 优秀 玄学的解题方法,但同样是搜索,我们所的分数却相差甚远,即搜索的优化问题;

前言

​ 这是很基础的东西,这里只作为回顾.

​ 讲着实力不足,请不要D讲者;

BFS

​ BFS,广度优先搜索,用于逐层拓展的工具,可以有效地通过比较同一层之间的结果进行有效地减枝,而相比之下DFS的减枝就比较玄学,故能用BFS时,BFS的时间复杂度一般比DFS要低很多;

记忆化搜索

​ 记忆化搜索,属于DP的分支,但是其实现更加简单,依靠于DFS,所以在一些方面更具优越性;

前言

​ 记忆化可以作为DP难以实现时一个简易的方法(我知道你们都秒切DP,就我一个蒟蒻不会QWQ).

​ 讲的很浅显,但是不要D讲者;

浅谈

​ 记忆化搜素,顾名思义,是通过储存一个状态的最优信息,减少DFS的搜索树;

关于trie

​ 其实字典树和以上两种算法有很大不同,但是hash由于其优秀的应用,导致有些字符串查找用hash也是可行的.

​ 字典树中支持添加,查找,区间查询(可持久化字典树),而且在异或操作上有更加好的操作;

前置知识

​ 树的基本构造;

入坑

​ 字典树是通过动态建点,而形成的树,基本数组有两维, $tr[x][to]$ 中第一维存的是节点标号,而第二维存的是当字符为 $to$ 时通向的节点;

关于HASH

​ 这应该是经常使用的一个算法,因为其预处理后,优秀的$O(1)$处理出子串,并且$O(1)$比较,大快人心,而且写法简单,令人心情愉悦;

​ 但是其空间复杂度较高,并且有玄学模数以及哈希冲突,以至于如果想hack,其实可以hack掉;

前置知识

​ 关于进制,模数,hash就用到了重构进制,取模稀疏,所以哈希表又叫稀疏表;