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

2016年07月27日 39 阅读

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

DES加密解密算法详解

2016年07月27日 37 阅读

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

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

2016年07月27日 34 阅读

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

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

2016年07月27日 38 阅读

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

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

2016年07月27日 33 阅读

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

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

2016年07月27日 36 阅读

算法：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）

2016年07月27日 38 阅读

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

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

2016年07月27日 36 阅读

算法：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 + 二分）

2016年07月27日 36 阅读

算法：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）

2016年07月27日 32 阅读

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

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

2016年07月27日 35 阅读

算法：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）

2016年07月27日 39 阅读

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

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

2016年07月27日 38 阅读

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

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

2016年07月27日 34 阅读

算法：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）

2016年07月27日 34 阅读

算法：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）

2016年07月27日 34 阅读

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

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

2016年07月27日 34 阅读

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

算法：poj 1655 Balancing Act（树形dp）

2016年07月27日 36 阅读

算法：poj 1655 Balancing Act（树形dp）2014-01-01 csdn shuangde800题意一n个节点的棵树，去掉某个节点后，会变成一个森林.这个森林中的每个树都有个节点数量， 其中最大节点数设为max问删除某个节点后，max最小可以多少？思路和poj-3107 GodFather完全一样！ 不想吐槽了。。。其实本来不想发这篇，不过发现今天是八月最后一天，而且 还差一篇就发了80篇了。。于是。。就很邪恶的水了代码/**=====...

算法：poj 1947 Rebuilding Roads （树形背包dp）

2016年07月27日 38 阅读

算法：poj 1947 Rebuilding Roads （树形背包dp）2014-01-01 csdn shuangde800题意给一棵树,问最少删掉几条边.使得剩下的子树中有节点个数为p个的思路几天前就看了 这题, 但是没什么想法,之后每天都有去想一下, 直到今天, 在我对自己方法还有怀疑的情况下,竟然AC了 ..f（i, j） 表示子树i,保留j个节点的最少删边次数, 注意,这里保留的j个节点的子树,是指根节点为i的且有j个节点的子树.这样理解的话,...

算法：poj 2378 Tree Cutting（树形dp）

2016年07月27日 36 阅读

算法：poj 2378 Tree Cutting（树形dp）2014-01-01 csdn shuangde800题意给一颗n个结点的树，节点编号为1~n，把删除一个节点之后，剩下的分支中节点数量最多的数 量不大于总数量一半的编号全部按顺序输出思路和poj-3107 GodFather完全一样，只是输出不一样。 改为<=n/2的就输出即可。代码/**===================================================...