Wormholes Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 64177   Accepted: 23954 Description While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar becau…

2018年8月28日 0条评论 1点热度 阅读全文

博主链接 KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数,函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。-----摘要搜狗百科 一.KMP算法求解什么类型问题 字符串匹配。给你两个字符串,寻找其中一个字符串是否包含另一个字符串,如果包含,返回包含的起…

2018年7月18日 0条评论 1点热度 阅读全文

dijistra算法是求从源点s开始到其他点的最短路径问题。前提条件是带权值的边。权值为正数。 1.将每个点的距离设为无穷大,彼此都不连通。将这些点的集合设为S. 2.另一个集合为V。从源点s开始,距离设为0,放到集合V中。 3.设每条边是<u,v>。则通过dist(v) = min{dis(v),dist(u) + l(u,v)} 进行松弛操作。选取最小代价的点,放到集合V中,知道集合S中的元素被拿光结束。 注意:编码时可以通过数组 visited 来对两个集合进行区分。 bellman_ford算法…

2017年11月17日 0条评论 2点热度 阅读全文

基础练习 十六进制转十进制   时间限制:1.0s   内存限制:512.0MB         问题描述   从键盘输入一个不超过8位的正的十六进制数字符串,将它转换为正的十进制数后输出。   注:十六进制数中的10~15分别用大写的英文字母A、B、C、D、E、F表示。 样例输入 FFFF 样例输出 65535 #include<cstdio> int main() { long long n; scanf("%I64X"…

2017年11月16日 0条评论 1点热度 阅读全文

http://www.61mon.com/index.php/archives/200/

2017年8月12日 0条评论 2点热度 阅读全文

这个函数最近用了几次,就把它放到我的代码片吧,可以复用 在数组arrayNum[p:r]中查找第k(k > 0)个小的元素(下标为p+k-1) int findK(int arrayNum[], int p, int r, int k) { /** *在数组arrayNum[p:r]中查找第k(k > 0)个元素(下标为p+k-1) * p <= r && 0 < k && k <= p - r +1 (合法输入说明) *一个随机算法待加入,加入后可以避…

2017年3月16日 0条评论 1点热度 阅读全文

第一节、B树、B+树、B*树 1.前言:        动态查找树主要有:二叉查找树(Binary Search Tree),平衡二叉查找树(Balanced Binary Search Tree),红黑树(Red-Black Tree ),B-tree / B+-tree / B*-tree (B~Tree)。前三者是典型的二叉查找树结构,其查找的时间复杂度O(log2N)与树的深度相关,那么降低树的深度自然会提高查找效率。 但是咱们有面对这样…

2017年3月2日 0条评论 9点热度 阅读全文

51nod题目地址:点击打开链接 有若干个活动,第i个开始时间和结束时间是[Si,fi),活动之间不能交叠,要把活动都安排完,至少需要几个教室? 分析:能否按照之一问题的解法,每个教室安排尽可能多的活动,即按结束时间排序,再贪心选择不冲突的活动,安排一个教室之后,剩余的活动再分配一个教室,继续贪心选择…… 反例: A:[1,2)  B:[1,4) C:[5,6) D:[3,7) 已经按结束时间排好顺序,我们会选择 教室1: A C 教室2:  B 教室3:  D 需要3个教室。 但是如…

2016年4月29日 0条评论 14点热度 阅读全文

51nod题目地址:点击打开链接 有若干个活动,第i个开始时间和结束时间是[Si,fi),活动之间不能交叠,要把活动都安排完,至少需要几个教室? 分析:能否按照之一问题的解法,每个教室安排尽可能多的活动,即按结束时间排序,再贪心选择不冲突的活动,安排一个教室之后,剩余的活动再分配一个教室,继续贪心选择…… 反例: A:[1,2)  B:[1,4) C:[5,6) D:[3,7) 已经按结束时间排好顺序,我们会选择 教室1: A C 教室2:  B 教室3:  D 需要3个教室。 但是如…

2016年4月29日 0条评论 8点热度 阅读全文

51nod地址:点击打开链接 n个人,已知每个人体重,独木舟承重固定,每只独木舟最多坐两个人,可以坐一个人或者两个人。显然要求总重量不超过独木舟承重,假设每个人体重也不超过独木舟承重,问最少需要几只独木舟? 分析:  一个显然的策略是按照人的体重排序。 极端化贪心策略,最重的人要上船——如果最重的人和最轻的人体重总和不超过船的承重,则他们两个占用一条船。否则(因为假设最重的人的体重也不超过船的承重了),最重的人单独占一条船。转变为(n – 1)或者(n – 2)的问题了。 关键在于这种贪心策略是正确的。我…

2016年3月31日 0条评论 3点热度 阅读全文