5 Lonverce

尚未进行身份认证

路漫漫其修远兮, 吾必将上下而求索. 衣带渐宽终不悔, 未成大神誓不退.

等级
TA的排名 13w+

C#利用斐波那契堆实现优先队列

        继上一章C#利用二叉堆实现优先队列之后,我们继续来探究一下关于优先队列的另一个实现—— 斐波那契堆(FibonacciHeap)。      相比起二叉堆中规中矩的实现而言,斐波那契堆的设计显得更为大胆而精妙。在这里,我们只讨论使用最频繁的两个操作:插入与移除,而不考虑优先级变更与关键字搜索等功能,因为这两个功能对我而言绝不常用,而且会使我们的结构变得复杂,所以我任性地作出...

2018-03-27 12:35:17

C#利用二叉堆实现优先队列

        相信许多人都发现并好奇,.NetFramework为什么没有为我们提供优先队列这种数据结构的封装实现?其实不然,基于红黑树实现的SortedDictionary泛型类恰是优先队列的一种实现,而且其功能更为灵活。不过对于我而言,却总希望写一个利用二项堆实现的优先队列,尽管这两者从算法复杂度的层面上而言相差无几,都能在O(log2N)内提供添加和移除操作,但实际上,算法编码的复杂度...

2018-03-17 17:35:49

C++并行编程(二): 利用C++标准库实现Semaphore信号量

    在上一节中,我们使用C++11标准库中的提供的条件变量以及互斥变量封装实现了两个仿Windows内核事件类:ManualResetEvent和AutoResetEvent。在这一节中,我们将继续使用标准库中提供的类来实现高仿信号量Semaphore。而后文的代码中,有使用到上一节代码中定义的某些抽象基类,看不懂的读者们可以查阅上一章《C++并行编程(一):利用C++标准库实现仿Windo...

2018-02-27 17:57:13

C++并行编程(一): 利用C++标准库实现仿Windows内核事件对象

    我们知道,无论是Linux还是Windows,在底层的操作系统API中都提供了一些与线程间同步操作相关的内核对象,就以我最熟悉的Windows讲起,就提供了诸如临界区(关键段)、事件、互斥变量、条件变量、信号量、读写锁、旋转锁甚至原子操作等等的一系列方式,而Linux中也提供了类似的机制。由于这些底层机制在应用程序开发中经常使用,但在不同操作系统平台中调用的API又不一样,所有可见市面上有...

2018-02-27 11:46:56

( 题解 )第六届蓝桥杯决赛试题 -- 完美正方形 (线段树 + 深搜)

题目:完美正方形如果一些边长互不相同的正方形,可以恰好拼出一个更大的正方形,则称其为完美正方形。历史上,人们花了很久才找到了若干完美正方形。比如:如下边长的22个正方形23467812131415161718212223242627285060如【图1.png】那样组合,就是一种解法。此时,紧贴上边沿的是:6050紧贴下边沿

2016-05-17 15:52:35

蓝桥杯算法提高 -- 学霸的迷宫

思路:A*寻路配合优先队列#include#include#include#include#includeusingnamespacestd;constintMAXINT=0x70FFFFF;//格子类classCell{public: staticintDestRow,DestCol;public: boolIsVisit

2015-12-04 15:53:43

蓝桥杯算法提高 -- 金陵十三钗

思路: 这道题最基本的做法就是DFS直接暴力破解,这样的复杂度毫无疑问的O(n!),是不能完全AC的.那么,看到这道题问的是最优解,那么想必跟动态规划能扯上关系了,但是咋一看,转移方程可不太好写,一开始的时候我还写了个错的转移式,妄想能在O(n^2)内求解...*_*...言归正传,使用动态规划的话,要注意的是:在为第i个妓女匹配时,需要在前i-1

2015-12-03 19:08:17

蓝桥杯算法提高 -- 周期字串

思路:相信大家都很容易想到,根据字符串的长度,求出所有约数,然后按照约数的顺序来检验.但是检验的策略非常重要,最重要的两点就是: (1)对每个不同长度周期的字符串,最多只判断一次. (2)如果长度为N的字符串在原串的周期检验中不成立,则长度为N的约数的字符串也不会成立.根据上述的结论,我们可以大概感觉到,我们不仅要求约数,还要求约数的约数(依次递归

2015-12-03 14:39:43

Poj_3744 解题报告

原题我就不提供了,大家可以自己上www.POJ.org搜索.大概题意:小明要通过一条"地雷之路".路上有好多个地雷,而小明现在站在路的开端(1号位置),小明有P的概率向前移动一步,有(1-P)的概率向前移动两步,问小明能安全通过这条路的概率.输入格式:1.输入多组数据,以EOF结束2.每组数据包括两行,第一行输入N,P,分别表示地雷数目和走一步的概率

2015-04-23 12:14:27

第六届蓝桥杯省赛试题--垒骰子 以矩阵的方法实现 解题报告

本贴声明:关于这道题的基本解法,我在之前曾经发表过,以动态规划的方式在O(N)的时间复杂度内求解,但对于数据规模为10^9的数据而已,O(N)显然是不够的,当时我受困良久.但幸运的是,某网友给了我一个万分有用的建议,以矩阵的方式的进行求解.当我实现以后,我发现这是一个O(log(2)(N))[注:以2为底N的对数]的算法,速度之快,毋庸置疑. 这道题的矩

2015-04-21 13:23:31

第六届蓝桥杯校园选拔赛试题---派遣敢死队 解题报告

原题:  G将军有一支训练有素的军队,这个军队除开G将军外,每名士兵都有一个直接上级(可能是其他士兵,也可能是G将军)。现在G将军将接受一个特别的任务,需要派遣一部分士兵(至少一个)组成一个敢死队,为了增加敢死队队员的独立性,要求如果一名士兵在敢死队中,他的直接上级不能在敢死队中。请问,G将军有多少种派出敢死队的方法。注意,G将军也可以作为一个士兵进入敢死队。输入格式输入的第一

2015-04-18 15:49:49

第六届蓝桥杯试题--生命之树 解题报告

原题:在X森林里,上帝创建了生命之树。他给每棵树的每个节点(叶子也称为一个节点)上,都标了一个整数,代表这个点的和谐值。上帝要在这棵树内选出一个非空节点集S,使得对于S中的任意两个点a,b,都存在一个点列{a,v1,v2,...,vk,b}使得这个点列中的每个点都是S里面的元素,且序列中相邻两个点间有一条边相连。在这个前提下,上帝要使得S中的点所对应的整数的和尽量大。

2015-04-17 18:47:50

第六届蓝桥杯省赛试题--垒骰子 解题报告

第六届蓝桥杯省赛试题--叠骰子解题报告

2015-04-15 16:22:53
勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!