子谦。

入门教程

未归档(52)

/ 注册

全部文章 / 入门教程（共9篇）

数位DP入门详解+题目推荐

\(update:2019-9-6\) 博客里某些东西没有解释清楚，完善了对应的解释在开始之前，我们先来看一道题——题目链接题目要求，相邻两位的差大于等于2，那么我们先来构造一个试一试。比如说\(15246\)这个数，我们先取第一位为\(1\)，然后第二位是\(5...

入门教程数位DP 数据结构

2019-09-03

0 590

最小生成树

何为最小生成树？最小生成树就是对于一个连通图，保留若干条边，使图依然联通，且边权和最小。因为\(n\)个点的连通图（以下自动默认为连通图，），最少要有\(n-1\)条边。所以对于一个图的最小生成树，也一定只有\(n-1\)条边。反证一下（此证明仅限于非负边权）：如果这个图的最小生成树...

图论最小生成树入门教程

2019-08-16

0 403

负环详解

什么是负环？顾名思义，就是一个所有边的边权和为负数的环出现负环会怎么样？我们知道，一般情况下，图上的最短路都是确定的。但是一旦图上有一个负环，\(s\)到\(t\)的最短路就会不远千里的去覆盖上这个环（只要能够到达），并且不厌其烦的走上一遍又一遍。由于负环的边权和是负的，并且...

入门教程图论负环

2019-08-16

0 556

主席树入门详解+题目推荐

主席树学名可持久化线段树，就是这个可持久化，衍生了多少数据结构为什么会有主席树这个数据结构呢？它被发明是用来解决什么问题的呢？给定n个数，m个操作，操作类型有在某个历史版本下单点修改，输出某个历史版本下某个位置的值的值，n和m小于等于1e6 乍一看是不是一点头绪也没有...

入门教程数据结构主席树

2018-11-06

0 573

状压DP入门详解+题目推荐

在动态规划的题型中，一般叫什么DP就是怎么DP，状压DP也不例外所谓状态压缩，一般是通过用01串表示状态，充分利用二进制数的特性，简化计算难度。举个例子，在棋盘上摆放棋子的题目中，我们可以用1表示当前位置摆放棋子，用0表示当前位置不摆放棋子。这样的话，就能够直接运用许多二进制运算的特...

入门教程动态规划状压DP

2018-10-17

0 678

树形DP入门详解+题目推荐

树形DP。这是个什么东西？为什么叫这个名字？跟其他DP有什么区别？相信很多初学者在刚刚接触一种新思想的时候都会有这种问题。没错，树形DP准确的说是一种DP的思想，将DP建立在树状结构的基础上。既然说了这是一种思想，那么单讲的话，也讲不出什么东西来。所以我们结合具体题目进行讲解...

入门教程动态规划树形DP

2018-10-15

0 481

单调队列/单调栈入门详解+题目推荐

以前一直以为这两个是很高级的东西，这段时间用到了才开始学，发现实际上非常简单下面我们以单调队列为例进行讲解，单调栈自行类比顾名思义单调队列这个名字就指明了它的性质——单调性我们来看一道例题——滑动窗口题面在此不再赘述，大意就是有一个长度为\(n\)的数列，一...

入门教程数据结构单调队列/单调栈

2018-09-09

0 499

树链剖分入门详解+入门题推荐

以前没有接触过树链剖分的同学们看到这个东西是不是觉得很高大上呢，下面我将带你们进入树的世界（讲得不好别打我）首先我们来看一道题软件包管理器这道题的大意是，每个软件有一个父软件（除根节点外）。要安装一个软件必须先安装它的父软件，要卸载一个软件必须先卸载它的所有子软件，模拟对软...

入门教程数据结构树链剖分

2018-09-03

0 370

NOI&&NOIP知识点集萃

更新日志更新了一篇的线段树的讲解，最近还是写不了什么高级算法，只能先从基础的做起，见谅更新了一篇树状数组的讲解，没学过的快去看看吧更新了一篇数位DP的讲解，还请大家多多支持刚刚重返OI，难度较高的东西近期不太敢写，担心误人子弟，就更新了一篇负环和最小生成树的博客，希望对大家有帮助 ...

入门教程

2018-03-25

0 461