-
【图论】强连通分量
前言 在学习该部分之前，请熟悉此部分的概念。我们使用Tarjan算法求解时要用到的概念有：DFS树，DFS森林，DFS序，以及其中的树边，前向边，返租边与横叉边。了解它们有助于读者理解Tarjan的工作原理。 概念 子图的定义 假设有G =&l... -
【数据结构】邻接表与链式前向星
邻接表与链式前向星更正： 使用vector存图的叫做邻接表 使用数组模拟的叫做链式前向星 邻接表（使用vector） 使用邻接表的优劣： 优势： 码量少，易操作 不用担心空间，不易写错 劣势： C++11之前不能使用auto v : i... -
【动态规划】背包问题
前言 根据维基百科 ，背包问题（Knapsack problem）是一种组合优化的NP完全（NP-Complete，NPC）问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。... -
【动态规划】状态压缩DP
前言 二进制的很多应用离不开集合这个概念，我们都知道在计算机当中，所有数据都是以二进制的形式存储的。一般一个int整形是4个字节，也就是32位bit，我们通过这32位bit上0和1的组合可以表示多大21亿个不同的数。如果我们把这32位bit看成是一... -
信奥队五月竞赛总结反思
前言 前一星期与这星期一，信奥队进行了一次综合测试，包括初赛，复赛，演讲与做题情况四个项目综合评分，来评测我们近一个学期的学习情况，这里做一次总结与反思 各项目反思 初赛 初赛可以说是我个人最为薄弱的环节了，我个人主要失分点在前面的选择题和... -
【动态规划】LIS与LCS（最长上升子序列）
引子-LIS问题 这几天在学习DP（动态规划），里面第一个接触到的问题就是LIS问题，这里简单概述如下: 给定一个长度为NNN的数列AAA，求数值单调递增的子序列的的长度最长是多少？ 其中LIS（最长上升子序列）指的是从序列A中选择若干个i，使... -
【图论】最短路
前言 最短路是图论最重要的算法之一，也是算法难点。经过这篇的学习，你会发现你离成功就差一个最短路的距离（虽然它难以被找到）。最短路是指，某个点到某个点之间的距离最短的路径。 必要的知识 学会存储一张有向图，我们一般使用邻接矩阵和邻接表。因为邻接矩... -
【搜索】优先队列BFS
前言 在讲解优先队列BFS之前，让我们回顾一下最普通的走迷宫问题： 对于一个迷宫，从起点开始，对于四周能扩展的点打上标记并加入队列。直到从队列取出来的点表示的位置为终点时，退出搜索 显然，在没有限制的情况下，我们只需要给出一条路径，如果把迷宫看...