-
二叉堆简述
简述 对于堆，我个人的理解就是一种优先队列，从队列中取元素的时候总是取出最大（或最小）的元素。二叉堆是一种堆的一种实现形式，是一棵完全二叉树。对于二叉堆，我们显然可以分成两类：大根堆和小根堆，表示他每次取出的是最大元素还是最小元素。而大根堆一定是满足这样的一个性质，即：对于任意一个节点，他一定不大于他的父亲，而且不小于他的两个儿子。小根堆反之。 实现功能 以$O(n)$的时间建树，并以$O(logn)$的复杂度实现插入、寻找最小（或最大）值，修改元素，删除元素。 实现思路（小根堆）…
-
左偏树简述
简述 左偏树与二叉堆一样，是一种优先队列的实现。但是与二叉堆不一样，他不是一种完全二叉树，而是一种不平衡二叉树，这样做的目的是为了实现一个重要的性质--合并。通常的二叉堆并不能方便的实现两个堆之间的合并，而左偏树，却恰恰适合解决这样的问题。 实现功能 实现一个最小优先队列，是的插入、删除、合并等操作均在$O(logN)$的时间复杂度内完成。 实现思路 左偏树定义了一种节点叫“外节点”，即这个节点的左子树或者右子树为空。并且定义了一个性质叫“距离”，就是这个节点到他子孙中最近的外节点…
-
概率dp专题整理(2/2)
LightOJ 1027 A Dangerous Maze: 预先求出递推式，最后通过公式直接计算。 #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #include<vector> using namespace std; int gcd(int a, int b){ if (b ==…
-
数论基础专题小结
这个专题很杂，牵涉到很多数学公式和一些优化方法，还是要根据不同的题目来积累经验。 LightOJ 1282 Leading and Trailing: 这道题牵涉到求一个大数的前几位和后几位的方法，前者主要是通过对数进行处理，后者通过快速取模。 #include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<vector> using…
-
概率dp专题整理(1/2)
概率DP主要用于求解期望、概率等题目。转移方程有时候比较灵活，没有固定的范式，没有模版可言。正如大部分的dp题目一样，思考量远大于代码量。需要注意的是，一般求概率是正推，求期望是逆推。 LightOJ 1030 Discovering Gold: #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; int a[10…
-
区间dp专题小结
区间DP是一类在区间上进行动态规划的最优问题，一般是根据问题设出一个表示状态的dp，可以是二维的也可以是三维的，一般情况下为二维。然后将问题划分成两个子问题，也就是一段区间分成左右两个区间，然后将左右两个区间合并到整个区间，或者说局部最优解合并为全局最优解，然后得解。 这类DP可以用常规的for循环来写，也可以用记忆化搜索来写。一般情况下记忆化搜索的代码比较好写，所以一般都用dfs来代替获得dp值。然而说到底，这只是一种思想，具体的代码根据题目的不同差别很大，而且有很多需要考虑的细节。 POJ…
-
斜率优化dp专题小结
斜率优化dp是一种通过构造斜率表达式，用维护凸包的方法来去除多余的点以减少算法复杂度的方法。通常可以将问题规模减小一个维度，从而提高运行效率。 这个算法的关键是将dp的状态转移方程进行转换，比如对于如下状态转移方程： $$dp[i]=Min(dp[j]+M+(sum[i]-sum[j])^2),j\in [1,i),i\in [1,n]$$ 如果直接dp那么复杂度将会是(O(n_2)),某些情况下就会显得效率不够。这时候就可以用斜率dp进行优化，将其优化到$O(n)$。 首先我们需要将状态转移方…
-
一些常见OJ网站的整理
听说你们老喜欢刷题了，我就帮你们稍微整理下比较热门的刷题网站吧，这类网站其实有很多的，网上也能一抓一大把，在玩游戏玩累了，吹老牛吹烦了的时候多刷刷题还是非常有益身心健康的。 一般我们把这类的网站叫做在线评测系统，简称OJ(Online Judge)，主要用途是给广大程序员学习算法，或者广大学生备战程设比赛用的。过几天我们学校的ACM队应该也会招新了，到时也会提供一些学习资料和模拟比赛的机会，希望大家多多参与。 以下是一些比较有名气的OJ系统: 1. http://acm.hdu.edu.cn…
-
大组合数取模的Lucas定理
一般情况下，我们计算大组合数取模问题是用递推公式进行计算的： $$ C_n^m=(C_{n-1}^m+C_{n-1}^{m-1}) mod\ p $$ 其中p相对较小的素数。但是当n和m过大时，计算的耗费就急剧增加$O(mn)$，在实践中不适用。当这时候就需要Lucas定理进行快速运算: $$ C_n^m=\prod_{i=0}^{k}C_{n_i}^{m_i}\ mod\ p $$ 其中： $$ m=m_kp^k+m_{k-1}p^{k-1}+...+m_1p+m_0 $$ $$ n=n_kp…
-
Garbled Bloom Filters算法简述
简述 Garbled Bloom Filters（GBF） 算法是Bloom Filters （BF）算法的变形，并且结合了Shamir的信息分享算法，更好的解决了hash冲突的问题其形式上是将Bloom Filters算法中的BitSet数组转换成了字符串数组，数组中的每一个字符串长度为安全参数$\lambda$，可以通过调节这个参数来获得想要的安全性。该算法同Bloom Filters 一样，是一种有一定容错率的hash算法，对于存在于集合中的元素查询返回的值总是true，而对于不在集合中…