【算法导论】排序（一）

2017年02月05日 65 阅读

【算法导论】排序（一）2014-01-01 csdn shuangde800虽然久闻大名，但第一次接触算法导论，是看了网易公开课MIT的《算法导论》课，记得 第一集就讲到了 插入排序和归并排序。几个星期前也买了算法导论这本书，准备慢慢啃~这星期主要在看前两 部分，除了对于讲渐进时间、递归式分析这些东西感到云里雾里的，其它的都就感觉越看越有觉得入 迷，果然不愧是一本经典之作好吧，开始。本文主要是用C++把书中的算法实现，以及一些笔记。一、插入排序。插入算法的...

【算法导论】排序 （二）：堆排序

2017年02月05日 59 阅读

【算法导论】排序 （二）：堆排序2014-01-01 csdn shuangde800四、（1）堆排序第一次听堆排序是在107lab听忠哥讲的，但是没讲怎么实现。那时刚看了数据结 构的二叉树，还以为要通过指针建立二叉树的方式来实现，觉得挺难的。其实堆排序实现没有想象中 的那么难。“堆”这个词最初是在堆排序中提出来的，但后来就逐渐指”废料收集储存区“，就像程 序设计语言Lisp和Java中所提供的设施那样。我们...

【算法导论】排序 （三）：快速排序 深入分析

2017年02月05日 52 阅读

【算法导论】排序 （三）：快速排序 深入分析2014-01-01 csdn shuangde800五、快速排序快速排序是最常用的一种排序算法，包括C的qsort，C++和Java的sort，都采用了快 排（C++和Java的sort经过了优化，还混合了其他排序算法）。快排最坏情况O（ n^2 ），但平均效率 O（n lg n），而且这个O（n lg n）几号中隐含的常数因子很小，快排可以说是最快的排序算法，并非浪得虚名 。另外它还是就地排序。快速排序是基于...

【算法导论】排序 （四）：决策树、线性时间排序（计数、基数、桶排序）

2017年02月05日 78 阅读

【算法导论】排序 （四）：决策树、线性时间排序（计数、基数、桶排序）2014-01-01 csdn shuangde800到目前为止，一共整理总结了五大排序算法：1、插入排序2、冒泡排序、选择排序、交换排序 （把这三种方法归为一种，因为他们的思想本质上都是一样的）3、归并排序4、堆排序5、快速排序以上五种排序都可以称为“比较排序”，顾名思义，因为他们都是基于比较元素 来决定其相对位置的。其中前两种的时间为O（n^2），归并排序和堆排...

DES加密解密算法详解

2017年02月05日 68 阅读

DES加密解密算法详解2014-01-01近段时间因为项目需要，所以一直致力于网络与信息安全方面，免不了涉及了信息的加密与解密，所以这些日子一直在苦苦钻研密码学。密码学是一门古老的学科，在密码学发展的历史上，出现了多种加密方法，又很早的古典加密算法，后来又出现了更成熟的分组密码，公钥密码及流密码等，因为我只涉及了分组公钥密码，所以在这篇文章中就暂且先介绍分组密码，在说分组密码之前要说的就是密码学中常见的两种体制，一种是对称密码体制，一种是非对称密码体制，也...

适用于连续资源块的数组空闲链表的算法

2017年02月05日 70 阅读

适用于连续资源块的数组空闲链表的算法2014-01-01 51cto dog250如何来管理空闲资源，显而易见的是组织成一个双向链表，称作freelist，然后每次从该链表上取出一个，释放的时候再放回去。为了减少碎片，最好的策略就是优先分配最近释放掉的那个，如果能考虑合并的话，类似伙伴系统那样，就再好不过了，本文给出的是一个通用的可以将资源映射到一个整型ID的资源分配算法，完全基于一个数组，不需要内存管理，也不需要分配结构体。组织链表的时候，内存管理要耗去...

分析分析师：数据科学部门如何建.

2017年02月05日 76 阅读

分析分析师：数据科学部门如何建.2014-01-01 csdn 问天鼓很多大公司都宣称在建立数据科学部门，这个部门该如何组建，大家都在摸石头过河。O ‘reilly Strata今年 六月份发布了报告 《Analyzing the Analyzers》，比较清晰的阐述了数据科学部门 所需要的不同角色及其技能。重点内容翻译如下：数据科学家的分类研究方法自我认识请被调查者用常用的5级标准（从完全同意到完全不同意）来回答 “我觉得自己是一...

算法：CodeForces #196（Div. 2） 337D Book of Evil（树形dp）

2017年02月05日 57 阅读

算法：CodeForces #196（Div. 2） 337D Book of Evil（树形dp）2014-01-01 csdn shuangde800题意给一棵n个结点的树，任意两个节点的距离是指连接两点的最短的边数在树上的某个结点有一个“恶魔之书”，这本书会让距离它d以内的节点都受到影响已知有m个节点收到了影响，问最多有几个结点可能放着“恶魔之书”？思路要判断某个点是不是放着书，就要判断这个点的周围d距离以内是否包含所有受影响的m节点而如果某个节点距...

算法：hdu 1011 Starship Troopers （树形背包dp）

2017年02月05日 61 阅读

算法：hdu 1011 Starship Troopers （树形背包dp）2014-01-01 csdn shuangde800题意有n个洞穴编号为1～n，洞穴间有通道，形成了一个n-1条边的树, 洞穴的入口即根节点是1。每个洞穴有x只bugs，并有价值y的金子，全部消灭完一个洞穴的虫子，就可以获得这个洞穴的y个金子.现在要派m个战士去找金子，从入口进入。每次只有消灭完当前洞穴的所有虫子，才可以选择进入下一个洞穴。一个战士可以消灭20只虫子，如果要杀死x...

算法：hdu 1561 The more, The Better （树形背包dp）

2017年02月05日 61 阅读

算法：hdu 1561 The more, The Better （树形背包dp）2014-01-01 csdn shuangde800题目ACboy很喜欢玩一种战略游戏，在一个地图上，有N座城堡，每座城堡都有一定的宝物，在每次游戏中ACboy允许攻克M个城堡并获得里面的宝物。但由于地理位置原因，有些城堡不能直接攻克，要攻克这些城堡必须先攻克其他某一个特定的城堡。你能帮ACboy算出要获得尽量多的宝物应该攻克哪M个城堡吗？思路简单树形背包dp,当作树形背包...

算法：HDU 2196 Computer（树形dp经典）

2017年02月05日 56 阅读

算法：HDU 2196 Computer（树形dp经典）2014-01-01 csdn shuangde800题意：给出一棵树，求离每个节点最远的点的距离思路：把无根树转化成有根树分析 ，对于上面那棵树，要求距结点 2的最长距离，那么，就需要知道以2为顶点的子树（蓝色圈起的部分，我们叫它Tree（2）），距顶点2的最 远距离L1还有知道2的父节点1为根节点的树Tree（1）-Tree（2）部分（即红色圈起部分），距离结点1 的最长距离+dist（1,2） ...

算法：hdu 3586 Information Disturbing（树形dp + 二分）

2017年02月05日 58 阅读

算法：hdu 3586 Information Disturbing（树形dp + 二分）2014-01-01 csdn shuangde800题意给一棵n个节点的树，节点编号为1～n，根节点为1。每条边有权值，砍掉一条边要花费cost（w）要砍掉一些边， 使得每个叶子节点无法走到根节点。要求砍掉花费总和不能超过m的情况下，让每条 边花费上限尽量低思路二分可以砍的边的权值上限，然后树形dpf[i]: 表示让i子树所有的叶 子节点无法到达i点的最小花费f[i...

算法：hdu 4003 Find Metal Mineral （树形背包dp）

2017年02月05日 57 阅读

算法：hdu 4003 Find Metal Mineral （树形背包dp）2014-01-01 csdn shuangde800题意给一棵n个节点的树, 节点编号为1~n, 每条边都有一个花费值.有k个机器人从S点出发, 问让 机器人遍历所有边,最少花费值多少？思路很好的一题, 推荐！前天看的这题, 今天才想出来的. 方法想出来后,代码很简单最近做的几道dp,都是一开始没什么想法,然后过两天再想就想出来了,也许是因 为人的潜意识其实会一直在想某个问题翻...

算法：hdu 4044 GeoDefense （树形dp | 多叉树转二叉树）

2017年02月05日 52 阅读

算法：hdu 4044 GeoDefense （树形dp | 多叉树转二叉树）2014-01-01 csdn shuangde800题意这是一个塔防游戏，地图是一个n个编号为1～n的节点的树， 节点1是敌人的基地，其他叶子 节点都是你的基地。敌人的基地会源源不断地出来怪兽，为了防止敌人攻进你的基地，你可以选择造塔。每个节点最多只能造一个塔，且节点i可以有ki种塔供你选择，价钱和攻击力分别为price_i, power_i攻击力power_i，效果是让敌人经...

算法：hdu 4597 Play Game（区间dp）

2017年02月05日 57 阅读

算法：hdu 4597 Play Game（区间dp）2014-01-01 csdn shuangde800题意Alice和Bob玩一个游戏，有两个长度为N的正整数数字序列，每次他们两个只能从其中一个序 列，选择两端中的一个拿走。他们都希望可以拿到尽量大的数字之和，并且他们都足够聪明，每次都选择 最优策略。Alice先选择，问最终Alice拿到的数字总和是多少？思路这题应该算是区间dp吧， 可以看一下这题的原型：其他规则都一样，但是只有一个数字序列，也是每...

算法：HDU 4649 Professor Tian（反状态压缩dp，概率）

2017年02月05日 59 阅读

算法：HDU 4649 Professor Tian（反状态压缩dp，概率）2014-01-01 csdn shuangde800题目大意初始有一个数字A0， 然后给出A1,A2..An共n个数字，这n个数字每个数字分别有一个操 作符，&，|，^且每个数字出现的概率是pi如果某个数字出现了，那么就和前面的数字用 它的操作符进行位运算。问最终的期望值是多少？思路这题官方题解说是反状态压缩 ，还是第一次做这种题。知道了怎么表示状态这题就觉得不难做了，赛...

算法：HDU 4679 Terrorist’s destroy（树形dp | 多校8）

2017年02月05日 55 阅读

算法：HDU 4679 Terrorist’s destroy（树形dp | 多校8）2014-01-01 csdn shuangde800题意给一棵树，每条边有个权值，要删掉一条边，删掉以后会变成两颗子树，设两个子树的直径分别 为d1, d2，删掉的这条边权值为w问删掉哪一条边，使得w*max（d1, d2）的值最小？思路典型的 树形dp, 但比赛时的代码写得非常搓，200+行，还好1A了f（u, 0）：以u点为顶点的子树的直径f （u, 1）：以u的父...

算法：HDU 4681 String （dp, LCS | 多校8）

2017年02月05日 60 阅读

算法：HDU 4681 String （dp, LCS | 多校8）2014-01-01 csdn shuangde800题意给出3个字符串A,B,C，要你找一个字符串D, 要满足下面规定a） D是A的子序列b） D是B 的子序列c） C是D的子串求D的最大长度要注意子序列和子串的区别，子序列是不连续的，字串是连 续的思路由题目可知，C一定是A和B的子序列，那么先假设C在A和B中只有一个子序列，看下 面例子：abcdefdegacebdfghcf可以看到&...

算法：poj 1155 TELE （树形背包dp）

2017年02月05日 57 阅读

算法：poj 1155 TELE （树形背包dp）2014-01-01 csdn shuangde800题意某收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结 构，这棵树的根结点位于足球比赛的现场，树叶为各个用户终端，其他中转站为该树的内部节点。从 转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的，一场转播的总费用等于传输信号 的费用总和。现在每个用户都准备了一笔费用想观看这场精彩的足球比赛，有线电视网有权决定...

算法：poj 1523 SPF（tarjan求割点）

2017年02月05日 59 阅读

算法：poj 1523 SPF（tarjan求割点）2014-01-01 csdn shuangde800题意给一个连通的无向图，求这个图的所有割点，并且输出各个割点和相连的边去掉之后，会变成几 个连通分量思路用tarjan求割点的基础题，要求对tarjan算法的原理真正搞懂，这题就水了。代码/**=====================================================* This is a solution for AC...