糖醋盐明清 - 个人主页动态 - 牛客网

发布(94) 评论刷题收藏

2019-08-09 20:51

已编辑

南阳理工学院 C++

字典树模板

#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 find(char* data); /* carbohydrate cart carburetor caramel caribou carbonic cartilage carbon carriage carton car carbonate */ int main() { char strs[INF][...

0 点赞评论收藏

分享

2019-08-09 20:51

已编辑

南阳理工学院 C++

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

读题可以知道当成环的时候会有冲突，当不止有一个拓扑排序的时候信息不完全。 当有相等的时候可以用并查集把他们当成一个节点来处理； 代码如下：  #include<stdio.h> #include<string.h> #define mmset(a,b) memset(a,b,sizeof(a)) const int N = 100005; const int M = 200005; struct edge { int x, y, flag ; }; struct node { int to,w,next; }; node edges[M]; edge data[M]; ...

0 点赞评论收藏

分享

2019-08-09 20:51

已编辑

南阳理工学院 C++

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

循环不定式可以用来证明一个算法的正确性： 比如我现在有一个算法A,我要证明它的正确性：步骤如下： 第0步：定义循环不定式； 第1步：证明循环不定式在算法开始的时候是正确的； 第2步：证明循环不定式在算法每次迭代(循环)的时候是正确的； 第3步：证明循环不定式在算法结束时是正确的； 以下是用循环不定式来证明冒泡排序的正确性： 首先看代码：  #include<stdio.h> int main() { int data[15]; int len = 15; for(int i = 0; i < 15; i++) { scanf("%d",&data[...

0 点赞评论收藏

分享

2019-08-09 20:51

已编辑

南阳理工学院 C++

0 点赞评论收藏

分享

2019-08-09 20:51

已编辑

南阳理工学院 C++

图论-最小生成树

最小生成树：一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。 最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出；   一：kruskal(克鲁斯卡尔) 将图中的每条边按从小到大排个序。然后按这个顺序建个树就是最小生成树。 kruskal主要是建树过程中不能出现环，如果加入当前边，会形成环，就放弃这个边，继续向下建树。直到这个树 有n-1条边即可(n个点形成的树一定有n-1条边)； 我们可以用并查集来判断是否成环： 代码如下(复杂度为：Elogn)  #include<stdio.h> #...

0 点赞评论收藏

分享

2019-08-09 20:55

已编辑

南阳理工学院 C++

图论-最短路总结

一：迪杰斯特拉(Dijkstra)算法        Dijkstra算法是单源最短路算法。他能求出一个点到其他点的最短距离。这个点叫做源点； 他的主要思路就是将所有顶点分为两部分，一部分是点集合是Q,剩下部分点集合是P;其中Q集合的点到源点的最短距离 已经求出来，P集合是待求到源点最短距离的点集合； Dijkstra就是对这两个集合进行操作。 我们假定源点是S. 第一步:我们将两个集合初始化，Q集合只有S点，P集合是除S点剩下的点。因为S点到S点的最短距离已经确定，是0； 第二步：在P集合选取出一个距离S点最近的一个点，然后通过这个点对S点和其他点进行松弛； 第三步：重复第二步，直到这个过程...

0 点赞评论收藏

分享

2019-08-09 20:55

已编辑

南阳理工学院 C++

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

前面已经说过kmp是一种字符串匹配算法。就是给你一个模式串p,和一个主串m。让你找出p在m中的位置； ac自动机与kmp类似，也是一种字符串匹配算法。与kmp不同的是，kmp是单模式的字符串匹配算法。 而ac自动机是多模式的字符串匹配算法。也就是给你n个模式串p1,p2,p3.......pn，和一个主串m。,让你找出 这n个模式串在m中的位置。  有的同学可能会进行n次kmp来解决多模式字符串匹配的问题，但是这样时间复杂度太高了，所以我们考虑用ac自动机。  在讲解ac自动机之前，我必须假定你已经会字典树(如果你不会的话请自行百度)和kmp(kmp不会的可以自行百度也可以看一下 我之前写km...

0 点赞评论收藏

分享

2019-08-09 20:45

已编辑

南阳理工学院 C++

从动态该规划角度理解kmp

kmp是一种高效的字符串匹配算法(模式匹配算法)； 给你一个主串m,模式串p。kmp可以找出p在m中的位置； 比如主串m：abadabaad和模式串p:abaa;那么p在m中的位置是5; 如果是纯暴力(朴素的模式匹配算法)的话时间复杂度会达到O(n*m),是比较高的； 但是用kmp的话，时间复杂度会达到O(n+m); kmp是在朴素的模式匹配算法上进行优化的算法，我们首先来用一张图看一下朴素模式匹配的算法逻辑：  首先定义两个指针i,j; i指向主串m,j指向模式串p; 刚开始i,j都指向字符串的首字符； 0.    m[1] == p[1],两者匹配，i++,j++;然后继续比较，直到不匹配...

0 点赞评论收藏

分享

2019-08-09 20:53

已编辑

南阳理工学院 C++

关于oj造数据主要用到的就是随机函数和文件流  1.随机函数是rand(),头文件为<cstdlib> 用法： int res = rand()%b + a; res是从a开始(包括a)连续数b个数这个区间中的一个随机数，（ res = [a,b) ）; 需要注意的是如果不设置随机种子的话，那么每次随机出来的数是一样的 设置随机种子函数srand();头文件<cstdlib>; 这里我们用时间作为随机种子，因为程序运行很快，而时间是以秒为单位的，所以我们要用到Sleep(1000); 代码如下  #include<stdio.h> #include<c...

0 点赞评论收藏

分享

2019-08-09 20:55

已编辑

南阳理工学院 C++

线段树002-区间修改

接下来讲解一下区间修改： 在线段树001-概述中讲了单点修改，现在又增加了一种操作将区间x~y的值修改为v; 比如在下面这个图中我要将1~5区间的值全都改为v;  正常人的思维是把1~5这个区间的修改看成对点1,2,3,4,5的单点修改；但这样的复杂度是nlog(n)是比较高的；  我们换一种想法，在修改区间的时候我们仍然像区间查询一样自上而下的寻找要修改的区间。那么我们最后 找到区间是1~3和4~5这两个区间。 我们把代表这两个区间的节点的值进行修改；这样一来我们就完成了区间修改； 但是这样就会出现新的问题，我只是修改了这两个节点的值，那么如果我要查找2~5区间的值的加和，按照区间查询的步骤...

0 点赞评论收藏

分享

2019-08-09 20:55

已编辑

南阳理工学院 C++

线段树 001- 概述

线段树就是一个能高效维护动态区间的一个数据结构； 他能把一个区间分成多个区间，这些区间根据它们的之间的关系形成一个树形结构。 这个过程可以构建出一颗完全二叉树。 其中线段树的操作有：         1.修改         2.查询  比如我们现在要维护一个长度为n的区间的和，那么当n=10的时候，该区间所对应的树为：  可以发现每个节点代表一个区间，每个节点存的是该区间的和； 每个节点的儿子的区间加起来一定等于该节点所代表的区间。这些都是很显然的性质； 所以我们建树的时候应该自底而上的建树。也就是说我必须先把所有的儿子先建好，然后开始根据儿子的值构建父亲； 该部分的代码如下  #inclu...

0 点赞评论收藏

分享

2019-08-09 20:55

已编辑

南阳理工学院 C++

浅谈动态规划优化

动态规划是解决多阶段决策最优化问题的一种思想方法。 有时动态规划的时间复杂度过高，需要我们对动态规划进行优化。 对动态规划进行优化的普遍方法是重新定义阶段，我们用一个例子来加以说明：  鹰蛋问题： 有一堆共 M 个鹰蛋，一位教授想研究这些鹰蛋的坚硬度 E。他是通过不断从一幢 N 层的楼上向下扔鹰蛋 来确定 E 的，当鹰蛋从第 E 层楼及以下楼层落下 时是不会碎的，但从第（E+1）层楼及以上楼层向下落时会摔碎。 如果鹰蛋未摔碎，还可以继续使用，但如果鹰蛋全碎了却仍未确定 E，这显然是一个失败的实验。教授希望实验是成功的 这里假设所有的鹰蛋都具有相同的坚硬度。给定鹰蛋个数 M 与楼层数 N。 要求...

0 点赞评论收藏

分享

2019-08-09 21:01

已编辑

南阳理工学院 C++

状态压缩dp(状压dp)

注：在涉及到位运算时，一定要注意位运算的优先级。该加的括号一定要加 状压dp是一类比较难理解的dp; 在讲状压dp之前，我们应该清楚所有的dp是解决多阶段决策最优化问题的一种思想方法； 请注意多阶段这三个字： 经过前面三种背包的学习，可以发现如何定义状态是解决动态规划最重要的一步； 状态的定义也就决定了相当于阶段的划分； 在背包问题中，我们通过物品的件数i和背包的容量j来定义状态或者说是划分阶段； 动态规划多阶段一个重要的特性就是无后效性。无后效性就是值对于某个给定的阶段状态，它以前各阶段的状态无法 直接影响它未来的发展，而只能通过当前的这个状态。换句话说影响当前阶段状态只可能是前一阶段的状态...

0 点赞评论收藏

分享

2019-08-09 20:57

已编辑

南阳理工学院 C++

关于精度的问题

在一些问题中经常会遇到一些关于精度的保留； 1.要求保留小数后n位小数：代码如下 #include<stdio.h> int main() { double num = 1.123456789; int n = 6; printf("%0.*lf\n",n,num);    //1.123457 return 0; } 注意，他会在小数点第n+1位四舍五入； 2.要求截取小数后n位，也就是不四舍五入： #include<stdio.h> #include<math.h> int main() { double num = 1.123456...

0 点赞评论收藏

分享

2019-08-09 20:57

已编辑

南阳理工学院 C++

stl-二分找上下界

下面介绍两个函数用来查找一个有序序列关键字的上下界 upper_bound返回第一个大于的元素的下标；  lower_bound返回第一个大于或等于元素的下标； 代码如下：  #include<stdio.h> #include<algorithm> using namespace std; int main() { int data[10] ={0,1,1,2,2,2,2,3,4,7}; //upper_bound(a,b,key) 从区间a,b-1查找key,找不到返回b(注意，此时a,b是迭代器类型) int res = upper_bound(data,data...

0 点赞评论收藏

分享

创作者周榜

更多

关注他的用户也关注了：

牛客网
牛客企业服务