最优树(Huffman) 最优树可以记忆为:越是距离根节点近的点的权值越大,离根节点越远的点的权值越小, 节点i,权值 $w_i$ ,深度为 $l_i$ ,使得 $\Sigma_{i}^{i=n} w_i * l_i$ 最小,那么此数就是Huffman树 二叉Huffman树 通过最小堆来从树的叶子节点建树, 1.n个节点 $w_i$ push进入priority_queue(优先队列来模拟最小堆), 2019-04-27 算法 最优树
质数筛 1不是质数 一个数只能被1和自己整除的数叫做质数 数N,如果不是质数,那么N一定有一个$<=sqrt(N)$的约数 试除法,一个一个试 E氏筛 任意一个数N的倍数一定不是质数,2N,3N……求 1~N之间的质数 1234567891011const int maxn =1e6;int prime[maxn];for (int i=2;i<=sqrt(n);i++) & 2019-04-26 算法
trie异或最大值2道例题 The XOR Largest Pair题目:在给定的N个整数中选出2个进行^运算,得到结果最大的是多少? 思路 将N个正数按照二进制位(从高位到低位)存到字典树中,求^ 的最大值,意思是每一位都尽量走反方向的,本来该位为0,树中有1就走1,没有则继续走0,这样求得的结果一定是最接近^的最大值, 可以变插入变询问^的最大值,然后更新ans,因为两两相互查询,前面的插入的数没有和后面 2019-04-26 算法 trie
trie数组模拟 自闭 数组模拟trie1.trie存的是字符串,从s[0],开始存 二维数组,第一维记录节点的编号,第二维的索引代表字符,数组值存 节点编号(26个指针,指向下一个节点)1234567891011121314151617181920212223const int maxn=1e6;int tot = 0;//全局变量,记录所以节点的数量int endp[maxn];//每个节点编号都可能作为 2019-04-23 算法 trie
poj2442Sequence(堆) 题目思路:m个长度为n的序列,每个序列中任取一个,构成 $n^m$ 个和,求其中最小的n个和 当m=2时,求2个序列中,任取一个所构成和中的n个最小和, 将2个序列从小到大排序,最小的一定是 $A[1]+B[1]$ ,那么下一个最小的是 $min(A[1]+B[2],A[2]+B[1])$ ,若此时最小的为A[2]+B[1],下一个最小状态从当前最小状态的下标进行移动,那么下一个 2019-04-21 算法 堆
poj2823_滑动窗口(单调队列) 单调队列滑动窗口 如果没有窗口的限制,而求[0,i]的最值,模拟单调栈(一头不变)解决,求最大值就维护一个单调递减的,输出栈的底部(模拟的栈),求最小值同理 当窗口限制的时候,我开始想的是队列存值 (用单调队列来维护窗口内的值),如果仅仅存的是值,那么将无法知道队列中值是否在窗口内, 此时如果队列存的是 该值的下标那么将很好解决窗口的范围问题, 1234567891011121314 2019-04-21 算法 单调队列
poj1456_Supermarket(最小堆) 题目思路: 题目给的是时间$t_i$ 意思是:距离过期的时间,只要 $[1,t_i]$ 之内被卖出就行了 将时间从小到大排序,维护一个小根堆, 堆为空,加入, 当不为空时,如果 $t_i$ > que.size() 意思是当前物品距离过期的时间大于已经卖出的个数,那么该物品一定可以卖出 如果 $t_i$ = que.size(),判断堆顶的卖出的最小利润是否小于该物 2019-04-21 算法 堆
动态维护中位数 暴力 开一个priority_queue push pop ,,,,,,, 太慢了 1234567891011121314151617181920212223242526272829#include <iostream>#include <queue>#include <vector>using namespace std;const int maxn=1 2019-04-20 算法
leetcode_042 题目思路:先找到最大值,分别从两边开始遍历,遍历时用head记录当前最高的,遇到height[i]< height[head]就算入面积中 1234567891011121314151617181920212223242526272829303132333435363738394041424344#include <iostream>using namespace std;c 2019-04-20 算法
最大连续子段和(3种情况) 非常经典的dp问题题目 如何理解 当前子序碰到 a[i]<0 加不加到子序中 如果将a[i]加入到sum中,sum仍然>0,那么加入是有意义的,否则没有意义,即是加入a[i] a[i]<0使得sum减小,但我们已经记录上一个sum作为最大的自序和,并且加入a[i]后,a[i+1]更大,成为新的最大子序和。 因为求最大子序的和,当 $sum[i-1]+a[i]< 2019-04-20 算法 子序和