第一章 基础算法
双指针
算法6：双指针，通常有两种情况：
代码结构一般是：
1
2
3
4
5
6
7
| for(i = 0, j = 0; i < n; i++)
{
while(j < i && check(i, j))
j++;
}
|
每个指针在所有循环中总共移动的次数不超过$n$，双指针算法就是将朴素的两层for遍历（时间复杂度为$O(n^2)$）优化到$O(n)$。
解题的思路一般是：从朴素做法入手，从中发现一些问题的性质，如单调性等，将原来的$O(n^2)$时间复杂度优化到$O(n)$。
双指针的几个例子：
- 读入一行字符串，其中有若干个单词，每个单词中间有一个空格隔开，要求输出每一个单词。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include<iostream>
using namespace std;
int main()
{
char str[1000];
gets(str);
int n = strlen(str);
for(int i = 0; i < n; i++)
{
int j = i;
while(j < n && str[j] != ' ') j++;
for(int k = i; k < j; k++) cout << str[k];
cout << endl;
i = j;
}
return 0;
}
|
- 最长连续不重复子序列：给定一个长度为n的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。
i表示一段区间的右边界，j表示这段区间的左边界。遍历i，找到这段区间最左能到多远，即j的位置，当i向右移时，j一定是向右移或者是不动，一定不会向左移，即是这个问题的单调性，i和j在循环走过的长度都不会超过n，因此时间复杂度是$O(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
| #include<iostream>
using namespace std;
const int N = 100010;
int a[N], s[N];
int n;
int main()
{
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];
int res = 0;
for(int i = 0, j = 0; i < n; i++)
{
s[a[i]] ++;
while(s[a[i]] > 1)
{
s[a[j]] --;
j++;
}
res = max(res, i - j + 1);
}
cout << res << endl;
return 0;
}
|
- 数组元素的目标和：给定两个升序排序的有序数组A和B，以及一个目标值x。数组下标从0开始。
请你求出满足A[i] + B[j] = x的数对(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 a[N], b[N];
int main()
{
int n, m, x;
cin >> 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(a[i] + b[j] > x) j--;
if(j >= 0 && a[i] + b[j] == x)
{
cout << i << ' ' << j << endl;
break;
}
}
return 0;
}
|
位运算
算法7：位运算
算法题中位运算的常用操作：
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;
int lowbit(int x)
{
return x & -x;
}
int main()
{
int n;
cin >> n;
while(n--)
{
int x;
cin >> x;
int res = 0;
while(x) x -= lowbit(x), res++;
cout << res << ' ' ;
}
return 0;
}
|
离散化
算法8：离散化
这里特指整数的离散化，它所针对的问题是：假设有一个数组，其元素个数很少，但元素的值域很大，如a[5]={1, 3, 100, 2000, 500000}，我们又需要以这些元素为下标进行一些其他的操作。再开一个500000长度的数组显然是不明智的，因此就需要离散化，将这些值域很大的数字映射到从0开始的连续的自然数。要进行离散化需要考虑两个问题：
a[]中可能有重复元素 $\to$ 去重；- 如何快速地算出
a[i]离散化后的值 $\to$ a[]是有序的，即找到数字的下标即可 $\to$ 二分
代码模板：
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.eras(unique(alls.begin(), alls.end()), alls.end());
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;
}
|
例子：假定有一个无限长的数轴，数轴上每个坐标上的数都是0。现在，我们首先进行 n 次操作，每次操作将某一位置x上的数加c。接下来，进行 m 次询问，每个询问包含两个整数l和r，你需要求出在区间[l, r]之间的所有数的和。
数据范围：$-10^9 \le x \le 10^9$，$1\le n, m \le 10^5$，$-10^9 \le l \le r \le 10^9$，$-10000 \le c \le 10000$。
可见相比于整个数轴的范围，要取的数是比较稀疏的，但是跨度很大，这些数的下标就可以用离散化的思想来处理。
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
| #include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 300010;
int n, m;
vector<int> alls;
vector<PII> add, query;
int a[N], s[N];
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;
}
int main()
{
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());
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] << endl;
}
return 0;
}
|
当然可以自己实现unique函数。
1
2
3
4
5
6
7
8
9
10
| vector<int>::iterator unique(vector<int> &a)
{
int j = 0;
for(int i = 0; i < a.size(); i++)
if(!i || a[i] != a[i-1])
a[j++] = a[i];
return a.begin() + j;
}
|
区间合并
算法9：区间合并
若两个区间有交集，那就可以把它们合并到一个较长的区间，可以扩展到多个区间。
例子：给定$n$个区间$[l_i,r_i]$，要求合并所有有交集的区间。注意如果在端点处相交，也算有交集。
输出合并完成后的区间个数。例如：[1,3]和[2,6]可以合并为一个区间[1,6]。
数据范围：$1\le n \le 100000$，$-10^9 \le l_i \le r_i \le 10^9$。
解题思路：
- 按区间左端点排序；
- 扫描整个区间，扫描的过程中把所有有交集的区间合并。每次维护一个当前的区间$[st, ed]$，设已扫描到第$i$个区间$[st_i, ed_i]$，那第$i$个区间和当前的区间的关系有：
- 第$i$个区间在当前的区间的内部；$\to$ 当前区间不变
- 第$i$个区间与当前的区间有交集，但不全在其内部；$\to$ 当前区间更新成$[st, ed_i]$
- 第$i$个区间与当前的区间没有有交集。$\to$ 当前区间更新成$[st_i, ed_i]$
（与区间有关的题目的思路大多都是贪心）
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
| #include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int, int> PII;
void merge(vector<PII> &segs)
{
vector<PII> res;
sort(segs.begin(), segs.end());
int st = -2e9, ed = -2e9;
for(auto seg : segs)
if(ed < seg.first)
{
if(st != -2e9) res.push_back({st, ed});
st = seg.first, ed = seg.second;
}
else ed = max(ed, seg.second);
if(st != -2e9) res.push_back({st, ed});
segs = res;
}
int main()
{
int n;
cin >> n;
vector<PII> segs;
for(int i = 0; i < n; i++)
{
int l, r;
cin >> l >> r;
segs.push_back({l, r});
}
merge(segs);
cout << segs.size() << endl;
return 0;
}
|