emerald's blog

Huffman编码 huffman树的路径来存字符，节点的权值来存字符串的数量 ，满足 $\Sigma_{i} ^{i=n} w_i * l_i$ ，则新字符串的总长度最小， 求最长字符串的最小值：在合并的过程中，合并一个就加入到队列中，如果val值相同，那么每次合并合并次数最少(即深度最小)的点，这样能使合并次数多的字符串（子树大的）往根节点靠拢（画图理解，子树往中间填，而不是往长的地

最优树可以记忆为：越是距离根节点近的点的权值越大，离根节点越远的点的权值越小， 节点i,权值 $w_i$ ,深度为 $l_i$ ,使得 $\Sigma_{i}^{i=n} w_i * l_i$ 最小，那么此数就是Huffman树 二叉Huffman树 通过最小堆来从树的叶子节点建树， 1.n个节点 $w_i$ push进入priority_queue(优先队列来模拟最小堆),

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++)

The XOR Largest Pair题目：在给定的N个整数中选出2个进行^运算，得到结果最大的是多少？ 思路 将N个正数按照二进制位（从高位到低位）存到字典树中，求^ 的最大值，意思是每一位都尽量走反方向的，本来该位为0，树中有1就走1，没有则继续走0，这样求得的结果一定是最接近^的最大值， 可以变插入变询问^的最大值，然后更新ans,因为两两相互查询，前面的插入的数没有和后面的数比，但

自闭 数组模拟trie1.trie存的是字符串，从s[0],开始存 二维数组，第一维记录节点的编号,第二维的索引代表字符，数组值存 节点编号（26个指针，指向下一个节点）1234567891011121314151617181920212223const int maxn=1e6;int tot = 0;//全局变量，记录所以节点的数量int endp[maxn];//每个节点编号都可能作为一个

题目思路：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],下一个最小状态从当前最小状态的下标进行移动,那么下一个最

单调队列滑动窗口 如果没有窗口的限制，而求[0,i]的最值，模拟单调栈（一头不变）解决，求最大值就维护一个单调递减的,输出栈的底部(模拟的栈),求最小值同理 当窗口限制的时候，我开始想的是队列存值 (用单调队列来维护窗口内的值)，如果仅仅存的是值，那么将无法知道队列中值是否在窗口内， 此时如果队列存的是 该值的下标那么将很好解决窗口的范围问题， 123456789101112131415161

题目思路： 题目给的是时间$t_i$ 意思是：距离过期的时间，只要 $[1,t_i]$ 之内被卖出就行了 将时间从小到大排序,维护一个小根堆， 堆为空，加入， 当不为空时，如果 $t_i$ > que.size() 意思是当前物品距离过期的时间大于已经卖出的个数，那么该物品一定可以卖出 如果 $t_i$ = que.size()，判断堆顶的卖出的最小利润是否小于该物品利润，小于就换成该

暴力 开一个priority_queue push pop ,,,,,,, 太慢了 1234567891011121314151617181920212223242526272829#include <iostream>#include <queue>#include <vector>using namespace std;const int maxn=100

题目思路：先找到最大值，分别从两边开始遍历，遍历时用head记录当前最高的，遇到height[i]< height[head]就算入面积中 1234567891011121314151617181920212223242526272829303132333435363738394041424344#include <iostream>using namespace std;con