Aull Chen's Blog

surface改造——安装Ubuntu 事情的起因是觉得每次都带游戏本去上课太重了，想找个轻一点的趁手工具。本着能省就省和可玩性高的原则，最后在海鲜市场淘了一台二（？）手的surface pro 4（带个问号是因为机身上贴有转转的验机贴，疑似不止二手，but who cares?）。作为一台发布于2015年的win平板，虽然它重量不轻，屏占比不高，处理器不好，电池续航4小时，发热严重，但是它只要550（8+256），还能玩gal。不过最重要的是，搭载了x86架构处理器，在折腾的方便程度上明显好于arm架构。没有谁能拒绝把一个电子产品安装上Linux系统，没有。 ~~考虑到之后还想玩gal，~~这次的改造选择了安装双系统，对原win10进行了保留。 What You Need Surface(any type supported by linux-surface) U disk Keyboard Love and Peace 准备工作 镜像（iso) 任意**linux-surface**支持的Linux系统镜像都是可以的。当然如果不介意某些硬件（比如触屏）无法正常工作或者热衷于 ...

字符串匹配 This article is a study note on Introduction to Algorithms. 定义 顾名思义，在一个目标串中寻找是否出现模板串的过程，为字符串匹配。 算法 预处理时间 匹配时间 朴素算法 000 O((n−m+1)m)Ο((n-m+1)m)O((n−m+1)m) Rabin-Karp Θ(m)\Theta(m)Θ(m) O((n−m+1)m)Ο((n-m+1)m)O((n−m+1)m) 有限自动机算法 $Ο(m \Sigma Knuth-Morris-Pratt Θ(m)\Theta(m)Θ(m) Θ(n)\Theta(n)Θ(n) 朴素字符串匹配算法 最简单直观的算法，又叫做BF(Brute Force)算法。两层循环，逐一比较目标串与模式串之间的每一个字符是否匹配。 伪代码 123456NAIVE-STRING-MATCHER(T,P) n = T.length m = P.length for s = O to n — m if P[1..m] == T[s+1.. s+m] print ...

最小生成树 在阅读下列内容之前，请了解 图 和 树 相关内容，并了解以下定义： 生成子图 生成树 定义 我们定义无向连通图的 最小生成树（Minimum Spanning Tree，MST）为边权和最小的生成树。 注意：只有连通图才有生成树，而对于非连通图，只存在生成森林。 Kruskal 算法 Kruskal 算法是一种常见并且好写的最小生成树算法，由 Kruskal 发明。该算法的基本思想是从小到大加入边，是个贪心算法。 前置知识 并查集、贪心、图的存储。 实现 伪代码：（不写正经代码是因为不想写并查集……真想看去找AI吧~） 1Input. The edges of the graph e, where each element in e is (u,v,w) denoting that there is an edge between u and v weighted w.2Output. The edges of the MST of the input graph.3Method. 4result←∅5sort e into nondecreasing order  ...

多源最短路 请确保自己已经了解图的相关内容。包括但不限于： 图，邻接表，邻接矩阵 路径，最短路，权，环 有向图，无向图 Dijkstra算法，Bellman-Ford算法 文中所有的证明都是不严谨的，详细数学证明可移步《算法导论》相关章节。 定义 顾名思义，求一张图上所有节点到其他可连通节点的最短路径。 最短路算法 Floyd Johnson Dijkstra Bellman–Ford 最短路类型 每对结点之间的最短路 每对结点之间的最短路 单源最短路 单源最短路 作用于 任意图 任意图 非负权图 任意图 能否检测负环？ 能 能 不能 能 时间复杂度 O(N3)O(N^3)O(N3) O(NMlog⁡M)O(NM\log M)O(NMlogM) O(Mlog⁡M)O(M\log M)O(MlogM) O(NM)O(NM)O(NM) 注：表中的 Dijkstra 算法在计算复杂度时均用 priority_queue 实现。 Floyd 算法 弗洛伊德算法可以用来求任意两个结点之间的最短路。 复杂度比较高，但是常数小，容易实现（只有三个 fo ...

单源最短路 请确保自己已经了解图的相关内容。包括但不限于： 图，邻接表，邻接矩阵 路径，最短路，权，环 有向图，无向图 定义 顾名思义，求单一起点到其他可连通节点的最短路径。有两种比较经典的算法： 最短路算法 Dijkstra Bellman–Ford 最短路类型 单源最短路 单源最短路 作用于 非负权图 任意图 能否检测负环？ 不能 能 时间复杂度 O(Mlog⁡M)O(M\log M)O(MlogM) O(NM)O(NM)O(NM) 注：表中的 Dijkstra 算法在计算复杂度时均用 priority_queue 实现。 Dijkstra 迪杰斯特拉算法是一个经典的求单源最短路的算法。其优点是容易理解，在数据量不大的情况下拥有较好的效率。缺点则是无法处理存在负权边的图。 过程 先介绍Dijkstra算法要用到的松弛操作（后面的Bellman–Ford算法也会用到松弛操作）。 对于边(u,v)，松弛操作对应下面的式子：dis(v)=min(dis(v), dis(u)+w(u,v))。 这么做的含义是显然的：我们尝试用S->u-> ...

578a9066b62d8523a8d89172458a1de0083f677eaaa2c8617876a64f0711673a478e7fa81a1002ea441188a72ce3e1db673e9c84a7356ecf5524c4fe7dbcd98e9f347382536defa58947b58245ca20dfae5260420b99c2c6fa953aecdc1b857ddc48e9f51264b44982b4a491ae2fb1b6c54c10ac903c819763208ebb6ac48b08ee7e0f7f7a5e114a14f7ddc504017d8b5c3be9f5da5c3a8baa6eca63d73ad276e0b9f5e06d79c91efe14925bf4c0510ed6b62c25f297fcde9a4ea5a55406192dbd7606582a52c453d2ffbb014c35e9b9cf51fb033d1c2d93abf2513feaa01503d8a5d96fab9d498352692ad2ee0e7394022ff7f7dfabcbe49 ...

多重背包 前言 多重背包问题，和完全背包问题相比，其实就是每个物品可以取的数目是限定的。 一、经典多重背包 有 n(n ≤ 100)种物品和一个容量为 m(m ≤ 10000) 的背包。第 i 种物品的容量是 c[i]，价值是 w[i]。现在需要选择一些物品放入背包，每种物品可以选择 x[i] 件，并且总容量不能超过背包容量，求能够达到的物品的最大总价值。 1、状态设计 状态(i, j)表示前i种物品恰好放入容量为j的背包 (0 ≤ i < n，0 ≤ j ≤ m)； 令dp[i][j]表示状态(i, j)下该背包得到的最大价值，即前i种物品（每种物品可以选择x[i]件）恰好放入容量为j的背包所得到的最大总价值； 2、状态转移方程 dp[i][j]=max(dp[i−1][j−c[i]×k]+w[i]×k)   (0≤k≤x[i])dp[i][j]=max(dp[i-1][j-c[i] \times k]+w[i] \times k) \ \ \ (0 \le k \le x[i]) dp[i][j]=max(dp[i−1][j−c[i]×k]+w[i]×k)   (0≤ ...

动态规划 之 完全背包 前言 完全背包问题，相比 0/1背包问题，其实就是每个物品可以取无限次，就像“完全披萨”一样（无端联想） 一、完全背包𢖩莉 典例 有 n(n ≤ 100) 种物品和一个容量为 m(m ≤ 10000) 的背包。第 i 种物品的容量是 c[i]，价值是 w[i]。 现在需要选择一些物品放入背包，每种物品可以无限选择，并且总容量不能超过背包容量，求能够达到的物品的最大总价值。 以上就是完全背包问题的完整描述，和 0/1 背包的区别单纯在于每种物品可以无限选取。 1、状态设计 状态(i, j)表示前i种物品恰好放入容量为j的背包 (0 ≤ i < n，0 ≤ j ≤ m)； 令 dp[i][j] 表示状态 (i, j) 下该背包得到的最大价值，即前i种物品（每种物品可以选择无限件）恰好放入容量为j的背包所得到的最大总价值； 2、状态转移方程 dp[i][j]=max(dp[i−1][j−c[i]×k]+w[i]×k)  (0≤k≤jc[i])dp[i][j]=max(dp[i-1][j-c[i] \times k]+w[i] \times k) \ \ ...

动规入门：0/1背包 前言 0/1 背包问题，作为动态规划问题的经典问题，可以帮助捋顺思维。之所以叫0/1背包，是因为在这类问题中每种物品只有一个，每个物品只有放和不放两种选择，即对于一种物品，可以表示为0和1两种状态。因此0/1背包统计的是 恒定容量 储存数个 不同物品 的 最大价值。核心在于确认好初始状态、递推基数和递推增量（反正就是dp[i][j-?] + ?，理解万岁）。说白了主要难点还是在确认递推关系上。 一、经典0/1背包问题 有 n(n ≤ 100) 个物品和一个容量为 m(m ≤ 10000) 的背包。 第 i 个物品的容量是 c[i]，价值是 w[i]。现在需要选择一些物品放入背包，并且总容量不能超过背包容量，求能够达到的物品的最大总价值。 1、状态设计 动态规划的最核心之一是确认好dp数组的含义。这决定了你接下来的递推关系和最终问题的返回值。（不知道为什么叫dp数组的自己去查动态规划的英文）每次当你找递推关系出现问题的时候，最好的方法就是回头看一下你确认的dp数组的含义。如果实在找不出，那就要考虑是否在这最开始就出现了问题。 在01背包问题中，我们一般情况下 ...

博客文章多了，某天突然发现，有一个tag点进去404，在本地运行hexo s却正常没有问题。 首先是老传统STFW，但是网络上的相关内容却都是解决tags总页面404的，我却是单独的tag页面丢失，没找到我想要的内容。用实力证明搜索引擎不可靠（笑）。刚好那段时间比较忙，就暂且把这事搁置了。（反正博客也没什么人看） 中间有一天突发奇想，把链接里相关tag的大写改为小写，发现可以访问了。没时间去解决（懒狗不想手动修改每一个tag），于是在Tags页面下写了条评论。 今天闲下来突然想起还有这事。搜索引擎一如既往稳定发挥。怎么办呢？不急，我还有一招——RTFM。找到hexo在Github上的仓库，在Issues里面寻找。果然找到了老前辈的馈赠——BUG反馈：大写开头的标签出现404 · Issue #818 · hexojs/hexo (github.com) 在里面逛了一圈发现是因为git中设置了大小写不敏感。 解决过程 在网上查找修改 git 设置不忽略大小写的方法。（顺便看到了很多因为这个引发的“事故”哈哈） 进入博客文件夹的 git 目录：.deploy_git，修改 .git 文件夹 ...