c++笔记3

优先队列

普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。优先队列是一种按照优先级决定出队顺序的数据结构，优先队列中的每个元素被赋予级别，队首元素的优先级最高。

例如：4入队，1入队，3入队，此时队首元素不是4而是1，这是因为默认最小的元素优先级最高。此时如果选择出队，那么是1出队。

优先队列的实现方法有很多，最简单常见的是利用“堆”这个数据结构来实现。所以我们先从堆排序开始讲起。

堆排序

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

使用堆排序对一组数进行排序，主要分为2步：

建堆，复杂度O(n)，建堆的过程类似体育比赛中的淘汰赛，两个一组进行淘汰，选出优胜者。然后再对优胜者分组，两个一组进行淘汰...直到只剩下唯一的优胜者。整个过程需要比较 n/2+n/4+n/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\) 中的优先队列就是采用大根堆来实现的。

使用优先队列

//优先队列需要头文件  

#include<queue>  // 定义优先队列  

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\) 中的优先队列？以下为具体示例。

#include<cstdio>  

#include<queue>  

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,vector<int>,less<int> > p;  

priority_queue <int,vector<int>,greater<int> > q;

\(less\) 是从大到小， \(greater\) 是从小到大。

结构体优先队列

要想使用结构体的优先队列， 需要在结构体内部重载小于号。

struct node  {  

    int x, y;  

    bool operator < (const node & a) const      {  

        return x<a.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_queue<node,vector<node>, 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的和，我们可以理解为总的编码长度。

按照本图的分配方法，整棵树的权值为：(2+4)×5+7×4+(8+12+19)×3+(20+30)×2=275

这是一个最优的编码方式。构造哈夫曼树，需要配合一个优先队列来实现。

什么是单调队列

单调队列，即单调递减或单调递增的队列。单调队列与单调栈十分类似， 都是单增单减， 唯一的区别在于弹出元素时， 栈只能在栈顶将后进的元素弹出，而单调队列则可以在队列两端都进行元素的弹出， 在尾部实现元素的插入, 单调队列实际上是应用了双端队列的属性。

图中，企图插队的人战斗力为 6，队尾的5，1 都小于它，而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为奇数。假设a>=b，则 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)%p=b%pa%p	错误	(42)%3
(a+b)%p=(a%p)+(b%p)	错误	(5+5)%3
(a+b)%p=((a%p)+(b%p))%p	正确

快速幂

快速幂，顾名思义，就是可以比较快的求出x的y次幂。

通常我们要求x的y次幂复杂度是O(y)的，就是循环y次，每次乘x。但实际上我们可以将复杂度降低到O(log(y))的级别，用到的是二进制的性质以及幂指数的性质。

首先我们可以将y表示成2的幂次的和，形如y=2p1+2p2+2p3...的形式。

比如:22=16+4+2（ 22对应的二进制是10110)

那么x22=x16×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;

}

首先我们要理解x=x×x在做什么，x×x=x2,x2×x2=x4,...所以x 值的的变化就是x−>x2−>x4−>x8−>x16....。

刚才的例子中的y为22需要的就是 x22=x16×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大的元素。假设cnt1<k且cnt1+cnt2≥k，说明第k大的元素为x，直接返回答案即可。否则如果cnt1+cnt2<k，说明第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≤cnt1+cnt2 说明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)，就只要验证猜想。

不妨假设当k<n时，存在常数t满足T(k)≤tk那么：

T(n)≤O(n)+(t/n)∗(n−1+n−2+...+k+n−k+...+n−1)

于是有：

T(n)≤O(n)+(t/n)∗((n+k−1)(n−k)/2+(2n−k−1)k/2)

进而得到

T(n)≤O(n)+(t/2n)∗(n2−n−2k2+2nk)=O(n)+t/2∗(n−1−2k2/n+2k)

所以， T(n)=O(n)

nth-element

事实上，C++给我们提供了一个叫做nth_element的函数，可以在O(n)时间复杂度内求一个数组中第k小的数。

它的用法是：nth_element(a+l,a+l+k-1,a+r)

这样会使得a数组中区间[l,r)（注意是左闭右开区间）中第k小的元素处在第k个位置上，也即a[l+k−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 。那么有：

A=a1×10n/2+a0

B=b1×10n/2+b0

A×B=c2×10n+c1×10n/2+c0

其中：

c2=a1×b1c2=a1×b1

c1=a0×b1+b0×a1c1=a0×b1+b0×a1

c0=a0×b0c0=a0×b0

对于长度为n的两个数相乘，我们设其复杂度为T(n)。

我们是将其划分为四个长度为n/2的两个数进行递归乘法运算，之后进行三次加法进行求解。

因此T(n)=4∗T(n/2)+O(n)。

应用主定理求解T(n)，a=4,b=2,d=1，logba=2>d，因此T(n)=O(nlogb⁡a)=O(n2) 。

总的复杂度并无变化。

对于 c1=a0×b1+b0×a1，将其继续转化为c1=(a1+a0)∗(b1+b0)−(c2+c0) 。

在这个运算中，有4次加法，只有1次乘法。

通过转换，原来需要计算4次(n/2)2 的乘法，现在只需要计算3 次，其余依靠加减法来计算。

这便是Karatsuba乘法分治的核心思路。

#define sz(s) int(s.size())
#define super vector<int>
namespace integer {using super = vector<int>;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 vector<int64>super 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%p>aj%p不代表ai>aj。

散列函数

散列函数是这样一种特殊的函数。待处理的数据作为参数输入给散列函数，散列函数对数据进行特定的处理之后，将对应生成的新数据返回出来。一般来说，使用散列和散列函数，是为了将不便于存储、范围过大的数据”压缩成“便于存储和使用的数据，之前所说的对质数取模就源于这种思想。

我们可以构造这样一种散列函数对字符串进行压缩：

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|−1+s[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−l+1)%mod

不过，在实际计算时， (hash[r]−hash[l]∗seedr−l+1)%mod可能会被计算成负数，此时我们要对其加上mod，从而转化为[0,mod−1] 中的数。

上面公式中seed的取值通常为大于字符集的质数。

例如，对于字符串ababc，a,b,c对应的 ASCI码分别为 97,98,99。

它的前缀 a,ab,aba,abab,ababc就分别对应着：

hash[1],hash[2],hash[3],hash[4],hash[5]hash[0]=0，seed=137,mod=10007hash[1]=(hash[0]∗137+97)%mod=97hash[2]=(hash[1]∗137+98)%mod=3380hash[3]=(hash[2]∗137+97)%mod=2835hash[4]=(hash[3]∗137+98)%mod=8227hash[5]=(hash[4]∗137+99)%mod=6416

子串aba的hash值就等于：

(hash[3]−hash[0]∗seed3)%mod=2835

子串abc的hash值就等于：

(hash[5]−hash[2]∗seed3)%mod=2837

可以发现区间[1,2]和区间[3,4] 的字符串相同，其hash 值分别为：

(hash[2]−hash[0]∗seed2)%mod=3380,(hash[4]−hash[2]∗seed2)%mod=3380

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_set<int> S;

unordered_set<int> ::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

1. 赋值、查询等操作都与 mapmap 没有差别。
2. 不保证内部元素有序。操作的平均复杂度均为 O(1)O(1) 。

unordered_map<string, 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(nlog⁡n)或O(n2)。

不过，本节中我们将介绍两种特殊的排序算法，是不基于比较操作的排序算法，被称为非比较排序。他们的最好时间复杂度甚至可以低至O(n)。

非比较排序的基本思路是，直接按照数值将数字放在应该放的位置，保证位置靠前的对应的数值更小，这样就完成了从小到大的排序。

基数排序

算法描述

基数排序的基本思想是，先将待排序的所有数统一成相同的长度（位数不足的在前面补0）。

从最低位到最高位，按对应位的数字大小进行排序。在算法进行到第i位前，能够保证序列是按最低的i−1位上的数排好序的。这样当我们处理完每一位之后，所有数字就按其大小顺序排好序了。因为每一位上的数字只有0−>9，我们可以先把该位为0的数字放在前面，再接下来放该位为1的数字...... 这样就不用进行比较操作了。再进一步，如果所有数字都小于232。我们可以将它们看作是216（即65536）进制数。这些216进制数，最多只有两位数，且每一位上的数字小于216。因此我们只要进行两次排序操作，即先按低位排序，再按高位排序。每次排序时，按类似十进制的操作，先把对应位为0的数字放在前面，接下来放对应位为1的数字......最后放对应位为 65535 的数字。

这样总的操作次数仅为 max(n,217)。

算法实现

具体的算法流程如下：

1. 计算出序列中每个数在216进制下的低位和高位数字分别是多少。
2. 依次按低位和高位数字进行排序，排序时，依次放对应位为0,1,...,65535的数字。

3. #define N 200020
   #define pii pair<int,int>
   using namespace std;
   int n, a[N], tot;
   pii p[N];
   vector<pii>G[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) << " ";
   }