Lonverce-CSDN博客

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

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

2018-03-27 12:35:17 707

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

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

2018-03-17 17:35:49 1256

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

题目 :完美正方形如果一些边长互不相同的正方形，可以恰好拼出一个更大的正方形，则称其为完美正方形。历史上，人们花了很久才找到了若干完美正方形。比如：如下边长的22个正方形2 3 4 6 7 8 12 13 14 15 16 17 18 21 22 23 24 26 27 28 50 60如【图1.png】那样组合，就是一种解法。此时，紧贴上边沿的是：60 50紧贴下边沿

2016-05-17 15:52:35 12037

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

思路 : A* 寻路配合优先队列#include #include #include #include #include using namespace std; const int MAXINT = 0x70FFFFF;// 格子类class Cell{public: static int DestRow,DestCol;public: bool IsVisit

2015-12-04 15:53:43 2601

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

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

2015-12-03 19:08:17 3347 2

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

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

2015-12-03 14:39:43 2247

原创 Poj_3744 解题报告

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

2015-04-23 12:14:27 742

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

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

2015-04-21 13:23:31 5726 6

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

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

2015-04-17 18:47:50 5449 1

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

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

2015-04-15 16:22:53 8704 6

Lonverce的专栏