grant's Blog

记录生活中的点点滴滴

算法基础课笔记（六）

发表于 更新于 分类于 ，   阅读次数： Valine：
本文字数： 6.2k 阅读时长 ≈ 6 分钟

1.9：位运算

常用操作：

(1) 求x的第k位数字 x >> k & 1

(2) lowbit(x) = x & -x = x & (~x + 1)，返回x的最后一位1及后面所有0构成的数

~n是对n的所有二进制位取反，也就是n的反码，~n+1也就是n的补码。

例题：801. 二进制中1的个数（模板题）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
给定一个长度为 n 的数列，请你求出数列中每个数的二进制表示中 1 的个数。

输入格式
第一行包含整数 n。
第二行包含 n 个整数，表示整个数列。

输出格式
共一行，包含 n 个整数，其中的第 i 个数表示数列中的第 i 个数的二进制表示中 1 的个数。

数据范围
1≤n≤100000,
0≤数列中元素的值≤10^9
输入样例：
5
1 2 3 4 5
输出样例：
1 1 2 1 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <cstdio>
using namespace std;

int main(){
    int n;
    scanf("%d",&n);
    
    while (n--){
        int res = 0;
        int x;
        scanf("%d",&x);
        while (x){
            x -= x & -x;
            res ++;
        }
        printf("%d ",res);
    }

    return 0;
}

举个例子：

1
2
3
                              x = 1 0 0 1 0
                           ~x+1 = 0 1 1 1 0
lowbit(x) = x & (~x+1) = x & -x = 0 0 0 1 0

1.10：离散化

在一些问题中，我们只关心 n 个数字之间的相对大小关系，而不关心它们具体是多少。
因此，我们可以用一种叫离散化的技术来将数字映射到 1 ∼ n 的整数， 从而降低问题规模，简化运算。

离散化本质上可以看成是一种 哈希，其保证数据在哈希以后仍然保持原来的全/偏序关系。（保序性）

通俗地讲就是当有些数据因为本身很大或者类型不支持，自身无法作为数组的下标来方便地处理，而影响最终结果的只有元素之间的相对大小关系时，我们可以将原来的数据按照从大到小编号来处理问题，即离散化。

用来离散化的可以是大整数、浮点数、字符串等等。

考虑一个问题，给定一串正整数，从小到大排列，范围在0~10^9（很大），个数在10^5（较少）。

开一个10^9的数组显然不现实，所以需要离散化处理。

离散化 —— 模板题 AcWing 802. 区间和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素
// unique可以用库函数也可以自己实现
// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{// find的作用也就是用二分的方式通过alls中的数找到其在alls中的下标
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; // 映射到1, 2, ...n
}

find的作用也就是用二分的方式通过alls中的数找到其在alls中的下标！！！

离散化和哈希表的区别：离散化通过二分将稀疏的数据映射到连续的一串数1~n，而哈希表不会映射到连续的一串数。离散化方便后续的前缀和等对连续量的处理，而哈希表不能排序，不能这样做。

补充：不保序，实现在线的离散化。

1
2
3
4
5
6
7
8
#include <unordered_map>
unordered_map<int, int> S;

int get(int x)
{
    if (S.count(x) == 0) S[x] = ++ n;
    return S[x];
}

例题：802. 区间和（模板题）

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
假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。
现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c。
接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r] 之间的所有数的和。

输入格式
第一行包含两个整数 n 和 m。
接下来 n 行，每行包含两个整数 x 和 c。
再接下来 m 行，每行包含两个整数 l 和 r。

输出格式
共 m 行，每行输出一个询问中所求的区间内数字和。

数据范围
−10^9≤x≤10^9,
1≤n,m≤10^5,
−10^9≤l≤r≤10^9,
−10000≤c≤10000
输入样例：
3 3
1 2
3 6
7 5
1 3
4 6
7 8
输出样例：
8
0
5

思路：树状数组、线段树、离散化+前缀和都可以。

算法1：离散化+前缀和。

观察题目，虽然坐标跨度很大，但是实际用到的坐标很稀疏，最多用到n+2*m个坐标，考虑离散化处理用到的坐标x，l，r。

保序的离散化：需要把数据全部保存下来，再进行离散化。

ios::sync_with_stdio(false);，关闭同步流，iostream的缓冲跟stdio的同步。关闭之后能加速cin与cout速度，但是取消后就cin就不能和scanf，sscanf, getchar, fgets之类同时用了，否则就可能会导致输出和预期的不一样。还有，将endl替换成”\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
55
56
57
58
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int,int> PII;
const int N = 300010;// 最多n+2*m个坐标
int n,m;
int a[N],s[N];// s是前缀和数组

vector<int> alls;// 存储所有待离散化的值
vector<PII> add,query;// 插入操作和查询操作

// 二分求出输入的坐标x的离散化下标
int find(int x){// 找到第一个大于等于x的位置
    int l = 0,r = alls.size()-1;
    while (l < r){
        int mid = l+r>>1;
        if (alls[mid] < x) l = mid+1;
        else r = mid;
    }
    return r + 1;// 映射到1, 2, ...n，+1避免前缀和的下标问题
}

int main(){
    ios::sync_with_stdio(false);// 关闭同步流加速cin,cout
    cin >> n >> m;
    
    int x,c;
    for (int i = 0;i < n;i++){
        cin >> x >> c;
        add.push_back({x,c});
        alls.push_back(x);
    }
    
    int l,r;
    for (int i = 0;i < m;i++){
        cin >> l >> r;
        query.push_back({l,r});
        alls.push_back(l);
        alls.push_back(r);
    }
    // 排序，去重
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());
    // 处理插入
    for (auto item : add){
        int x = find(item.first);
        a[x] += item.second;
    }
    // 预处理前缀和
    for (int i = 1;i <= alls.size();i++) s[i] = s[i-1] + a[i];// 注意取<=
    // 处理查询
    for (auto item : query){
        int l = find(item.first),r = find(item.second);
        cout << s[r] - s[l-1] << "\n";
    }
    return 0;
}

拓展：手写unique函数。（双指针算法）

前提：已经从小到大排好序，目标：去重。

对于一个数列：1 2 2 3 3 4 5 5 7。

归纳出非重复元素的特点：

  1. 它是第一个元素；
  2. $a[i] \ne a[i-1]$.

满足以上两点之一的元素就是非重复元素。

1
2
3
4
5
6
7
8
vector<int>::iterator unique(vector<int> &a){// 针对java、python等可以手动实现
    // C++中比STL慢一点
    int j = 0;
    for (int i = 0;i < a.size();i++){
        if (!i || a[i] != a[i-1]) a[j++] = a[i];// j走得总比i慢
    }// a[0] ~ a[j - 1] 存放所有a中不重复的数
    return a.begin() + j;
}

1.11：区间合并

在蓝桥杯（二三）中提到过区间选点（贪心），和区间合并都属于一类区间贪心问题。

区间贪心整理： https://www.acwing.com/blog/content/3387/。

例题：803. 区间合并（模板题）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
给定 n 个区间 [li,ri]，要求合并所有有交集的区间。
注意如果在端点处相交，也算有交集。
输出合并完成后的区间个数。
例如：[1,3] 和 [2,6] 可以合并为一个区间 [1,6]。

输入格式
第一行包含整数 n。
接下来 n 行，每行包含两个整数 l 和 r。

输出格式
共一行，包含一个整数，表示合并区间完成后的区间个数。

数据范围
1≤n≤100000,
−10^9≤li≤ri≤10^9
输入样例：
5
1 2
2 4
5 6
7 8
7 9
输出样例：
3

注意如果在端点处相交，也算有交集。比如[1,2]和[2,3]算有交集。

思路：

1.将所有区间按左端点排序。（从小到大）

2.考虑两区间的情况，共有3种，如图。

image-20210806125719821

区间[st,ed]就是当前所维护的合并区间。

情况一：当前区间完全被上一区间覆盖，直接跳过

情况二：将当前区间的右端点更新为上一区间的右端点，达到区间延长的效果

情况三：当前区间的左端点严格大于上一区间的右端点，则表示该区间不能合并，更新区间且count++

题解一：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
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int,int> PII;
vector<PII> segs;// 存放待合并的区间

void merge(vector<PII> &segs){
    vector<PII> res;// 存答案

    sort(segs.begin(),segs.end());// pair的sort排序，优先first排序，相同再second排序
    int st = -2e9,ed = -2e9;// 初始化维护区间为-INF到-INF，本题可取-2e9
    for (auto seg : segs){
        if (ed < seg.first){
            if (st != -2e9) res.push_back({st,ed});// 加入if判断避免n=1时存入[-2e9,-2e9]
            st = seg.first,ed = seg.second;
        }
        else{
            ed = max(ed,seg.second);
        }
    }

    if (st != -2e9) res.push_back({st,ed});// 加入if判断避免n=0时存入[-2e9,-2e9]
    segs = res;
}

int main(){
    ios::sync_with_stdio(false);
    int n;
    cin >> n;

    int l,r;
    while (n--){
        cin >> l >> r;
        segs.push_back({l,r});
    }
    
    merge(segs);
    cout << segs.size() << "\n";

    return 0;
}

关于if (st != -2e9)的解释：

1.for循环内，加入if判断避免n=1时存入[-2e9,-2e9]；

2.for循环外，加入if判断避免n=0时存入[-2e9,-2e9]。（n>=1时可以不加if判断）

补充：

这种写法是先将之前完成合并的区间加入res，再更新当前区间端点。

1
2
if (st != -2e9) res.push_back({st,ed});// 加入if判断避免n=1时存入[-2e9,-2e9]
st = seg.first,ed = seg.second;

看这两句的顺序。

所以for循环之外需要多处理一次，还有每次push_back要判断。

而题解二则不用考虑，因为题解二只求区间数，先将新开拓的区间计算进答案，再来维护当前的合并区间。

题解二：题目并没有要求 求出所有具体区间左右端点，可以直接用int res = 0来记录答案，+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
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;

int n;
vector<PII> query;

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
    {
        int l, r;
        cin >> l >> r;
        query.push_back({l, r});
    } 

    sort(query.begin(), query.end());

    int cnt = 0, st = -2e9;

    for (auto item : query)
    {
        if (item.first > st) cnt ++ ;
        st = max(st, item.second);
    }

    cout << cnt << endl;
    return 0;
}
坚持原创技术分享，您的支持将鼓励我继续创作！