对数据的常见操作

前缀和

前缀和，是一个序列的前n项和，可以理解为高中的数列的前n项和。如果给你一个数组，要求你求出这个数组中某段区间的和，我们可以用遍历区间的方式来求和，下面是求得区间和的朴素算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
using namespace std;

const int N = 1e5+10;
int main()
{
    int a[N];
    for(int i = 1;i<=n;i++) cin>>a[i];
    //记录和
    int ans;
    
    //输入两个区间
    int l,r;
    cin>>l>>r;
    //累加
    for(int i = l;i<=r;i++) ans+=a[i];
    cout<<ans;
}

但是这样做，如果求多个区间和就要多次遍历，这样时间复杂度会很高，索性我们在输入数据的同时，构造前缀和数组S[]使得每一个S[]数组的下标表示一段从1开始的连续的区间和(也可以从数组下标0开始)，下面是代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<iostream>
using namespace std;

const int N = 1e5+10;
int main()
{
    int a[N],S[N];
    
    //构造前缀和数组
    for(int i = 1;i<=n;i++){
        cin>>a[i];
        s[i] += s[i-1]+a[i];
    }    
    
}

当需要求得一个区间的和的时候，可以利用前缀和的思想，例如给一个数组a[5] = {1,2,3,4,5}，要求区间2-3的和。由S[]数组的性质我们可以得到，S[3]-S[1] = a[2]+a[3](展开就知道了)，所以说对于任意的区间[l,r]，有区间和 = S[r] - S[l-1]。

下面是根据推断得到的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int a[N], s[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    //构造前缀和
    for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i]; 

    while (m -- )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", s[r] - s[l - 1]); // 区间和的计算
    }

    return 0;
}

二维前缀和

对于二维前缀和，可以理解为求取坐标范围内值的和。这里只是预处理，方便我们接下来自由计算两个区间内的前缀和：(x1,y1) - (x2,y2)。

这里可以理解为倒着的x,y轴，简单来说需要计算二维数组的范围值。枚举到i,j坐标的时候，对其左，上方向接触到墙数组范围进行求和，然后记录到s数组制定的i,j数组位置。

在简单的构造了S二维前缀和，我们来讨论计算二维数组的随意区间和。

我们用图形来理解，需要求得红色区间值的和应该怎么做。直接用最大的蓝色矩阵减去绿色和紫色小条就行。减去完发现多减了一个a[i][j],加上即可，如下图所示。

外围蓝色矩形面积s[i][j] = 绿色面积 s[i - 1][j] + 紫色面积 s[i][j - 1] - 重复加的红色的面积 s[i - 1][j - 1] + 小方块的面积 a[i][j]。

因此得出公式

s[i][j] = s[i - 1][j] + s[i][j - 1 ] + a[i][j] - s[i - 1][j - 1]

接下来回归问题去求以(x1,y1)为左上角和以(x2,y2)为右下角的矩阵的元素的和。

紫色面积是指 (1, 1)左上角到(x1 - 1, y2)右下角的矩形面积 ，黄色面积是指(1, 1)左上角到(x2, y1 - 1)右下角的矩形面积。

不难推出：

绿色矩形的面积 = 整个外围面积s[x2, y2] - 黄色面积s[x2, y1 - 1] - 紫色面积s[x1 - 1, y2] + 重复减去的红色面积 s[x1 - 1, y1 - 1]

以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为

s[x2, y2] - s[x1 - 1, y2] - s[x2, y1 - 1] + s[x1 - 1, y1 - 1]

然后我找到了一个图可以很好的描述这类问题：原链接在这里

一维差分

首先给定一个原数组a：a[1], a[2], a[3],,,,,, a[n];

然后我们构造一个数组b ： b[1], b[2], b[3],,,,,, b[i];

使得 a[i] = b[1] + b[2] + b[3] + ,,,,,, + b[i]

也就是说，a数组是b数组的前缀和数组，反过来我们把b数组叫做a数组的差分数组。换句话说，每一个a[i]都是b数组中从头开始的一段区间和。构造差分b数组最为直接的方法如下：

由于a数组对应索引是，b数组从1开始到索引的前缀和。那么我们只要改变对应的b[l](l是左索引)，就可以对后面产生连锁反应。
举个例子，b数组是1 2 3 4 5 6 7只需要将1这个数据+3那么包含1+3的前缀和都会+3.同理，如果在4这里-3那么之后包含4-3的前缀和都会-3,所以说包含1和4的前缀和不会发生变化。

b[l] + c，效果使得a数组中a[l]及以后的数都加上了c，但只要求l到r 区间加上 c, 因此还需要执行 b[r + 1] - c,让a数组中a[r + 1]及往后的区间再减去c(绿色部分)，这样对于a[r]以后区间的数相当于没有发生改变。

因此我们得出一维差分结论：给a数组中的[l, r] 区间中的每一个数都加上c,只需对差分数组b做 b[l] + = c, b[r+1] - = c。时间复杂度为O(1), 大大提高了效率。

这里需要注意的是，我们开始拿了a[]数组来构造b数组。所以说我们执行完insert函数，要用b数组来构造回我们的a数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//模版代码
#include<iostream>
using namespace std;
const int N = 1e5+10;
int a[N],b[N],c[N];
int n,m;
//构造差分数组的函数
void insert(int l,int r,int c)
{
    b[l]+=c;
    b[r+1]-=c;
}

int main()
{
    cin>>n>>m;
    //输入构造差分数组的原数组
    for(int i = 1;i<=n;i++) cin>>a[i];
    //构造差分序列 - b就是差分数组
    for(int i = 1;i<=n;i++) insert(i,i,a[i]);
    
    while(m--)
    {
        int l,r,c;
        cin>>l>>r>>c;
        //插入更改的值
        insert(l,r,c);
    }
    //这里是析出原数组
    for(int i = 1;i<=n;i++) c[i] = c[i-1]+b[i];
    //输出
    for(int i = 1;i<=n;i++) cout<<c[i]<<" ";   
    
}

二维差分

结合一维差分的用途，可以容易的想到，二维差分主要是用于快速将一个区块中的所有元素都加上 d。在这里可以把二维数组当做，y个x的一维数组。
对于一维差分，两个操作

  • 在指定区间开始时加上对应的c
  • 在指定区间结束+1减去对应的c

假定我们已经构造好了b数组，类比一维差分，我们执行以下操作来使被选中的子矩阵中的每个元素的值加上c

b[x1][y1] + = c ;

b[x1][y2+1] - = c;

b[x2+1][y1] - = c;

b[x2+1][y2+1] + = c;

其实就和一维差分一样，我们在当前的块+c,那么只要包含的这个块的前缀和都会+c.最终需要的结果是a这个数组，也就是我们的前缀和数组嘛。

对于上述的操作我是这样理解的：

b[x1][y1] += c; 对应图1 ,让整个a数组中蓝色矩形面积的元素都加上了c。
b[x1][y2 + 1] -= c; 对应图2 ,让整个a数组中绿色矩形面积的元素再减去c，使其内元素不发生改变。
b[x2 + 1][y1] -= c; 对应图3 ,让整个a数组中紫色矩形面积的元素再减去c，使其内元素不发生改变。
b[x2 + 1][y2 + 1] += c; 对应图4,让整个a数组中红色矩形面积的元素再加上c，红色内的相当于被减了两次，再加上一次c，才能使其恢复。

这四个步骤，本质上是让包含我们处理过的b数组区域的前缀和+c或者-c

我们将上述操作封装成一个插入函数:

1
2
3
4
5
6
7
8
void insert(int x1,int y1,int x2,int y2,int c)
{     
    //对b数组执行插入操作，等价于对a数组中的(x1,y1)到(x2,y2)之间的元素都加上了c
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

但是二维差分不像一维数组的差分构造。不可能像一维作差得出我们的二维差分数组，这里太难记了。这里介绍一种比较巧妙的方法：将差分矩阵中每个元素一个一个的插进去。

我们可以先假想a数组为空，那么b数组一开始也为空，因此每次让以(i,j)为左上角到以(i,j)为右下角面积内元素(其实就是一个小方格的面积)去插入 c = a[i][j]，等价于原数组a中(i,j) 到(i,j)范围内 加上了 a[i][j],因此执行n*m次插入操作，就成功构建了差分b数组.

1
2
3
4
5
6
7
for(int i = 1;i <= n;i++)
 {
     for(int j = 1;j <= m;j++)
     {
         insert(i, j, i, j, a[i][j]);    //构建差分数组
     }
 }

构造处理过后的b数组公式(最终的结果)：

1
b[i][j] = a[i][j] − a[i − 1][j] − a[i][j − 1] + a[i −1 ][j − 1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1e3 + 10;
int a[N][N], b[N][N];
//在区间内插入我们的值 - 可以看前面的图
void insert(int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}
int main()
{
    int n, m, q;
    cin >> n >> m >> q;
    //输入原数组
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    //插入构造b差分数组
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            insert(i, j, i, j, a[i][j]);      //构建差分数组
        }
    }
    //输入我们要插入值的范围
    while (q--)
    {
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        insert(x1, y1, x2, y2, c);
    }
    //前缀和构造回来。  先原数组构造差分 - 插入目标值 - 构造回来原数组
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            //二维前缀和
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];  
        }
    }
    //打印
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            printf("%d ", b[i][j]);
        }
        printf("\n");
    }
    return 0;
}

双指针

双指针，指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。换言之，双指针法充分使用了数组有序这一特征，从而在某些情况下能够简化一些运算。

对撞指针

对撞指针是指在数组中，将指向最左侧的索引定义为左指针(left)，最右侧的定义为右指针(right)，然后从两头向中间进行数组遍历。

对撞数组适用于连续数组和字符串，也就是说当你遇到题目给定连续数组和字符床时，应该第一时间想到用对撞指针解题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//伪代码
function fn (list) {
  var left = 0;
  var right = list.length - 1;

  //遍历数组
  while (left <= right) {
    left++;
    // 一些条件判断 和处理
    ... ...
    right--;
  }
}

//对撞指针能够解决：：1.二分查找 2.两数之和 II - 输入有序数组 3.反转字符串 4.反转字符串中的元音字母 5.回文字符串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//实现函数
void reS(char s[]){
    int length = strlen(s); // 计算数组长度
    if(length == 0 || length == 1) return;
    int left = 0;
    int right = length - 1;
    while(left < right){
        // 交换数据
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp; 
        left++; 
        right--; 
    }
    return;
}

快慢指针

快慢指针也是双指针，但是两个指针从同一侧开始遍历数组，将这两个指针分别定义为快指针（fast）和慢指针（slow），两个指针以不同的策略移动，直到两个指针的值相等（或其他特殊条件）为止，如 fast 每次增长两个，slow 每次增长一个。

一般快慢指针用于维护区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//伪代码
slow = head;
fast = head;
while (fast != NULL && fast->next != NULL) {
    slow = slow->next;
    fast = fast->next->next;
    if (slow == fast) {
        return true;
    }
}
return false;

//快慢指针能够解决：链表中倒数第k个节点  1.链表的中间节点 2.链表是否有环 3.链表环的长度 4.链表环的起点
//判断链表是否有环
bool hasCycle(ListNode *head) {
    if (head == NULL || head->next == NULL) {
        return false;
    }
    ListNode *slow = head; // 慢指针
    ListNode *fast = head->next; // 快指针
    while (slow != fast) { // 当快慢指针不相遇时
        if (fast == NULL || fast->next == NULL) { // 如果快指针到达链表尾部，说明链表没有环
            return false;
        }
        slow = slow->next; // 慢指针走一步
        fast = fast->next->next; // 快指针走两步
    }
    return true; // 如果快慢指针相遇，说明链表有环
}

哈希表*

哈希表的实现

实现方法可以看看，实际上用的是stl中的hash，可以直接理解成 输入数据 -> f(x) ->映射为另一数据，不需要太过于纠结怎么实现的原理

散列表（Hash Table）是一种特殊的数据结构，它最大的特点就是可以快速实现查找、插入和删除。数组的最大特点就是：寻址容易，插入和删除困难；而链表正好相反，寻址困难，而插入和删除操作容易。结合两者的优点，做出一种寻址、插入和删除操作同样快速容易的数据结构。这就是哈希表创建的基本思想。

map: a经过哈希函数变为b，产生映射关系

hash表本质是数组，散列的数据集中到一个数组上，用最少资源按照一定的逻辑存储我们的数据

说人话就是大范围索引存储改为小范围索引存储

哈希函数：也称为是散列函数，是Hash表的映射函数，它可以把任意长度的输入变换成固定长度的输出，该输出就是哈希值。

哈希函数相当于排列规则，我们可以依靠这个排列规则排列键的顺序，同时也可以用这个排列规则寻找我们的值.

如果用日常生活来举例的话，哈希表转换结果就是我们的字典目录一样。

哈希表和哈希函数的标准定义：若关键字为k，则其值存放在h(k)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为哈希函数，按这个思想建立的表为哈希表。

设计出一个简单、均匀、存储利用率高的散列函数是散列技术中最关键的问题。
但是，一般散列函数都面临着冲突的问题。两个不同的关键字，由于散列函数值相同，因而被映射到同一表位置上。该现象称为冲突(Collision)或碰撞。发生冲突的两个关键字称为该散列函数的同义词(Synonym)。

哈希表的实现就是映射函数构造，看某个元素具体属于哪一个类别。如何构造我们要考虑两个问题：

  • n个数据原仅占用n个地址，虽然散列查找是以空间换时间，但仍希望散列的地址空间尽量小。
  • 无论用什么方法存储，目的都是尽量均匀地存放元素，以避免冲突。

直接定位法

Hash(key) = a·key + b (a、b为常数)

优点：以关键码key的某个线性函数值为哈希地址，不会产生冲突.

缺点：要占用连续地址空间，空间效率低。

例：关键码集合为{100，300，500，700，800，900}， 选取哈希函数为Hash(key)=key/100， 则存储结构（哈希表）如下：

这种方法计算最简单，且不会产生冲突。适合于关键字分布基本连续的情况，如果关键字分布不连续，空位较多，则会造成存储空间的浪费。

举一个例子，假设有一个记录了从 1 岁到 100 岁的人口数字统计表。其中年龄为关键字，哈希函数取关键字自身，如下表所示。

比如想要查询 25 岁的人有多少，则只要查询表中第 25 项即可。

这种方法一般不使用，除非是我们查询的表比较简单的情况之下。

除留余数法

Hash(key) = key mod p (p是一个整数)

特点：以关键码除以p的余数作为哈希地址。

关键：如何选取合适的p？

技巧：若设计的哈希表长为m，则一般取p≤m且为质数 （也可以是不包含小于20质因子的合数）。

取p≤m且为质数是为了少开区间，mod质数是为了输出不同区间的值，让数据更加散乱。

这种方法是最常见构造散列表的方法

乘余取整法

Hash(key) = [B*( A*key mod p ) ]下取整 (A、B均为常数，且0<A<1，B为整数)

特点：以关键码key乘以A，取其小数部分，然后再放大B倍并取整，作为哈希地址。

例：欲以学号最后两位作为地址，则哈希函数应为： H(k)=100*(0.01*k % p )其实也可以用法2实现：H(k)=k % 100

这也是一种简单且常用的哈希函数方法。其关键点在于p 的选择。根据经验而言，一般 p 取素数或者 m，这样可以尽可能的减少冲突。(可以理解p为限定映射区域)

比如我们需要将 7 个数 [432, 5, 128, 193, 92, 111, 88] 存储在 11 个区块中（长度为 11 的数组），通过除留余数法将这 7 个数应分别位于如下地址：

比如432，对11取余数，余数为3，放在03位置

数字分析法

特点：某关键字的某几位组合成哈希地址。所选的位应当是：各种符号在该位上出现的频率大致相同。

例：有一组（例如80个）关键码，其样式如下：

平方取中法

特点：对关键码平方后，按哈希表大小，取中间的若干位作为哈希地址。

理由：因为中间几位与数据的每一位都相关。（乘法的性质）

例：2589的平方值为6702921，可以取中间的029为地址。

折叠法

特点：将关键码自左到右分成位数相等的几部分（最后一部分位数可以短些），然后将这几部分叠加求和，并按哈希表表长，取后几位作为哈希地址。

适用于：每一位上各符号出现概率大致相同的情况。

法1：移位法 ── 将各部分的最后一位对齐相加。

法2：间界叠加法──从一端向另一端沿分割界来回折叠后，最后一位对齐相加。

例：元素42751896, 用法1： 427＋518＋96=1041 用法2： 427 518 96—> 724+518+69 =1311

哈希表优化冲突*

Hash表解决冲突的方法主要有以下几种：

开放定址法（开地址法）、 链地址法（拉链法）、 再哈希法（双哈希函数法）、 建立一个公共溢出区，而最常用的就是开发定址法和链地址法。

开放寻址法

开放寻址法：又称开放定址法，当哈希碰撞发生时，从发生碰撞的那个单元起，按照一定的次序，从哈希表中寻找一个空闲的单元，然后把发生冲突的元素存入到该单元。这个空闲单元又称为开放单元或者空白单元。

就是映射的位置有数了，就在这个位置的下一个位置存储，如果还有继续查找下一个位置以此类推。

查找时，如果探查到空白单元，即表中无待查的关键字，则查找失败。开放寻址法需要的表长度要大于等于所需要存放的元素数量，非常适用于装载因子较小（小于0.5）的散列表。

开放定址法的缺点在于删除元素的时候不能真的删除，否则会引起查找错误，只能做一个特殊标记，直到有下个元素插入才能真正删除该元素。

可以把开放寻址法想象成一个停车问题。若当前车位已经有车，则继续往前开，直到找到一个空停车位。

设计思路：有冲突时就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。

含义：一旦冲突，就找附近（下一个）空地址存入。

开放寻址法的基本函数是：

1
Hi(key)=(H(key) + f(i)) MOD m, i=0,1,2,…, k(k<=m-1)，

其中，m 为散列表长度，一般为素数；

H(key) 为散列函数，用于计算索引，key为关键字值；

f(i) 为增量序列，用于解决冲突，且f(0) = 0，i为已经尝试计算索引的次数。

当散列值H0(key)发生冲突时，再计算H1(key)……，直到不冲突为止。

实现步骤

得到给定的 key；

根据函数计算得 hashValue；

若不冲突，则把关键字值存入下标为hashValue的桶；

若冲突，则使 i++ ，也就是往后找，直到找到第一个空桶并填入当前key。若到了尾部则循环到前面。

线性探查法

冲突函数：是i的一次多项式，典型取法为f(i)=i。

​ 线行探查法(Linear Probing)是开放定址法中最简单的冲突处理方法，它从发生冲突的单元起，依次判断下一个单元是否为空，当达到最后一个单元时，再从表首依次判断。直到碰到空闲的单元或者探查完全部单元为止。

​ 对于一个散列表，在散列过程中，某些元素形成一些区块，这种现象称作一次聚集（primary clustering）。就是说，散列到区块中的任何关键字都需要多次探测才可以解决哈希碰撞，然后，把该关键字添加到相应区块的桶中。

下面是一道例题用线性探查实现开放寻址法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <cstring>
#include <iostream>

using namespace std;

const int N = 200003, null = 0x3f3f3f3f;

int h[N];

int find(int x)
{
    int t = (x % N + N) % N;
    //开放寻址法就是 挨个找，找不到就算，找到了就返回呗
    while (h[t] != null && h[t] != x)//没到尽头和不为我们的目标值
    {
        t ++ ;
        if (t == N) t = 0;//指针回位
    }
    return t;
}

int main()
{
    memset(h, 0x3f, sizeof h);

    int n;
    scanf("%d", &n);

    while (n -- )
    {
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        if (*op == 'I') h[find(x)] = x;
        else
        {
            if (h[find(x)] == null) puts("No");
            else puts("Yes");
        }
    }

    return 0;
}

拉链法

基本思想：将具有相同哈希地址的记录链成一个单链表，m个哈希地址就设m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构。

注：有冲突的元素可以插在表尾,也可以插在表头

例：设{ 47, 7, 29, 11, 16, 92, 22, 8, 3, 50, 37, 89 }的哈希函数为： Hash(key)=key mod 11， 用拉链法处理冲突，则建表如下图所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/*拉链法实现上诉题目*/
#include <cstring>
#include <iostream>

using namespace std;

const int N = 1e5 + 3;  // 取大于1e5的第一个质数，取质数冲突的概率最小 可以百度

//* 开一个槽 h
int h[N], e[N], ne[N], idx;  //邻接表

void insert(int x) {
    // c++中如果是负数 那他取模也是负的 所以 加N 再 %N 就一定是一个正数
    int k = (x % N + N) % N;
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx++;
}

bool find(int x) {
    //用上面同样的 Hash函数 讲x映射到 从 0-1e5 之间的数
    int k = (x % N + N) % N;
    for (int i = h[k]; i != -1; i = ne[i]) {
        if (e[i] == x) {
            return true;
        }
    }
    return false;
}

int n;

int main() {
    cin >> n;

    memset(h, -1, sizeof h);  //将槽先清空 空指针一般用 -1 来表示

    while (n--) {
        string op;
        int x;
        cin >> op >> x;
        if (op == "I") {
            insert(x);
        } else {
            if (find(x)) {
                puts("Yes");
            } else {
                puts("No");
            }
        }
    }
    return 0;
}

双散列*

冲突函数：f(i) = i * hash2(key)，典型取法是令hash2(key)=PRIME – (key ％ PRIME)，其中 PRIME 是小于散列表大小的质数。

双散列（double hashing）使用两个散列函数H(key)和hash2(key)。hash2(key)也以关键字为自变量，产生一个l至m-1之间的、并和m互素的数(即m不能被该数整除)作为探查序列的地址增量(即步长)。

要扩充哈希表，首先必须找下一个新的且够大(大约2倍)的质数，然后必须考虑重哈希的成本。我们不可能原封不动的拷贝，必须要检验旧表格中的每个元素，计算其在新表格中的位置，然后再插入到新表格中。

平方探查法*

冲突函数：是i的二次多项式，典型取法为f(i)=i^2。

平方探测法（Quadratic Probing）即是发生冲突时，用发生冲突的单元H(key), 加上 1²、 2²等，即H(key) + 1²，H(key) + 2²，H(key) + 3²...直到找到空闲单元。f(i)也可以构造为：±i^2,i=1,2,3,...,k。

在实际操作中，平方探测法不能探查到全部剩余的桶。不过在实际应用中，散列表如果大小是素数，并且至少有一半是空的，那么，总能够插入一个新的关键字。若探查到一半桶仍未找一个空闲的，表明此散列表太满，应该重哈希。平方探测法是解决线性探测中一次聚集问题的解决方法，但是，她引入了被称为二次聚集的问题——散列到同一个桶的那些元素将探测到相同的备选桶。下面的技术将会排除这个遗憾，不过要付出计算一个附加的哈希函数的代价。

字符串哈希

构造唯一数据表示字符串，可以理解为 f(x) = y。就是通过某种方法转化，使得两个毫无相关的数据产生关系。但是为了将映射关系进行一一对应，也就是，一个字符串对应一个数字，那么一个数字也对应一个字符串。
用字符串Hash的目的是，我们如果要比较一个字符串，我们不直接比较字符串，而是比较它对应映射的数字，这样子就知道两个子串是否相等。从而达到，子串的Hash值的时间复杂度为 O(1)，进而可以利用空间换时间来节省时间复杂度。我们希望这个映射是一个单射，所以问题就是如何构造这个Hash函数，使得他们成为一个单射。

构造字符串hash

简单例子，假设给你一个数字1166，形式上你只知道它只是1和6的组合，但你知道它代表的实际是1*10^3+1*10^2+6*10^1+6*10^0。
同理，给你一个字符串，要把它转换为数字，就可以先把每一个字符都先对应一个数字，然后把它们按照顺序乘以进制（Base）的幂进行相加，然后这个数可能很大，所以一般会取余数（MOD）。前面说过了，取模操作实际上是限制了数的长度。
根据上面的理解，其实将字符串映射成数字，和平时的将一个二进制，变为一个十进制数。相类似，把字符串当成，某种进制的数据，把字符串拆成很多位，然后对每一个位置的字符都进行哈希操作，再用进制的乘法操作将他们拼接起来。

这里我举个例子：11111，映射为一个值。这里假设值是O，映射的进制是10嘛

那么O = 1*10000+1*1000+1*100+1*10+1*1. 这样就可以映射了。

应对于:abcde。指定一个进制p，那么映射结果就是：

o = a*p^4+b*p^3+c*p^2+d*p^1+e*p^0。这就是一个最基础的字符串映射。

先定义以下：给定一个字符串 S = s1s2s3...sn对于每一个si就是一个字母，那么我们规定: idx(si) = si-'a'+1 （当然也可以直接用其ASCII值）。构造字符串Hash总共有三种方法。每一种方法，主要都是用使用 Base 和 MOD（都要求是素数），一般都是Base < MOD，同时将Base和MOD尽量取大即可，这种情况下，冲突（即不同字符串却有着相同的hash值）的概率是很低的。自然溢出方法，对于自然溢出方法，定义 Base ，而MOD对于自然溢出方法，就是 unsigned long long 整数的自然溢出

怎么构建我们的字符串前缀?

  • 将整个数组 当做是一个p进制的数。 通过这样的方式，将我们的字符串变成数字进行操作，但是我们这个数组转化完成可能会非常大，那么我们就mod一个大的数据，通过这样的方法映射到小区间中。
  • 字符串哈希完全不考虑冲突的情况 p = 131 or 13331 - Q = 2e64 这样可以忽略冲突 （溢出等价于 mod 2e64）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//相当于将字符型映射为整型（本来就是 将字符串映射成一个p进制的数据 - p一般为质数）
typedef unsigned long long ULL;
const int P = 131;
// p[i] = P^i, h[i] = s[1~i]的hash值
ULL p[N],h[N];

//预处理
void init()
{
    //字符串长度就是对应的进制 p^n - 也可以说是长度是项数的个数
    p[0] = 1,h[0] = 0;
    for(int i = 1;i<=n;i++){
        p[i] = p[i-1]*P; //P是进制
        h[i] = h[i-1]*P+s[i];//s是对应字符的ASCII值是吧
    }
}
//计算s[l~r]的哈希值
ULL get(int l,int r)
{
    return h[r]-h[l-1]*p[r-l+1];
}
//判断两个子串是否相等
bool substr(int l1,int r1,int l2,int r2){
    return get(l1,r1) == get(l2,r2);
}

高精度

在平常的实现中，高精度数字利用字符串表示，每一个字符表示数字的一个十进制位。因此可以说，高精度数值计算实际上是一种特别的字符串处理。

读入字符串时，数字最高位在字符串首（下标小的位置）。但是习惯上，下标最小的位置存放的是数字的 最低位，即存储反转的字符串。这么做的原因在于，数字的长度可能发生变化，但我们希望同样权值位始终保持对齐（例如，希望所有的个位都在下标 [0]，所有的十位都在下标 [1]……）；同时，加、减、乘的运算一般都从个位开始进行（回想小学的竖式运算），这都给了「反转存储」以充分的理由。（还有一个很重要的点，倒序可以消除前导0）

存储与读入

我们读入的数据是一个很长很长的数字，我们可以用字符串存储或者使用数组存储。下面是读入模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//初始化
void clear(int a[]){
    for(int i = 0;i< LEN;++i) a[i] = 0;
}

//读取数据
void read(int a[]){
    static char s[LEN+1];
 //输入字符串
    scanf("%s",s);    
    clear(a);
    //长度
    int len = strlen(s);
    //数据字符最小位置 - 转化
    for(int i = 0;i<len;++i) a[len-i-1] = s[i] - '0';
}

打印模版

1
2
3
4
5
6
7
8
//打印数据
void print(int a[]){
 int i;
    for(i = LEN - 1;i>=1;--i) if(a[i] != 0) break;
    //putchar 打印一个字符 这里传入的是int所以说要转化为char
    for(;i>=0;--i) putchar(a[i] + '0');
    putchar('\n');
}

高精度加法计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<cstdio>
#include<cstring>

static const int LEN = 1004;

int a[LEN],b[LEN],c[LEN];

void clear(int a[])
{
    for(int i = 0;i<=LEN;++i) a[i] = 0;
}

void read(int a[]){
    //用字符数组存储
    static char s[LEN+1];
    scanf("%s",s); //这里输入可以连续存入？
    
    //插入的数组 - 清理一下
    clear(a);
    int len = strlen(s);
    //转化为整数 - 高位在右低位在左
    for(int i = 0;i<len;++i) a[len-i-1] = s[i] - '0';    
}

void print(int a[]){
 int i;
    //打印低到高位置
    for(i = LEN - 1;i>=1;--i) if(a[i]!=0) break;
    //这里的i已经初始化为LEN-1了
    for(;i>=0;--i) putchar(a[i] + '0');
    putchar("\n");
}

void add(int a[],int b[],int c){
    clear(c);
    //先+再处理
    for(int i = 0;i<LEN-1;++i){
        c[i] += a[i]+b[i];
        //处理，进1
        if(c[i]>=10){
            c[i+1] += 1; 
            c[i]-=10;
        }
    }
}

int main(){
    read(a);
    read(b);
    
    add(a,b,c);
    print(c);
    return 0;
}

高精度减法计算

减法和加法一样，只不过进位变为了借位。

1
2
3
4
5
6
7
8
9
10
11
12
13
void sub(int a[], int b[], int c[]) {
  clear(c);

  for (int i = 0; i < LEN - 1; ++i) {
    // 逐位相减
    c[i] += a[i] - b[i];
    if (c[i] < 0) {
      // 借位
      c[i + 1] -= 1;
      c[i] += 10;
    }
  }
}

不过需要注意，竖式计算的减法，需要上面大于下面：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <cstdio>
#include <cstring>

static const int LEN = 1004;

int a[LEN], b[LEN], c[LEN];

void clear(int a[]) {
  for (int i = 0; i < LEN; ++i) a[i] = 0;
}

void read(int a[]) {
  static char s[LEN + 1];
  scanf("%s", s);

  clear(a);

  int len = strlen(s);
  for (int i = 0; i < len; ++i) a[len - i - 1] = s[i] - '0';
}

void print(int a[]) {
  int i;
  for (i = LEN - 1; i >= 1; --i)
    if (a[i] != 0) break;
  for (; i >= 0; --i) putchar(a[i] + '0');
  putchar('\n');
}

void sub(int a[], int b[], int c[]) {
  clear(c);

  for (int i = 0; i < LEN - 1; ++i) {
    c[i] += a[i] - b[i];
    if (c[i] < 0) {
      c[i + 1] -= 1;
      c[i] += 10;
    }
  }
}

int main() {
   read(a);
   read(b);
   //需要判断谁在上面
   if(a>b) sub(a, b, c);
   else sub(b,a,c);  
   print(c);
   return 0;
}

高精度乘法计算

有两种情况，一种是小数据*大数据，另一种就是大数据*大数据。如果是第一种，直接把小的数据当成一个值，直接乘大数据，再对大精度的每一位的处理就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void mul_short(int a[], int b, int c[]) {
  clear(c);

  for (int i = 0; i < LEN - 1; ++i) {
    // 直接把 a 的第 i 位数码乘以乘数，加入结果
    c[i] += a[i] * b;

    if (c[i] >= 10) {
      // 处理进位
      // c[i] / 10 即除法的商数成为进位的增量值
      c[i + 1] += c[i] / 10;
      // 而 c[i] % 10 即除法的余数成为在当前位留下的值
      c[i] %= 10;
    }
  }
}

这种方法，需要a,b两个数据不在同一数量级，如果在同一数量级会导致数据溢出。

第二种方法是竖式乘法，竖式乘法的本质是计算若干个a*bi*10^i的和，例如计算1337 * 42其实是1337*2*10^0 + 1337*4*10^1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void mul(int a[], int b[], int c[]) {
  clear(c);

  for (int i = 0; i < LEN - 1; ++i) {
    // 这里直接计算结果中的从低到高第 i 位，且一并处理了进位
    // 第 i 次循环为 c[i] 加上了所有满足 p + q = i 的 a[p] 与 b[q] 的乘积之和
    // 这样做的效果和直接进行上图的运算最后求和是一样的，只是更加简短的一种实现方式
    for (int j = 0; j <= i; ++j) c[i] += a[j] * b[i - j];
 //乘完一轮处理一下
    if (c[i] >= 10) {
      c[i + 1] += c[i] / 10;
      c[i] %= 10;
    }
  }
}

高精度除法计算*

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// 被除数 a 以下标 last_dg 为最低位，是否可以再减去除数 b 而保持非负
// len 是除数 b 的长度，避免反复计算
bool greater_eq(int a[], int b[], int last_dg, int len) {
  // 有可能被除数剩余的部分比除数长，这个情况下最多多出 1 位，故如此判断即可
  if (a[last_dg + len] != 0) return true;
  // 从高位到低位，逐位比较
  for (int i = len - 1; i >= 0; --i) {
    if (a[last_dg + i] > b[i]) return true;
    if (a[last_dg + i] < b[i]) return false;
  }
  // 相等的情形下也是可行的
  return true;
}

void div(int a[], int b[], int c[], int d[]) {
  clear(c);
  clear(d);

  int la, lb;
  for (la = LEN - 1; la > 0; --la)
    if (a[la - 1] != 0) break;
  for (lb = LEN - 1; lb > 0; --lb)
    if (b[lb - 1] != 0) break;
  if (lb == 0) {
    puts("> <");
    return;
  }  // 除数不能为零

  // c 是商
  // d 是被除数的剩余部分，算法结束后自然成为余数
  for (int i = 0; i < la; ++i) d[i] = a[i];
  for (int i = la - lb; i >= 0; --i) {
    // 计算商的第 i 位
    while (greater_eq(d, b, i, lb)) {
      // 若可以减，则减
      // 这一段是一个高精度减法
      for (int j = 0; j < lb; ++j) {
        d[i + j] -= b[j];
        if (d[i + j] < 0) {
          d[i + j + 1] -= 1;
          d[i + j] += 10;
        }
      }
      // 使商的这一位增加 1
      c[i] += 1;
      // 返回循环开头，重新检查
    }
  }
}

二分

二分查找的思路很简单，我们需要找的数据都是在数组中嘛，只要将这个数组分为两个部分，然后在左边找不到就到右边找，然后再把剩下的数组分为两部分，以此类推。但是需要注意一些细节，Knuth 大佬（发明 KMP 算法的那位）都说二分查找：思路很简单，细节是魔鬼.

二分查找采用双指针的形式，来对我们数组序列进行遍历。二分查找只使用于排好序的数组，不适用于其他。掌握二分查找的关键是，要明白数组是怎么分成两部分，两部分的边界是什么组成的。

暴力

暴力就是按照对应序列一个一个找，直到找到目标为止，没有找到就返回-1

1
2
3
4
5
6
7
int a[N];
int ans;
for(int i = 1;i<N;i++){
    if(a[i] == ans) return true;
  else break;
}
if(a[N]!=ans) return false;

这可以用蓝红划分数组来解释，假设我们数组开始全是灰色(没有被遍历)，设计一个蓝色指针指向数组的最左边，从左往右扫到蓝红边界，知道扫到目标值。

然后也同样，也可以在最右边设计一个红色指针，从右往左扫直到扫到蓝红边界，直到扫到我们的目标值。

这样的算法是十分低效的，原因是因为指针移动速度缓慢，每次只能在数组中搜索到一个值的信息。

二分细节

在上面，我们用蓝红表示二分数组中两个不同的区域：

如果我们在数组中间发现一个指针为蓝色，那么很显然这个指针之前的颜色全为蓝色：

同样的我们在右侧发现了一个红色区域块，就可以推断出其右侧区域都是红色

通过这样不断操作，直到找到我们的蓝红边界：

我们为什么要找蓝红边界，因为二分有几个常见的问题需要我们解决，假设ans是我们需要找到的二分值，对这个值我们有如下问题：

  • 找到第一个>=ans的元素
  • 找到最后一个<ans的元素
  • 找到第一个>ans的元素
  • 找到最后一个<=ans的元素

对于这个值暂时不去讨论，我们先搞定拓展红蓝色的代码：

1
2
3
4
5
6
7
8
//伪代码
l = -1,r = N;
while(l+1!=r){//直到达到边界
    m = (l+R)/2; //这里需要向下取整？
    if(isBlue(m)) l = m; //蓝色边界蔓延至我们的m
    else r = m; //反之就红色边界蔓延
    return l or r //缩小到最后就是我们要找的目标值
}

开始l指针指向蓝色区域，r指针指向红色区域，循环直到达到边界，保持l,r颜色不发生改变，遍历结束l,r就达到了蓝红边界处。二分查找的时间复杂度是o(log n),也就是一直在折半。

为什么l区域初始化为-1，这是因为我们需要再数组中分蓝和红区域，如果将l初始化为1，恰好数组中全是红色区域，这样就矛盾了。同理，r也不可以取r-1这个位置，也会导致矛盾。

同时验证一下m是否都在数组中，因为l最小值是-1,r最小值是1(这里r最小值是因为 l+1 = r 的时候会直接退出，如果r = 0那么就会直接跳出循环) ，m的最小值也就为 (1 + 1 )/2= 0。以此类推，l的最大值应该是N-2（N1跳出循环体循环），那么r的最大值也是为N(边界嘛)。所以说最大值是(N-2+N-1)/2 = N/2

更新指针的时候，都是指向蓝红边界的位置，如果我们改变为l = m+1会导致区域发生错误，我们就用更新为m和r的模版就行，不会搞乱自己。

死循环问题：全部问题都会归类为第一种退出循环的方式

1
2
3
4
5
6
7
8
9
10
11
//判断值 用m比对我们需要的值 - 需要的值是在左边还是在右边
isBlue(m)

//伪代码
l = -1,r = N;
while(l+1!=r){//直到达到边界
    m = (l+R)/2; //这里需要向下取整？
    if(isBlue(m)) l = m; //蓝色边界蔓延至我们的m
    else r = m; //反之就红色边界蔓延
    return l or r //缩小到最后就是我们要找的目标值
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
using namespace std;

const int N = 1e5+10;
int q[N];

int main()
{
    int n,m,k;
    cin>>n>>m;
    for(int i = 0;i<n;i++) cin>>q[i];
    
    //l和r是两个不同的区域蔓延的
    
    while(m--){
        //最开始出现 - 最后出现的位置 - 从0开始计数
        cin>>k;
        //红蓝区域
        int l = -1,r = n+1;
        while(l+1<r){
            int mid = (l+r)/2;
            if(q[mid]>=k) r= mid;
            else l = mid;
        }
        if(q[r] == k){
            //红色区域将二分点包括了
            cout<<r<<" ";
            r = n;
            //找到二分边界
            while(l+1<r){
                int mid = (l+r)/2;
                if(q[mid]<=k) l = mid;
                else r = mid;
            }
            //蓝色区域将二分点包括了
            cout<<l<<endl;
        }
        else out<<"-1 -1"<<endl;
    }
    
    
}

STL中的二分

stl中，有基于二分查找原理所构造的函数体：

lower_bound()函数用于在指定区域内查找不小于目标值的第一个元素，也就是查找和目标值相等或者比目标值大的数据。用法：

1
2
3
4
//在[first,last]中查找不小于val的元素
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,const T& val);
//在 [first, last) 区域内查找第一个不符合 comp 规则的元素
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);

upper_bound()函数，用于指向查找范围内大于目标值的第一个元素，用法：

1
2
3
4
//查找[first, last)区域中第一个大于 val 的元素。
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,const T& val);
//查找[first, last)区域中第一个不符合 comp 规则的元素
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);

二分答案

使用模版来解决二分答案问题，一般构造二分答案用两个步骤

  • 分析问题，构造check函数
  • 通过问题，决定二分的输出

与二分查找不同，二分答案的目标值是给一系列条件限制的。所以说我们需要check函数来构造符合题意的分割方式。

可以理解为，二分查找是在一维的数组中找到指定的值，二分答案是在二维的数组中找到指定的值。这里的维度表示约束变量，也就是说二分答案的时候我们有两个约束条件来考虑。

在满足两个条件的情况之下，绿色部分是我们的可选区域，也就是我们的值在这一个范围之内考虑，我们也可以通过考虑在变量约束情况之下，构造的check函数的单调性，来构造我们的check。下面是构造的模版代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool check(int x){
 //通过一系列条件构造出y
    //C可以理解为约束y的条件
    return y<=C; //x小，y小 这里返回值要看实际构造的函数的单调性
    return y>=C  //x小，y大
}

int find(){
    int l = -1,r = n+1;
    while(l+1<r){
        int mid = r+l>>1;
    //这里最大化 - 由二分查找我们可以知道压缩了蓝色空间
        //在图中可以理解为 x在可行区域内 - check为真 - l右边移动
        if(check(mid)) l = mid; 
        else r = mid;
    }
    return l;
}

同理，最小化答案也是一样的。只不过我们找的可行区域是不一样的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool check(int x){
 //通过一系列条件构造出y
    //C可以理解为约束y的条件
    return y<=C; //x大，y大 这里返回值要看实际构造的函数的单调性
    return y>=C  //x大，y小
}

int find(){
    int l = -1,r = n+1;
    while(l+1<r){
        int mid = r+l>>1;
  //最小化
        //压缩了红色的空间
        if(check(mid)) r = mid; 
        else r = mid;
    }
    return r;
}

在函数图像上我们可以看见，我们要求的的最大值和最小值，可以是在我们x轴的左侧也可以是在右侧。这里要看我们构造的check函数的单调性是递增还是递减的。

例如找最大值，递增函数，也就是x和y同增同减，那么往往最大值是在右侧；递减函数，也就是x越大，y越小。那么最大值往往是在左侧。但是x和y在题目中谁是谁怎么划分呢？

emmmm那只能用题目来理解了：

先判断，最终输出的结果是什么，题目要求我们输出l的最大值,那就说明了这道题是一个最大化的二分答案。（但是不知道啥时候该用二分哈哈哈）

既然是最大值，那么答案一定是在右边咯，所以说find函数确定了，然后x也确定了就是我们每段木头的最大值。再分析约束条件，题目要求把我们的木头切割成k段，那么y找到了，它的约束条件也就是y>=k咯（切割的段数要满足）。严谨一点，我们打一个表（这里直接照搬了）

分析x和y构成的函数，发现x越大那么y越小。说明是一个减函数。

观察图像，我们很容易就可以知道我们的l应该是在满足y的情况下尽可能靠右。这里x的区间呢，也就是[0,max]。为什么是这个区间呢，原因是如果我们不加y限制，那么我们想切多长就切多长呗。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>
using namespce std;

typedef long long LL;
const int N = 1e5+10;
int n,k,a[N];

bool check(int x){
    LL y = 0; //段数
    for(int i = 1;i<=n;i++) y+=a[i]/x; //y分割 - 这里的y可以看作段数
    //必须满足这个条件嘞
    return y>=k;
}

int find(){
    int l = 0,r = 1e8+10; //查找最大值，从左逼近，所以说右边随便设置超过限制的就行
    while(l+1<r){
        int mid = l+r>>1;
        if(check(mid)) l = mid; //最大化 - 看函数图像来理解
        else r = mid;
    }
    return l;
}

int main(){
    scnaf("%d%d",&n,&k);
    for(int i = 1;i<=n;i++) scanf("%d",&a[i]);
    printf("%d\n",find());
    return 0;
}

顺序也就是：

  • 第一，分析二分答案确定 x
  • 第二，确定函数是增函数还是减函数，然后确定求的答案是最大化还是最小化
  • 第三，根据第一第二构造我们的 check() 函数