糖醋盐明清

未归档

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

/ 注册

全部文章 / 未归档（共56篇）

HDU - 4081（次小生成树 + DFS）

题意要求a/b的最大值。其中a是任意两点的点权和，b是除去这两点剩下的最小生成树的值。我们可以先求出最小生成树，然后不断删边，然后求出删去这条边后的剩下的点的最小生成树的值（联想到次小生成树）。删边的过程可以用dfs枚举。代码如下啊： #include<stdio.h>...

2018-10-18

0 373

HDU - 2489（枚举+最小生成树）

通过dfs枚举所有点集合的情况，然后对这些点进行prim求的最小生成树。然后将边权和点权的比以及点集合存在到一个结构体数组里面，然后先对边权和点权的比进行排序，如果相等的话就按点集合的字典序排序即可；代码如下： #include<stdio.h> #include<...

2018-10-11

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

图论-最小生成树

最小生成树：一个有 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

浅谈动态规划优化

动态规划是解决多阶段决策最优化问题的一种思想方法。有时动态规划的时间复杂度过高，需要我们对动态规划进行优化。对动态规划进行优化的普遍方法是重新定义阶段，我们用一个例子来加以说明：鹰蛋问题：有一堆共 M 个鹰蛋，一位教授想研究这些鹰蛋的坚硬度 E。他是通过不断从一幢 N 层的楼上向下...

2018-07-21

0 395