大佬做的魔法少女网站,渭南网站建设服务,网站开发报价文件,网站300m是什么意思优先队列
普通的队列是一种先进先出的数据结构#xff0c;元素在队列尾追加#xff0c;而从队列头删除。优先队列是一种按照优先级决定出队顺序的数据结构#xff0c;优先队列中的每个元素被赋予级别#xff0c;队首元素的优先级最高。
例如#xff1a;4入队#xff0c…优先队列
普通的队列是一种先进先出的数据结构元素在队列尾追加而从队列头删除。优先队列是一种按照优先级决定出队顺序的数据结构优先队列中的每个元素被赋予级别队首元素的优先级最高。
例如4入队1入队3入队此时队首元素不是4而是1这是因为默认最小的元素优先级最高。此时如果选择出队那么是1出队。
优先队列的实现方法有很多最简单常见的是利用“堆”这个数据结构来实现。所以我们先从堆排序开始讲起。
堆排序
堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构并同时满足堆积的性质即子结点的键值或索引总是小于或者大于它的父节点。
使用堆排序对一组数进行排序主要分为2步
建堆复杂度O(n)建堆的过程类似体育比赛中的淘汰赛两个一组进行淘汰选出优胜者。然后再对优胜者分组两个一组进行淘汰...直到只剩下唯一的优胜者。整个过程需要比较 n/2n/4n/8...次所以复杂度为O(n)。
从堆顶逐个取出元素并对堆进行维护每次取值并维护的复杂度为O(log(n))因此堆排序的总复杂度为O(nlog(n))。 大根堆
能够用来做优先队列的数据结构有很多平衡树二项堆左偏树斐波那契堆......我们只介绍最简单的大根堆。
大根堆利用了与堆排序类似的方法。建堆后每次可以用 \(O(log(n))\) 的时间取出最大数。
堆的存储及建堆
直接使用数组来存储堆我们始终将 \(a_n\) 和 \(a_{n/2}\) 中较大的数放在 \(a_{n/2}\) 的位置上。
添加堆元素
直接将新的元素放在最后一个位置上\(a_n\)同时按照建堆时的方法比较\(a_n\)和\(a_{n/2}\) \(a_{n/2}\)和\(a_{n/4}\)... 这样可以在\(O(log(n))\)的复杂度维护好堆。
堆取最大
直接读取\(a_0\)复杂度\(O(1)\) 。
堆删除最大
删除最大值需要维护堆这个复杂度是\(O(log(n))\) 的。 取最大 添加 删除最大 数组 \(O(n)\) \(O(1)\) \(O(n)\) 链表 \(O(n)\) \(O(1)\) \(O(n)\) 排序好的数组 \(O(1)\) \(O(n)\) \(O(1)\) 大根堆 \(O(1)\) \(O(log(n))\) \(O(log(n))\)
stl的优先队列
虽然我们讲了很多大根堆的知识但实际并不需要我们手写一个大根堆\(C\) 的\(Stl\) 中直接提供了可以调用的优先队列 \(Stl\) 中的优先队列就是采用大根堆来实现的。
使用优先队列
//优先队列需要头文件
#includequeue // 定义优先队列
priority_queue结构类型 队列名;
priority_queue int q;
priority_queue double d; //优先队列的操作
q.size();//返回q里元素个数
q.empty();//返回q是否为空空则返回1否则返回0
q.push(k);//在q的末尾插入k
q.pop();//删掉q的第一个元素
q.top();//返回q的第一个元素
以上如何使用 \(stl\) 中的优先队列以下为具体示例。
#includecstdio
#includequeue
using namespace std;
priority_queue int q;
int main(){ q.push(10), q.push(8), q.push(12), q.push(14), q.push(6); while (!q.empty()) { cout q.top() ; q.pop(); }
}
程序大意就是在这个优先队列里依次插入 \(10、8、12、14、6\) 再输出。
输出的结果就是14 12 10 8 6
也就是说它是按从大到小排序的
less和greater优先队列
还是以 \(int\) 为例先来声明
priority_queue int,vectorint,lessint p;
priority_queue int,vectorint,greaterint q;
\(less\) 是从大到小 \(greater\) 是从小到大。 结构体优先队列
要想使用结构体的优先队列 需要在结构体内部重载小于号。
struct node { int x, y; bool operator (const node a) const { return xa.x; }
};
一个node结构体有两个成员x和y它的小于规则是x小者小。
它也是按照重载后的小于规则从大到小排序的。
priority_queue node q;
int main(){ k.x 10, k.y 100; q.push(k); k.x 12, k.y 60; q.push(k); k.x 14, k.y 40; q.push(k); k.x 6, k.y 80; q.push(k); k.x 8, k.y 20; q.push(k); while (!q.empty()) { node m q.top(); q.pop(); printf((%d,%d) , m.x, m.y); }
}
程序大意就是插入(10,100),(12,60),(14,40),(6,20),(8,20)(10,100),(12,60),(14,40),(6,20),(8,20) 这五个node
再来看看它的输出(14,40) (12,60) (10,100) (8,20) (6,80)
就是按照x从大到小排序的。
除了重载运算符之外还有一种方法可以自定义结构体如何比较大小这需要自己定义一个新的结构体专门用作比较。
struct node { int to, cost;
};//定义一个专门用作比较的结构体
struct cmp { bool operator() (node a, node b) { return a.cost b.cost; }
};
priority_queuenode,vectornode, cmp priq; 哈夫曼编码与哈夫曼树
哈夫曼编码
哈夫曼编码Huffman Coding又称霍夫曼编码是一种编码方式哈夫曼编码是可变字长编码VLC的一种。Huffman于1952年提出一种编码方法该方法完全依据字符出现概率来构造异字头的平均长度最短的码字有时称之为最佳编码一般就叫做 Huffman编码。
哈夫曼编码可以用来做无损的文件压缩我们常用的 zip,rar,7z等压缩算法都用到了哈夫曼编码而哈夫曼编码思想的本质是贪心算法。具体原理是这样的我们日常用到的所有文件存储在硬盘上的每一个字节8 bit都可以表示为0−255的一个数字。反过来保存这个数字需要一个字节的空间。但这些数字出现的频率是不一样的有的高有的低。于是我们想有没有方法让出现频率高的数字编码长度短一些让出现频率低的数字编码长度长一些这样占用的总空间就变小了。 编码 占用多少bit 10 2 11 2 000 3 001 3 010 3 0110 4 0111 4
哈夫曼编码保证所有编码的前缀都不相同这样就可以保证不同的原始数据一定编码成不同的哈夫曼码。反过来做解码的过程中能够明确知道每一个编码的结束位置方便快速解码。如果我们把编码中的 0,10,1 看作树的节点那么恰好对应一颗二叉树这就是哈夫曼树。
哈夫曼树
给定N个权值作为N个叶子结点构造一棵二叉树若该树的带权路径长度达到最小称这样的二叉树为最优二叉树也称为哈夫曼树 (Huffman Tree)。哈夫曼树是带权路径长度最短的树权值较大的结点离根较近。 以本图为例绿色的是最终的叶子节点节点上的数字是点的权值Wi我们可以理解为编码出现的次数。而叶子结点到根结点的距离 Li可以理解为编码的长度。而整个树的权值等于所有Wi×Li的和我们可以理解为总的编码长度。
按照本图的分配方法整棵树的权值为(24)×57×4(81219)×3(2030)×2275
这是一个最优的编码方式。构造哈夫曼树需要配合一个优先队列来实现。 什么是单调队列
单调队列即单调递减或单调递增的队列。单调队列与单调栈十分类似 都是单增单减 唯一的区别在于弹出元素时 栈只能在栈顶将后进的元素弹出而单调队列则可以在队列两端都进行元素的弹出 在尾部实现元素的插入, 单调队列实际上是应用了双端队列的属性。 图中企图插队的人战斗力为 6队尾的51 都小于它而6 和它战斗力相同它凭着插队的一股劲把这三个人全部挤掉到了7的后面。
这就是所谓的单调队列了队列元素保持单调递增减而保持的方式就是通过插队把队尾破坏了单调性的数全部挤掉从而使队列元素保持单调。
单调队列的出现可以简化问题队首元素便是最大小值这样选取最大小值的复杂度便为 O(1)由于队列的性质每个元素入队一次出队一次维护队列的复杂度均摊下来便是O(1) 。
单调队列VS单调栈
单调队列和单调栈的相同点
单调队列和单调栈的“头部”都是最先添加的元素“尾部”都是最后添加的元素。
递增和递减的判断依据是从栈底队尾到栈顶队首元素大小的变化情况。所以队列和栈是相反的。
它们的操作是非常相似的。当队列长度为无穷大时递增的单调队列和递减的单调栈排列是一样的
原因在于长度为无穷大的的队列不会在“头部”有popfront操作而在“尾部”的操作是一模一样的数据都从“尾部”进入并按照相同的规则进行比较。
两者维护的时间复杂度都是O(n)因为每个元素都只操作一次。
单调队列和单调栈的不同点
队列可以从队列头弹出元素可以方便地根据入队的时间顺序访问的顺序删除元素。单调队列和单调栈维护的区间不同。当访问到第 i个元素时单调栈维护的区间为[0,i) 而单调队列维护的区间为 (front,i)单调队列可以访问“头部”和“尾部”而单调栈只能访问栈顶也就是“尾部”。这导致单调栈无法获取 [0,i)的区间最大值/最小值。
二进制GCD
我们之前已经学习过如何利用辗转相除法求两个数的最大公约数。这里我们再讲一个利用二进制求解Gcd的方法。
二进制Gcd计算当中共有4种情况
a,b为偶数则Gcd(a,b)2×Gcd(a/2,b/2) 。
a为奇数b为偶数则Gcd(a,b)Gcd(a,b/2)。
a,b为奇数。假设ab则 Gcd(a,b)Gcd((a−b)/2,b)。
a为0则返回b。
ll gcd(ll a, ll b) { if (a 0) return b; if (b 0) return a; if (!(a 1) !(b 1)) return 2 * gcd(a 1, b 1); else if (!(a 1)) return gcd(a 1, b); else if (!(b 1)) return gcd(a, b 1); else return gcd(abs(a - b), min(a, b));
}
二进制Gcd只使用位移和加减法实现因此运行效率较高尤其在求高精大数的Gcd时效率提高明显这是因为大数除法的实现很复杂。
模运算与快速幂
模运算及性质
模运算多应用于程序编写中。%的含义为求余。模运算在数论和程序设计中都有着广泛的应用从奇偶数的判别到素数的判别从模幂运算到最大公约数的求法从孙子问题到凯撒密码问题无不充斥着模运算的身影。 性质 (a×b×c)%p((a×b)%p×c)%p 正确 可以避免大数运算 (a×b)%p(a%p)×(b%p) 错误 (5×5)%3 (a×b)%p((a%p)×(b%p))%p 正确 (a×b)%p(b×a)%p 正确 (ab)%pb%pa%p 错误 (42)%3 (ab)%p(a%p)(b%p) 错误 (55)%3 (ab)%p((a%p)(b%p))%p 正确
快速幂
快速幂顾名思义就是可以比较快的求出x的y次幂。
通常我们要求x的y次幂复杂度是O(y)的就是循环y次每次乘x。但实际上我们可以将复杂度降低到O(log(y))的级别用到的是二进制的性质以及幂指数的性质。
首先我们可以将y表示成2的幂次的和形如y2p12p22p3...的形式。
比如:221642 22对应的二进制是10110)
那么x22x16×x4×x2由于是二进制很自然地想到用位运算这个强大的工具和 。 运算通常用于二进制取位操作。一个数 1的结果就是取二进制的最末位。 运算比较单纯二进制去掉最后一位。
通过代码来详细讲解快速幂的思想
int fastPow(int x, int y) { int ans 1; while (y ! 0) { if (y 1) ans ans * x; x x * x; y 1; } return ans;
}
首先我们要理解xx×x在做什么x×xx2,x2×x2x4,...所以x 值的的变化就是x−x2−x4−x8−x16....。
刚才的例子中的y为22需要的就是 x22x16×x4×x2 。
所以每次判断y最低位是否为1如果为1则将答案乘上当前的x。每次y都右移一位。直到y为0。
通常情况下xy的答案都很大远远超过long long的数据范围需要对答案mod一个较大的质数。因此我们讨论快速幂主要是讨论xy%p的结果。在和*运算中 mod符号的位置不影响最终答案所以可以在快速幂的运算过程中直接对ans和x直接做mod处理。
**注意**快速幂求模运算并不要求模数为质数任意数都可以套用这个方法。
递推和递归的区别
在学习动态规划之前 我们先复习一下之前学过的递推和递归。
从程序上看递归表现为自己调用自己它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算大大地减少了程序的代码量。
递归是从问题的最终目标出发逐渐将复杂问题化为简单问题最终求得问题。递推则是由已知答案推出要求的问题。
如何分析递推式
递推的思想有些类似数学中常用的数学归纳法我们假设知道1−(n−1)的所有的答案看如何推导出n的答案。
搜索中的记忆化
记忆化搜索
我们在之前的课程中曾经提到过记忆化搜索记忆化搜索就是在搜索时记录一些有用的答案 我们递归的本质就是在搜索答案但是有些问题会被重复的搜索所以我们就可以用空间换时间的思想 将被搜索的问题的答案记录下来 当下一次再被搜索到这个问题的时候 就可以在O(1) 的时间给出答案。
int ans[1005];
int F(int n) { if (n 1 || n 2) return 1; if (ans[n] 0) ans[n] F(n - 1) F(n - 2); return ans[n];
}
记忆化搜索实际上就是在搜索过程中不做重复的计算遇到相同的搜索分支直接调用上次的计算结果。记忆化搜索是实现动态规划强有力的方法之一另外一种实现动态规划的方法就是递推在后面的章节中会详细讲解。
记忆化搜索的适用范围
根据记忆化搜索的思想它是解决重复计算而不是重复生成也就是说这些搜索必须是在搜索扩展路径的过程中分步计算的题目也就是“搜索答案与路径相关”的题目而不能是搜索一个路径之后才能进行计算的题目必须要分步计算。
动态规划的状态与转移
动态规划与贪心
多阶段逐步解决问题的策略就是按一定顺序或一定的策略逐步解决问题的方法。分解的算法策略也是多阶段逐步解决问题策略的一种表现形式主要是通过对问题逐步分解然后又逐步合并解决问题的。贪心算法每一步都根据策略得到一个结果并传递到下一步自顶向下一步一步地做出贪心决策。
动态规划算法的每一步决策给出的不是唯一结果而是一组中间结果而且这些结果在以后各步可能得到多次引用只是每走一步使问题的规模逐步缩小最终得到问题的一个结果。
贪心算法
贪心选择性质在求解一个问题的过程中如果再每一个阶段的选择都是当前状态下的最优选择即局部最优选择并且最终能够求得问题的整体最优解那么说明这个问题可以通过贪心选择来求解这时就说明此问题具有贪心选择性质。
最优子结构性质当一个问题的最优解包含了这个问题的子问题的最优解时就说明该问题具有最优子结构。
动态规划
最优化原理如果问题的最优解所包含的子问题的解也是最优的就称该问题具有最优子结构即满足最优化原理。
无后效性即某阶段状态一旦确定就不受这个状态以后决策的影响。也就是说某状态以后的过程不会影响以前的状态只与当前状态有关。
有重迭子问题即子问题之间是不独立的一个子问题在下一阶段决策中可能被多次使用到。
优势采用动态规划方法可以高效地解决许多用贪心算法或分治算法无法解决的问题。但贪心算法也有它的优势构造贪心策略不是很困难而且贪心策略一旦经过证明成立后它就是一种高效的算法。
分治与减治
分治法是很多高效算法的基础如排序算法快速排序归并排序快速傅立叶变换等等。
结合一些经典的分治问题来深入理解分治的思想并利用主定理分析这些问题的算法复杂度。
对一个分治算法进行复杂度分析时首先设T(n)表示对规模为n的数据进行分治的复杂度再列出T(n)有关的递推关系式之后判断是否适用主定理如果适用则应用主定理的对应情形进行求解。
算法描述
对于一个长度为n的序列要找出其中第k大的元素我们可以首先在序列中任意取出一个数x将比x小的数作为一个新序列记作序列1。
将比x大的数作为另一个新序列记作序列2。
假设比x大的数的个数为cnt1c与x相等的数的个数为cnt2假设cnt1≥k说明第k大的元素在序列1中我们递归的在序列1中找第k大的元素。假设cnt1k且cnt1cnt2≥k说明第k大的元素为x直接返回答案即可。否则如果cnt1cnt2k说明第k大的元素在序列2中递归在序列2中找即可不过在原序列中第k大的元素在序列2中则为第k−cnt1−cnt2大的元素因此我们应该在序列2中递归去找第k−cnt1−cnt2的元素。
算法流程梳理如下 在序列中随机取出一个数x将比x小的数划分为序列1比x大的数划分为序列2假设比x大的数个数为cnt1与x相等的数的个数为cnt2如果k≤cnt1在序列1中递归找第k大的元素否则如果k≤cnt1cnt2 说明x就是第k大的元素直接返回答案否则在序列2中递归找第k−cnt1−cnt2 大的元素。
solve(l, r, k){//表示对数组a中区间[l,r]的数找第k大 x a[l rand() % (r - l 1)]; L l, R r; for (i l; i r; i) if (a[i] x) tmp[L] a[i]; else if (a[i] x)
tmp[R--] a[i]; cnt1 r - R, cnt2 R - L 1 if (cnt1 k) return solve(R 1, r, k); else if (cnt1 cnt2 k) return x; else return solve(l, L - 1, k - cnt1 - cnt2);
}
算法实现
#define N 200020
using namespace std;
int n, k, a[N];
int tmp[N];
int solve(int l, int r, int k)//表示对数组a中区间[l,r]的数找第k大
{ int x a[l rand() % (r - l 1)]; int L l, R r; for (int i l; i r; i) if (a[i] x) tmp[L] a[i]; else if (a[i] x) tmp[R--] a[i]; int cnt1 r - R, cnt2 R - L 1; if (cnt1 k) return solve(R 1, r, k); else if (cnt1 cnt2 k) return x; else return solve(l, L - 1, k - cnt1 - cnt2);
int main(){ srand(time(0)); cin n k; for (int i 1; i n; i) cin a[i]; solve(1, n, k);
}
复杂度分析
首先用和快速排序一样的想法估计算法复杂度。
由于我们每次是随机从当前区间取出一个数那么平均意义下小于它和大于它的数的个数近乎相等递归求解时无论递归哪边下次处理的数据规模减半。因此设求解长为n的序列的第k大时间复杂度为T(n)。
那么T(n)T(n/2)O(n)。不难得到T(n)O(n)T(n)O(n)。但事实上更严谨的来讲
T(n)O(n)(T(n−1)T(n−2)...T(k)T(n−k)...T(n−1))/nT(n)O(n)(T(n−1)T(n−2)...T(k)T(n−k)...T(n−1))/n
我们上面已经估计了T(n)O(n)就只要验证猜想。
不妨假设当kn时存在常数t满足T(k)≤tk那么
T(n)≤O(n)(t/n)∗(n−1n−2...kn−k...n−1)
于是有
T(n)≤O(n)(t/n)∗((nk−1)(n−k)/2(2n−k−1)k/2)
进而得到
T(n)≤O(n)(t/2n)∗(n2−n−2k22nk)O(n)t/2∗(n−1−2k2/n2k)
所以 T(n)O(n)
nth-element
事实上C给我们提供了一个叫做nth_element的函数可以在O(n)时间复杂度内求一个数组中第k小的数。
它的用法是nth_element(al,alk-1,ar)
这样会使得a数组中区间[l,r)注意是左闭右开区间中第k小的元素处在第k个位置上也即a[lk−1]。
int main( ) { static int a[15] {0, 1, 2, 5, 7, 3, 4, 1};
nth_element(a 1, a 4, a 8); for (int i 1; i 8; i) { printf(%d , a[i]); printf(\n); } return 0;} karatsuba乘法
Karatsuba乘法是一种快速乘法。此算法在1960 年由Anatolii Alexeevitch Karatsuba提出并于1962年得以发表。 此算法主要用于两个大数相乘。普通乘法的复杂度是O(n2)而Karatsuba算法的复杂度仅为O(nlog3)约为 O(n1.585) log3是以2 为底。Karatsuba算法应用了分治的思想。
算法描述
假设我们有A,B两个大数都为n位要计算A∗B需要将A,B划分成两等份如下图所示 将A分成a1和a0两等份将B分成b1和b0两等份长度都为n/2 。那么有
Aa1×10n/2a0
Bb1×10n/2b0
A×Bc2×10nc1×10n/2c0
其中
c2a1×b1c2a1×b1
c1a0×b1b0×a1c1a0×b1b0×a1
c0a0×b0c0a0×b0
对于长度为n的两个数相乘我们设其复杂度为T(n)。
我们是将其划分为四个长度为n/2的两个数进行递归乘法运算之后进行三次加法进行求解。
因此T(n)4∗T(n/2)O(n)。
应用主定理求解T(n)a4,b2,d1logba2d因此T(n)O(nlogba)O(n2) 。
总的复杂度并无变化。
对于 c1a0×b1b0×a1将其继续转化为c1(a1a0)∗(b1b0)−(c2c0) 。
在这个运算中有4次加法只有1次乘法。
通过转换原来需要计算4次(n/2)2 的乘法现在只需要计算3 次其余依靠加减法来计算。
这便是Karatsuba乘法分治的核心思路。
#define sz(s) int(s.size())
#define super vectorint
namespace integer {using super vectorint;const int base_digits 9;const int base 1000000000;super trim(super a) {while (!a.empty() a.back() 0) a.pop_back();return a;}int compare(const super lhs, const super rhs) {int cmp sz(lhs) - sz(rhs), i sz(lhs) - 1;if (cmp ! 0) return cmp 0 ? -1 : 1;while (i ! -1 lhs[i] rhs[i]) i--;return i -1 ? 0 : lhs[i] rhs[i] ? -1 : 1;}inline void norm(int a, int k) {k (a 0 ? (a base, -1) : a base ? 0 : (a - base, 1)); }super add(const super lhs, const super rhs) {super res(sz(rhs) sz(lhs) ? lhs : rhs);super bit(sz(rhs) sz(lhs) ? rhs : lhs);res.push_back(0);int i 0, k 0;for (; i sz(bit); i) norm(res[i] k bit[i], k);for (; i sz(res) 0 k; i) norm(res[i] k, k);return trim(res); }super sub(super res, const super bit) {int i 0, k 0;for (; i sz(bit); i) norm(res[i] k - bit[i], k);for (; i sz(res) k 0; i) norm(res[i] k, k);return trim(res);}string to_string(super a) {string res ;if (a.empty()) return 0;static char s[10];sprintf(s, %d, a.back());res.append(s);for (int i sz(a) - 2; ~i; i--) {sprintf(s, %09d, a[i]);res.append(s);}return res;}super to_super(string s) {super res;for (int i sz(s), x; 0 i; i - base_digits) {const char* p s.c_str() max(0, i - base_digits);if (i ! sz(s)) s[i] \0;sscanf(p, %09d, x);res.push_back(x);}return trim(res);}#define int64 long long#define vll vectorint64super convert_base(const super a, int old_digits, int new_digits) {vll p(max(old_digits, new_digits) 1);for (int i p[0] 1; i sz(p); i)p[i] p[i - 1] * 10;super res;int64 cur 0;for (int i 0, cur_digits 0; i sz(a); i) {cur a[i] * p[cur_digits];cur_digits old_digits;while (new_digits cur_digits) {res.push_back(cur % p[new_digits]);cur_digits - new_digits;cur / p[new_digits]} }res.push_back(cur);return trim(res);}vll karatsuba(const vll a, const vll b) {int n sz(a);vll res(n n);if (n 32) {for (int i 0; i n; i)for (int j 0; j n; j)res[i j] a[i] * b[j];return res; }int k n 1;vll a1(a.begin(), a.begin() k);vll a2(a.begin() k, a.end());vll b1(b.begin(), b.begin() k);vll b2(b.begin() k, b.end());vll a1b1 karatsuba(a1, b1);vll a2b2 karatsuba(a2, b2);for (int i 0; i k; i) a2[i] a1[i];for (int i 0; i k; i) b2[i] b1[i];vll r karatsuba(a2, b2);for (int i 0; i sz(a1b1); i) r[i] - a1b1[i];for (int i 0; i sz(a2b2); i) r[i] - a2b2[i];for (int i 0; i sz(r); i) res[i k] r[i];for (int i 0; i sz(a1b1); i) res[i] a1b1[i];for (int i 0; i sz(a2b2); i) res[i n] a2b2[i];return res; }super mul(const super lhs, const super rhs) {const int new_digits 6;const int base 1000000;super a6(convert_base(lhs, base_digits, new_digits));super b6(convert_base(rhs, base_digits, new_digits));vll a(a6.begin(), a6.end());vll b(b6.begin(), b6.end());while (sz(a) sz(b)) a.push_back(0);while (sz(b) sz(a)) b.push_back(0);if (sz(a) 0) return super();while (sz(a) (sz(a) - 1))a.push_back(0), b.push_back(0);vll c(karatsuba(a, b));super res;int64 k 0;for (int i 0; i sz(c); i) {int64 p c[i] k;res.push_back(p % base);k p / base;}res convert_base(res, new_digits, base_digits);return trim(res); }}
using namespace integer;
istream operator (istream in, super p) {string s; in s;p to_super(s);return in;}
ostream operator (ostream out, super p) {return out to_string(p);}
int main() {ios::sync_with_stdio(false);super a, b;cin a b;cout mul(a, b) endl;return 0;} Hash散列
Hash一般翻译做散列或音译为哈希是把任意长度的输入通过散列算法变换成固定长度的输出该输出就是散列值。这种转换是一种压缩映射也就是散列值的空间通远小于输入的空间。例如我们可以将一个文件的特征提取出来通过某种方法的计算得到一个long long 的值这就是文件的 Has 值。对于两个不同的文件如果Hash值相同则可能这两个文件是一样的不一定如果两个文件的 Hash值不同则肯定是不一样的。因此 Hash本身允许我们建立一种 Key和 Value的结构Hash值是Key 具体的文件内容是 Value。如果 Hash值计算的足够巧并且数值范围足够大那么如果两个文件的Hash 值相同这两个文件相同的概率可能高达99.9999999999999%。在网络时代两个不同的人比较他们的文件是否相同无需将整个文件传给对方只需二人分别计算一个足够大的Hash,比如21024然后比较两个文件的Hash 值就好了。
数值Hash
根据之前所学我们可以用一个map来保存这些数字如果有相等的可以直接判断。map提供了一种红黑树结构可以让所有数字维持有序时间复杂度为O(nlog(n))。
我们还可以直接对这些数字排序然后遍历判断前后两个数字是否相等时间复杂度为O(nlog(n))。
曾经使用数组来记录一个数字是否存在但对于long long我们做不到把ai当做数组下标访问考虑用一个方法把这些数变得更小简单来说我们找一个大于n的质数p然后用ai%p当做ai的 Hash值然后我们就可以用一个大小为p的vector 数组记录 所有ai。这相当于将 %p相等的数分到同一个组里vector按照这种方法平均一个组中只有1,2个数我们只需要在组内比较是否有相同的数字即可。这个的平均复杂度为O(n)。
这里需要注意一点Hash只能判断是否相等不能记录大小关系因为 ai%paj%p不代表aiaj。
散列函数
散列函数是这样一种特殊的函数。待处理的数据作为参数输入给散列函数散列函数对数据进行特定的处理之后将对应生成的新数据返回出来。一般来说使用散列和散列函数是为了将不便于存储、范围过大的数据”压缩成“便于存储和使用的数据之前所说的对质数取模就源于这种思想。
我们可以构造这样一种散列函数对字符串进行压缩
f(s)s[1]s[2]s[3]...s[|s|]f(s)s[1]s[2]s[3]...s[|s|]
其中 s[i]表示字符串第i位的字符的ASCII 码。
可以很明显的看出来散列函数往往有着共通的缺陷即两个不同的原数据可能会对应着相同的散列函数值。这时我们称散列函数发生了冲突。
在算法竞赛中我们通常使用哈希即散列对字符串进行压缩将字符串压缩成数字从而方便、快速的比较两个字符串。
通常情况下我们对字符串进行压缩时会使用下面这种散列函数
hash(s)(s[1]×seed|s|−1s[2]×seed|s|−2...s[|s|]×seed0)%mod
其中 seed,mod分别为我们自行确定的两个常数一般情况下mod要求是一个较大的质数。
这样我们就把一个字符串转化为了[0,mod]中的一个整数。
在比较两个字符串是否相等时我们就不必依次比较其对应位置的字符是否相等而是直接比较两个字符串的散列函数值是否相等。
那么如何方便快捷的计算一个字符串s的子串s[l,r的散列函数值呢
我们仔细观察给出的散列函数的计算方式会发现实际上我们就是把字符串s当作了一个seed进制数每一位的字符对应的ASCII码就是这个seed进制数在这一位上的数字。
所以要快速的取出子串的散列函数值我们可以先计算出s的每个前缀的散列函数值。
即算
hash[i]hash(pre(s,i))(s[1]×(seedi−1)s[2]×(seedi−2)...s[i]×(seed0))%mod
对于子串s[l,r]其散列函数值等于
(hash[r]−hash[l]∗seedr−l1)%mod
不过在实际计算时 (hash[r]−hash[l]∗seedr−l1)%mod可能会被计算成负数此时我们要对其加上mod从而转化为[0,mod−1] 中的数。
上面公式中seed的取值通常为大于字符集的质数。
例如对于字符串ababca,b,c对应的 ASCI码分别为 97,98,99。
它的前缀 a,ab,aba,abab,ababc就分别对应着
hash[1],hash[2],hash[3],hash[4],hash[5]hash[0]0seed137,mod10007hash[1](hash[0]∗13797)%mod97hash[2](hash[1]∗13798)%mod3380hash[3](hash[2]∗13797)%mod2835hash[4](hash[3]∗13798)%mod8227hash[5](hash[4]∗13799)%mod6416
子串aba的hash值就等于
(hash[3]−hash[0]∗seed3)%mod2835
子串abc的hash值就等于
(hash[5]−hash[2]∗seed3)%mod2837
可以发现区间[1,2]和区间[3,4] 的字符串相同其hash 值分别为
(hash[2]−hash[0]∗seed2)%mod3380,(hash[4]−hash[2]∗seed2)%mod3380
hash值相同。
最小表示
我们有时会遇到这样一类问题比如判断环形的数组是否相等例如一串珠子围成一个环珠子编号分别为 3,4,5,1,2 。
这串珠子是可以任意旋转的如果以4为第一个我们看到的珠子编号就是4,5,1,2,3如果以 11 作为第一个那么编号为1,2,3,4,5。
给出一堆珠子的编号让我们判断其中是否有一对珠子可以通过旋转让编号完全相等的。
对于珠串 (1,2,3,4,5),(3,4,5,1,2)在数学上称为同构。对于这类同构的问题我们可以用最小表示法来判断两个珠串是否相同。
所谓最小表示法套用之前的 Hash 散列函数我们把 (1,2,3,4,5) 通过旋转得到的5个串的 Hash值都算出来但只用其中最小的那个值作为这个珠串的Hash 值。
(1,2,3,4,5),(2,3,4,5,1),(3,4,5,1,2),(4,5,1,2,3),(5,1,2,3,4)
利用我们上面提供的散列函数如果已经计算出1,2,3,4,5)的Hash值那么可以O(1)计算(2,3,4,5,1)的Hash值。即
Hash(2,3,4,5,1)((Hash(1,2,3,4,5)−1×seed5)×seed′1′)%mod
计算所有n个Hash值所需的时间为O(n)。
链式Hash
之前提到散列Hash有一个明显的缺陷即两个不同的数据散列Hash之后得到的散列值hash值相同。那么当我们要进行比较和查询时如果只是利用其hash值进行比较和查询就会发生错误。
事实上我们可以通过链表来解决这种冲突。
对于每一个hash值x我们用一个链表桶来存储hash值为x的数据。
这样就可以避免之前提到的错误出现。
例如当我们想要查询我们是否存储过一个数据时可以先求出它的hash值即散列函数值然后在其hash值对应的链表桶中查找是否存在这个数据即可。例如发现与当前hash 值相同的还有 55 个数据此时再将其与这5个数据本身的值逐个进行比较看是否相同如果都不相同则将当前数据直接加到末尾这样相同的hash值就有6个了。不过我们没必要自己实现这样的操作。在 C中unordered_set和unordered_map就是用链式hash的原理实现的。他们可以实现在 O(1)O(1) 的时间复杂度内进行查询、插入等操作不过相对于一般的set和map他们的缺陷在于内部元素并非有序的。
Stl中的Hash
在C中有几种特别的STL工具是使用hash表实现的。unordered_set与unordered_map就是这样两种STL工具。
unordered_set
插入、删除、查询等函数都和 set没有差别。
和setset一样保证内部元素没有重复。
不保证内部元素有序。
操作的平均复杂度为 O(1)O(1) 。
unordered_setint S;
unordered_setint ::iterator it;
int main(){ S.insert(10);
S.insert(5); S.insert(7); S.insert(9); S.insert(5); S.insert(10); S.erase(5); for (it S.begin(); it ! S.end(); it) { printf(%d , *it); }
}
unordered_map
赋值、查询等操作都与 mapmap 没有差别。不保证内部元素有序。操作的平均复杂度均为 O(1)O(1) 。
unordered_mapstring, int f;
int main(){ f[apple] 666; cout f[apple] endl; f[catch] 919; cout f[catch] endl; f.clear(); cout f[apple] f[catch] endl;
}
非比较排序
在之前介绍过的快速排序和归并排序都是以比较为基础操作的排序算法。这类算法的理论最优复杂度往往为O(nlogn)O(nlogn)或O(n2)。
不过本节中我们将介绍两种特殊的排序算法是不基于比较操作的排序算法被称为非比较排序。他们的最好时间复杂度甚至可以低至O(n)。
非比较排序的基本思路是直接按照数值将数字放在应该放的位置保证位置靠前的对应的数值更小这样就完成了从小到大的排序。
基数排序
算法描述
基数排序的基本思想是先将待排序的所有数统一成相同的长度位数不足的在前面补0。
从最低位到最高位按对应位的数字大小进行排序。在算法进行到第i位前能够保证序列是按最低的i−1位上的数排好序的。这样当我们处理完每一位之后所有数字就按其大小顺序排好序了。因为每一位上的数字只有0−9我们可以先把该位为0的数字放在前面再接下来放该位为1的数字...... 这样就不用进行比较操作了。再进一步如果所有数字都小于232。我们可以将它们看作是216即65536进制数。这些216进制数最多只有两位数且每一位上的数字小于216。因此我们只要进行两次排序操作即先按低位排序再按高位排序。每次排序时按类似十进制的操作先把对应位为0的数字放在前面接下来放对应位为1的数字......最后放对应位为 65535 的数字。
这样总的操作次数仅为 max(n,217)。
算法实现
具体的算法流程如下
计算出序列中每个数在216进制下的低位和高位数字分别是多少。依次按低位和高位数字进行排序排序时依次放对应位为0,1,...,65535的数字。 #define N 200020
#define pii pairint,int
using namespace std;
int n, a[N], tot;
pii p[N];
vectorpiiG[N];
int main()
{cin n;for (int i 1; i n; i) {cin a[i];p[i].first a[i] 16, p[i].second a[i] % 65536;}for (int i 1; i n; i)G[p[i].second].push_back(p[i]);for (int i 0; i 65536; i)for (int j 0; j G[i].size(); j)p[tot] G[i][j];for (int i 0; i 65536; i)G[i].clear();for (int i 1; i n; i)G[p[i].first].push_back(p[i]);tot 0; for (int i 0; i 65536; i)for (int j 0; j G[i].size(); j)p[tot] G[i][j];for (int i 1; i n; i)cout ((p[i].first 16) | p[i].second) ;
}
