算法Basic-双指针位运算离散化合并区间

Posted on Edited on In Views:

双指针

799. 最长连续不重复子序列

https://www.acwing.com/problem/content/801/

  • 解析：双指针算法：$O(n)$；i一直往前；j往左最远能到什么地方；
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 arr[N], q[N];

int main()
{
    int n; scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &arr[i]);
    
    
    int res = 0;
    for( int i = 0, j = 0; i < n; i++) 
    {
        q[arr[i]]++;
        while(q[arr[i]] > 1)
        {
            q[arr[j++]]--;
        }
        res = max(res, i - j + 1);
    }
    printf("%d", res);
    
    return 0;
}

800. 数组元素的目标和

给定两个升序排序的有序数组A和B，以及一个目标值x。数组下标从0开始。
请你求出满足A[i] + B[j] = x的数对(i, j)。

数据保证有唯一解。

https://www.acwing.com/problem/content/description/802/

  • 双指针：j指针不会退后
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
const int N = 100010;
int a[N], b[N];


int main()
{
    int n, m, x; scanf("%d%d%d", &n, &m, &x);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    for(int i = 0; i < m; i++) scanf("%d", &b[i]);

    for(int i = 0, j = m - 1; i < n; i++)
    {
        while(j >= 0 && b[j] + a[i] > x) j--;
        if (b[j] + a[i] == x) cout << i << " " << j << endl;
    }
    return 0;
}

位运算

比如查看数n的二进制表示中第k位是几？

  1. 先把第k位移动到最后一位：n >> k
  2. 看个位是几？x & 1

结合就是n >> k & 1.

801. 二进制中1的个数

lowbit(x)：返回x的最后一位1； x & -x。

-x等价于~x + 1：

比如：x = 1010... 1000;

那么：~x = 0101... 0111；

~x +1 = 0101... 1000；

x & (~x +1)=0..0...1000；

应用就是得到x中1的个数。

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

int lowbit(int x)
{
    return x & -x;
}
int main()
{
    int n; cin >> n;
    while(n -- )
    {
        int res = 0;
        int x; cin >> x;
        
        while(x) x -= lowbit(x), res++;
        cout << res << " ";
    }
    return 0;
}

离散化

802. 区间和

假定有一个无限长的数轴，数轴上每个坐标上的数都是0。

现在，我们首先进行 n 次操作，每次操作将某一位置x上的数加c。

近下来，进行 m 次询问，每个询问包含两个整数l和r，你需要求出在区间[l, r]之间的所有数的和。

https://www.acwing.com/problem/content/804/

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/*
真实用到的add操作和query操作数量不多于30w，但是x本身的范围比较大，因此把需要的操作离散化到一个连续数组上进行操作。
步骤 1.把全部需要的操作用一个数组存储；
步骤 2.找到数组上对应离散的数的坐标；
步骤 3.在对应坐标上做相应操作；
*/

#include <iostream>
#include <vector> 
#include <algorithm>
using namespace std;
const int N = 300010;
typedef pair<int, int> PII;

int a[N], s[N];  // 特定问题：前缀和数组
vector<PII> add, query; // 步骤3：增加操作、查询操作
vector<int> alls;  //步骤1： 储存全部操作的数组，帮助我们找到对应映射后的数的索引


//步骤2：找到对应数字的离散化坐标
int find(int x)
{
    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开始，因为我们要使用前缀和数组
}

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        int x, c; cin >> x >> c;
        add.push_back({x, c});
        
        alls.push_back(x);
    }
    for(int i = 0; i < m; i ++)
    {
        int l, r; 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()); //去重
    
    //add操作
    for(auto it : add)
    {
        int i = find(it.first);
        a[i] += it.second;
    }
    
    //前缀和预处理
    for(int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i];
    
    //query操作
    for(auto it : query)
    {
        int l = find(it.first), r = find(it.second);
        cout << s[r] - s[l - 1] << endl;
    }
    
    return 0;
}

区间合并

步骤1：按区间左端点排序；

步骤2：那么会三种情况：重叠、半重叠、不重叠；

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
//步骤1：按区间左端点排序；

//步骤2：那么会三种情况：重叠、半重叠、不重叠；

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


const int Size = -1e9-5;
typedef pair<int, int > PII;
vector<PII> segs;

void merge(int &res)
{
    sort(segs.begin(), segs.end());
    int st = Size, ed = Size;
    for(auto it : segs)
        if(ed < it.first) //不重叠
        {
            if (ed != Size) res++; //不是初始第一个区间
            st = it.first;
            ed = it.second;
        }
        else
            ed = max(ed, it.second);
    
    if(ed != Size) res++; //最后一个区间
}

int main()
{
    int n; cin >> n;
    while(n -- )
    {
        int l , r;
        cin >> l >> r;
        segs.push_back({l, r});
    }
    
    int res = 0;
    merge(res);
    cout << res << endl;
}