糖醋盐明清

分类

ac的题(11) mysql(1) 二分(3) 动态规划(3) 图论(2) 数据结构(4) 未归档(56) 模版(5) 算法(1) 算法基础知识(2) 算法思维(1) 蓝桥杯练习(3) 计划(1) 计算机网络网络(1)

/ 注册

全部文章（共94篇）

字典树模板

#include<stdio.h> #include<string.h> const int INF = 40005; int tire[INF][26], sum[INF], tol = 1; void insert(char* data,int rt); void fin...

2018-10-09

0 452

HDU - 1811 (并查集 + 拓扑排序)

读题可以知道当成环的时候会有冲突，当不止有一个拓扑排序的时候信息不完全。当有相等的时候可以用并查集把他们当成一个节点来处理；代码如下： #include<stdio.h> #include<string.h> #define mmset(a,b) memset(a...

2018-10-05

0 481

用循环不定式来证明冒泡排序的正确性

循环不定式可以用来证明一个算法的正确性：比如我现在有一个算法A,我要证明它的正确性：步骤如下：第0步：定义循环不定式；第1步：证明循环不定式在算法开始的时候是正确的；第2步：证明循环不定式在算法每次迭代(循环)的时候是正确的；第3步：证明循环不定式在算法结束时是正确的；以下是...

2018-09-27

0 545

学习计划

算法学习计划

2018-09-13

0 315

图论-最小生成树

最小生成树：一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出；一：kruskal(克鲁斯卡尔) 将图中的每条边按从小到大排个序。然后按这个顺...

2018-09-03

0 349

图论-最短路总结

一：迪杰斯特拉(Dijkstra)算法 Dijkstra算法是单源最短路算法。他能求出一个点到其他点的最短距离。这个点叫做源点；他的主要思路就是将所有顶点分为两部分，一部分是点集合是Q,剩下部分点集合是P;其中Q集合的点到源点的最短距离已经求出来，P集合是待求到源点最短距离的...

2018-09-02

0 335

ac自动机(字符串的多模式匹配)

前面已经说过kmp是一种字符串匹配算法。就是给你一个模式串p,和一个主串m。让你找出p在m中的位置； ac自动机与kmp类似，也是一种字符串匹配算法。与kmp不同的是，kmp是单模式的字符串匹配算法。而ac自动机是多模式的字符串匹配算法。也就是给你n个模式串p1,p2,p3.......pn，...

2018-08-31

0 360

从动态该规划角度理解kmp

kmp是一种高效的字符串匹配算法(模式匹配算法)；给你一个主串m,模式串p。kmp可以找出p在m中的位置；比如主串m：abadabaad和模式串p:abaa;那么p在m中的位置是5; 如果是纯暴力(朴素的模式匹配算法)的话时间复杂度会达到O(n*m),是比较高的；但是用kmp的话，时间...

2018-08-24

0 413

oj造数据

关于oj造数据主要用到的就是随机函数和文件流 1.随机函数是rand(),头文件为<cstdlib> 用法： int res = rand()%b + a; res是从a开始(包括a)连续数b个数这个区间中的一个随机数，（ res = [a,b) ）; 需要注意的是如果不设置随...

2018-08-23

0 539

线段树002-区间修改

接下来讲解一下区间修改：在线段树001-概述中讲了单点修改，现在又增加了一种操作将区间x~y的值修改为v; 比如在下面这个图中我要将1~5区间的值全都改为v; 正常人的思维是把1~5这个区间的修改看成对点1,2,3,4,5的单点修改；但这样的复杂度是nlog(n)是比较高的；我们换...

线段树区间修改

2018-08-22

0 461