【AcWing】基础算法
目录
1、快速排序
1.1 快速排序
1.2 第k个数
2、归并排序
2.1 归并排序
2.2 逆序对的数量
3、二分
3.1 数的范围
3.2 数的三次方根
4、高精度
4.1 高精度加法
4.2 高精度减法
4.3 高精度乘法
4.4 高精度除法
5、前缀和与差分
5.1 前缀和
5.2 子矩阵的和
5.3 差分
5.4 差分矩阵
6、双指针算法
6.1 最长连续不重复的子序列
6.2 数组元素的目标和
6.3 判断子序列
7、位运算
8、离散化
9、区间合并
1、快速排序
1.1 快速排序
785. 快速排序 - AcWing题库
1. 确定分界点：q[l]、q[r]、q[l + r >> 2]、随机
2. 调整区间
我们要将区间调整为下面这样子
当q[i] < x时，i++，当q[i] >= x时，i停止。当q[j] > x时，j--，当q[j] <= x时，j停止。判断一下此时是否i < j，若i < j则交换，否则就出循环。
此时为什么是正确的呢？
因为在任意时刻，i左边区间内的数都是小于等于x的，j右边区间内的数都是大于等于x的
3. 递归处理左右两段
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int q[N], n;
void quick_sort(int l, int r)
{
if (l >= r) return ;
int i = l - 1, j = r + 1, x = q[l];
while (i < j)
{
while (q[ ++ i] < x) ;
while (q[ -- j] > x) ;
if (i < j) swap(q[i], q[j]);
}
quick_sort(l, j);
quick_sort(j + 1, r);
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
quick_sort(0, n - 1);
for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);
return 0;
}
讲解代码中几个需要注意的地方：
1. 为什么while(i < j)里面的两个while循环不需要先判断i < j？
i < j是为了防止越界访问。我们先来看结束时，i和j的分布情况
(1) i和j可能会相遇在某一个x，此时i == j
(2) 因为i左边的数是<=x，j右边的数是>=x，所以i一定会停在j右边的区间的第一个数，j一定会停在i左边的区间的第一个数。最先开始的时候，i的左边没有数，j的右边没有数，会不会出现意外呢？不会的，以此时选取x=q[l]为例，一开始q[i] == x，i是不会动的，j会先动。若q[j] <= x，那么交换完q[i]和q[j]后，i++，j--，i的左边有值，j的右边有值。若q[j] > x，则j--找<=x的元素，找到后，两者一交换，左右就都不为空了。
2. 为什么一上来直接i++、j--？
因为无论是正常走，还是交换完，都需要让i++、j--。
注意：初始化时i = l - 1,j = r + 1
3. 递归时的区间选择
上面我们选取的分界点是x = q[l]，递归时就是使用j，若选取的分界点是x = q[r]，递归时就是使用i，否则就会出现死循环
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int q[N], n;
void quick_sort(int l, int r)
{
if (l >= r) return ;
int i = l - 1, j = r + 1, x = q[r];
while (i < j)
{
while (q[ ++ i] < x) ;
while (q[ -- j] > x) ;
if (i < j) swap(q[i], q[j]);
}
quick_sort(l, i - 1);
quick_sort(i, r);
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
quick_sort(0, n - 1);
for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);
return 0;
}
所以当选取的分界点是q[l]或q[r]时，要注意迭代区间的更新
当然，选取分界点时也可以直接使用随机数法或区中间值的方法
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int q[N], n;
void quick_sort(int l, int r)
{
if (l >= r) return ;
swap(q[l], q[l + rand() % (r - l + 1)]);
int i = l - 1, j = r + 1, x = q[l];
while (i < j)
{
while (q[ ++ i] < x) ;
while (q[ -- j] > x) ;
if (i < j) swap(q[i], q[j]);
}
quick_sort(l, j);
quick_sort(j + 1, r);
//quick_sort(l, i - 1);
//quick_sort(i, r); 也行
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
quick_sort(0, n - 1);
for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);
return 0;
}
此时会有疑问，就是为什么此时分界点选择的是q[l]，但是递归的时候可以用i呢？
实际上也是不行的，比如像5 4 1 3 2，若rand() == 2,变为1 4 5 3 2，若用i仍然会死循环，可以是因为rand()不一定是2
这个算法相比较我们之前的快速排序算法是有优势的
void QuickSort(int* a, int left, int right)//Hoare法
{
if (left >= right)
return;
int begin = left, end = right;
//随机选key
int randi = rand() % (right - left + 1);
randi += begin;
Swap(&a[left], &a[randi]);
int keyi = left;
while (begin < end)
{
while(begin < end && a[end] >= a[keyi])
end--;
while(begin < end && a[begin] <= a[keyi])
begin++;
Swap(&a[begin], &a[end]);
}
Swap(&a[begin], &a[keyi]);
QuickSort(a, left, begin - 1);
QuickSort(a, begin + 1, right);
}我们之前的算法在遇到全相等的情况时，时间复杂度是O(N^2)，因为遇到==基准值时是会跳过去的，而现在的代码不会
1.2 第k个数
786. 第k个数 - AcWing题库
可以直接使用快速排序先将数组排序，然后再输出第k个数，时间复杂度是O(N*logN)
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int q[N],n,k;
void quick_sort(int l, int r)
{
if(l >= r) return;
swap(q[l], q[l + rand() % (r - l + 1)]);
int i = l - 1,j = r + 1,x = q[l];
while(i < j)
{
while(q[++i] < x) ;
while(q[--j] > x) ;
if(i < j) swap(q[i], q[j]);
}
quick_sort(l, j);
quick_sort(j + 1, r);
}
int main()
{
scanf("%d%d", &n, &k);
for(int i = 0;i < n;i++) scanf("%d", &q[i]);
quick_sort(0, n - 1);
printf("%d\n", q[k - 1]);
return 0;
}也可以使用快速选择算法
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int q[N],n,k;
int quick_sort(int l, int r,int k)
{
if(l >= r) return q[l];
int i = l - 1,j = r + 1,x = q[l];
while(i < j)
{
while(q[++i] < x) ;
while(q[--j] > x) ;
if(i < j) swap(q[i], q[j]);
}
int sl = j - l + 1;
if(sl >= k) return quick_sort(l, j, k);
else return quick_sort(j + 1, r, k - sl);
}
int main()
{
scanf("%d%d", &n, &k);
for(int i = 0;i < n;i++) scanf("%d", &q[i]);
cout<<quick_sort(0, n - 1, k)<<endl;
return 0;
}这道题是保证第k个数在区间里面，所以区间里面至少有1个数，可以l==r作为递归结束条件，但是快速排序中一定要是l >= r，因为快速排序中l可能大于r
2、归并排序
2.1 归并排序
787. 归并排序 - AcWing题库
1. 确定分界点 mid = (l + r) / 2
2. 递归排序左右区间
3. 归并 ---- 将两个有序数组合二为一
注意：在这个步骤中，为了保证排序的稳定性，当两指针指向的值相等时，要将第一个数组的值放入临时数组
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int q[N], tmp[N], n;
void merge_sort(int l,int r)
{
if(l >= r) return;
int mid = (l + r) / 2;
merge_sort(l, mid);
merge_sort(mid + 1, r);
int i = l,j = mid + 1,k = 0;
while(i <= mid && j <= r)
{
if(q[i] <= q[j]) tmp[k++] = q[i++];
else tmp[k++] = q[j++];
}
while(i <= mid) tmp[k++] = q[i++];
while(j <= r) tmp[k++] = q[j++];
for(i = l,j = 0;i <= r;i++,j++) q[i] = tmp[j];
}
int main()
{
scanf("%d", &n);
for(int i = 0;i < n;i++) scanf("%d", &q[i]);
merge_sort(0, n - 1);
for(int i = 0;i < n;i++) printf("%d ", q[i]);
return 0;
}2.2 逆序对的数量
788. 逆序对的数量 - AcWing题库
可以像归并排序时一样，将数组划分为两部分，此时逆序对会有3种情况
我们只需要一直向下递归，直到每个区间都只有一个值，就能都变成第三种情况
并且我们可以在归并的同时就行排序，因为当q[i] > q[j]时，则q[i]到q[mid]都是大于q[j]的
在"并"的过程中，利用两个有序数组计算逆序对的数量
此时q[i] > q[j]，那么前半数组剩余的值都和q[j]构成逆序对
注意，逆序对的数量最多会大于int，所以开long long
#include<iostream>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int q[N], tmp[N], n;
ll merge_sort(int q[], int l, int r)
{
if(l >= r) return 0;
int mid = l + r >> 1;
ll res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);
int k = 0,i = l,j = mid + 1;
while(i <= mid && j <= r)
{
if(q[i] <= q[j]) tmp[k++] = q[i++];
else
{
tmp[k++] = q[j++];
res += mid - i + 1;
}
}
while(i <= mid) tmp[k++] = q[i++];
while(j <= r) tmp[k++] = q[j++];
for(int i = l,j = 0;i <= r;i++,j++) q[i] = tmp[j];
return res;
}
int main()
{
scanf("%d", &n);
for(int i = 0;i < n;i++) scanf("%d", &q[i]);
ll res = merge_sort(q, 0, n - 1);
printf("%lld\n", res);
return 0;
}3、二分
bool check(int x) {/* ... */} // 检查x是否满足某种性质
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;
}
return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
作者：yxc
来源：AcWing模板不需要特意去记什么时候在计算中点时要+1，只需要写出check后，根据更新判断
为什么计算中点时有时候要+1，有时候不需要呢？
因为l + r >> 1是向下取整，当l = r - 1时，若chack为真，则没变，会死循环
3.1 数的范围
789. 数的范围 - AcWing题库
这道题是整数二分，分为找左端点和右端点
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], n, q, k;
int main()
{
scanf("%d %d", &n, &q);
for(int i = 0;i < n;i++) scanf("%d", &a[i]);
while(q--)
{
scanf("%d", &k);
// 先找左端点
int l = 0, r = n - 1;
while(l < r)
{
int mid = l + r >> 1;
if(a[mid] < k) l = mid + 1;
else r = mid;
}
if(a[l] != k) printf("-1 -1\n");
else
{
// 找右端点
printf("%d ", l);
l = 0, r = n - 1;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(a[mid] > k) r = mid - 1;
else l = mid;
}
printf("%d\n", l);
}
}
return 0;
}3.2 数的三次方根
790. 数的三次方根 - AcWing题库
这道题是浮点数二分，初始时让l等于数的范围的左端点，r等于数的范围的右端点，一直二分，直到l和r之间的距离足够小即可。如何定义足够小呢？如果题目的浮点数保留6位小数，则while的循环条件时r - l > 1e-8
注意：浮点数二分不能直接取l=0,r=x，因为当0<x<1时，可能会出错，如求二次方跟时，x=0.01，而0.01的二次方根是0.1。在这道题中就不需要考虑这个，因为数的范围已经确定了
#include<iostream>
using namespace std;
int main()
{
double n;
scanf("%lf", &n);
double l = -10000,r = 10000;
while(r - l > 1e-8)
{
double mid = (r + l) / 2;
if(mid * mid * mid < n) l = mid;
else r = mid;
}
printf("%lf\n", l);
return 0;
}浮点数二分相对于整数二分更加简单，因为没有+1-1，所以不需要考虑边界问题
4、高精度
这里的高精度是指大数之间的加减乘除运算
4.1 高精度加法
791. 高精度加法 - AcWing题库
高精度加法，A + B，通常A和B是大小在0到10^6的整数
大整数的存储通常使用数组来存储，并且最好是倒过来存储，方便进位
使用数组进行加法的过程就是模拟整数加法，Ci = Ai + Bi + t，t表示进位
#include<iostream>
#include<string>
#include<vector>
using namespace std;
vector<int> add(vector<int> &A, vector<int> &B)
{
vector<int> C;
int t = 0; // 记录进位
for(int i = 0;i < A.size() || i < B.size();i++)
{
if(i < A.size()) t += A[i];
if(i < B.size()) t += B[i];
C.push_back(t % 10);
t /= 10;
}
if(t) C.push_back(1);
return C;
}
int main()
{
string a, b;
vector<int> A, B;
cin>>a>>b;
for(int i = a.size() - 1;i >= 0;i--) A.push_back(a[i] - '0');
for(int i = b.size() - 1;i >= 0;i--) B.push_back(b[i] - '0');
vector<int> C = add(A, B);
for(int i = C.size() - 1;i >= 0;i--) printf("%d", C[i]);
return 0;
}4.2 高精度减法
792. 高精度减法 - AcWing题库
高精度减法，A - B，通常A和B是大小在0到10^6的整数
因为一道题中结果可能很大，会使用到高精度的加减乘除，所以四种运算的存储方式相同
若Ai - Bi - t大于等于0，Ci = Ai - Bi - t
若Ai - Bi - t小于0，Ci = Ai - Bi - t + 10，t表示借位
#include<iostream>
#include<string>
#include<vector>
using namespace std;
bool cmp(vector<int>& A, vector<int>& B)
{
if(A.size() != B.size()) return A.size() > B.size();
for(int i = A.size() - 1;i >= 0;i--)
if(A[i] != B[i]) return A[i] > B[i];
return true;
}
vector<int> sub(vector<int> &A, vector<int> &B)
{
vector<int> C;
int t = 0;
for(int i = 0;i < A.size();i++)
{
t = A[i] - t;
if(i < B.size()) t-= B[i];
C.push_back((t + 10) % 10);
if(t < 0) t = 1;
else t = 0;
}
while(C.size() > 1 && C.back() == 0) C.pop_back(); // 处理前导0
return C;
}
int main()
{
string a, b;
vector<int> A, B;
cin>>a>>b;
for(int i = a.size() - 1;i >= 0;i--) A.push_back(a[i] - '0');
for(int i = b.size() - 1;i >= 0;i--) B.push_back(b[i] - '0');
if(cmp(A, B)) // A >= B
{
vector<int> C = sub(A, B);
for(int i = C.size() - 1;i >= 0;i--) printf("%d", C[i]);
}
else
{
vector<int> C = sub(B, A);
printf("-");
for(int i = C.size() - 1;i >= 0;i--) printf("%d", C[i]);
}
return 0;
}sub中是默认A大于等于B的
(t + 10) % 10，当t >= 0时结果是不变的，当t < 0时，这个位置需要借位
还需要处理前导0，如789-786，此时A是9 8 7，B是6 8 7，减完之后C是3 0 0，反转过后也就是003，我们需要的是3，所以需要处理前导0
4.3 高精度乘法
793. 高精度乘法 - AcWing题库
高精度乘法是一个很大的数字乘一个较小的数字，len(A)<=10^6，b<=10000
我们这里是将b当成一个整体，与A的每一位相乘
Ci = (Ai * b + t) % 10，t表示进位
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int b;
vector<int> mul(vector<int>& A, int b)
{
int t = 0;
vector<int> C;
for(int i = 0;i < A.size() || t;i++) // 结束条件是A遍历完，并且t也为0
{
if(i < A.size()) t += A[i] * b;
C.push_back(t % 10);
t /= 10;
}
while(C.size() > 1 && C.back() == 0) C.pop_back(); // 处理前导0
return C;
}
int main()
{
vector<int> A;
string a; cin>>a>>b;
for(int i = a.size() - 1;i >= 0;i--) A.push_back(a[i] - '0');
vector<int> C = mul(A, b);
for(int i = C.size() - 1;i >= 0;i--) printf("%d", C[i]);
return 0;
}同样需要处理前导0，如A = [3, 2, 1]，b = 0，结果是C = [0, 0, 0]
4.4 高精度除法
高精度除法通常A <= 10^6，b <= 10000
除法是从最高位开始计算的，而加减乘都是从最低位计算，为了保持统一，除法计算完reverse
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
vector<int> div(vector<int>& A, int b,int& r)
{
vector<int> C;
r = 0;
for(int i = A.size() - 1;i >= 0;i--)
{
r = r * 10 + A[i];
C.push_back(r / b);
r %= b;
}
reverse(C.begin(), C.end());
while(C.size() > 1 && C.back() == 0) C.pop_back(); // 处理前导0
return C;
}
int main()
{
string a;
int b;
cin>>a>>b;
vector<int> A;
for(int i = a.size() - 1;i >= 0;i--) A.push_back(a[i] - '0');
int r; // 余数
vector<int> C = div(A, b, r);
for(int i = C.size() - 1;i >= 0;i--) printf("%d", C[i]);
printf("\n");
printf("%d\n", r);
return 0;
}同样需要处理前导0，如1234 / 11，A = [4, 3, 2, 1]，b = 11，计算完后C = [0, 1, 1, 2]，逆置完后C = [2, 1, 1, 0]
5、前缀和与差分
5.1 前缀和
795. 前缀和 - AcWing题库
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int q[N], dp[N], n, m, l, r;
int main()
{
scanf("%d %d", &n, &m);
for(int i = 1;i <= n;i++)
{
scanf("%d", &q[i]);
dp[i] = dp[i - 1] + q[i];
}
while(m--)
{
scanf("%d %d", &l, &r);
printf("%d\n", dp[r] - dp[l - 1]);
}
return 0;
}5.2 子矩阵的和
796. 子矩阵的和 - AcWing题库
#include<iostream>
using namespace std;
const int N = 1010;
int m, n, q, x1, y1, x2, y2;
int a[N][N], dp[N][N];
int main()
{
scanf("%d%d%d", &n, &m, &q);
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
scanf("%d", &a[i][j]);
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + a[i][j];
}
}
while(q--)
{
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
printf("%d\n", dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1]);
}
return 0;
}5.3 差分
797. 差分 - AcWing题库
差分就是前缀和的逆过程
给定一个原数组a，我们要求差分数组b，使得a数组是b数组的前缀和，即a[i]=b[1]+b[2]+...+b[i]
1. 获得差分数组
很容易就能想到b[i] = a[i] - a[i - 1]
2. 使用差分数组
我们要对给定的区间[l, r]内的每个a数组加上c，按照正常做法，编译a数组的区间[l, r]，每个数加上c，时间复杂度是O(m * n)。
此时就可以使用差分数组了。因为a数组是b数组的前缀和，所以我们会发现对a数组的区间[l, r]每个数加上c，实际上只需要对b[l] += c，b[r + 1] -= c
注意，因为我们对b进行了操作，但没对a操作，所以此时a数组名义上是b数组的前缀和，但是数值上已经不是了，所以m次操作完成后，要重新求一遍a
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
int m, n, l, r, c;
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++) b[i] = a[i] - a[i - 1];
while(m--)
{
scanf("%d %d %d", &l, &r, &c);
b[l] += c;
b[r + 1] -= c;
}
for(int i = 1;i <= n;i++)
{
a[i] = a[i - 1] + b[i];
printf("%d ", a[i]);
}
return 0;
}我们会发现，两步是可以使用同一个函数的。第二步是在a数组的区间[l, r]上插入值c。我们可以把第一步抽象为，假设a数组全为0，那么b数组也全为0，现在需要往a数组的[i, i]区间插入数值a[i]，因为a数组并不是真的全为0，所以此时a数组既是b数组名义上的前缀和，也是数值上的前缀和
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
int m, n, l, r, c;
void insert(int l, int r, int c)
{
b[l] += c;
b[r + 1] -= c;
}
int main()
{
scanf("%d %d", &n, &m);
for(int i = 1;i <= n;i++)
{
scanf("%d", &a[i]);
insert(i, i, a[i]);
}
while(m--)
{
scanf("%d %d %d", &l, &r, &c);
insert(l, r, c);
}
for(int i = 1;i <= n;i++)
{
a[i] = a[i - 1] + b[i];
printf("%d ", a[i]);
}
return 0;
}5.4 差分矩阵
798. 差分矩阵 - AcWing题库
这个就是二维差分，与前面的差分是类似的
#include<iostream>
using namespace std;
const int N = 1010;
int n, m, q, x1, y1, x2, y2, c;
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()
{
scanf("%d %d %d", &n, &m, &q);
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
scanf("%d", &a[i][j]);
insert(i, j, i, j, a[i][j]);
}
}
while(q--)
{
scanf("%d %d %d %d %d", &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++)
{
a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + b[i][j];
printf("%d ", a[i][j]);
}
printf("\n");
}
return 0;
}6、双指针算法
6.1 最长连续不重复的子序列
799. 最长连续不重复子序列 - AcWing题库
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int n;
int a[N], b[N];
int main()
{
scanf("%d", &n);
for(int i = 0;i < n;i++) scanf("%d", &a[i]);
int ans = 0;
for(int i = 0,j = 0;i < n;i++)
{
b[a[i]]++;
while(b[a[i]] > 1)
{
b[a[j]]--;
j++;
}
ans = max(ans, i - j + 1);
}
printf("%d", ans);
return 0;
}6.2 数组元素的目标和
800. 数组元素的目标和 - AcWing题库
#include<iostream>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n, m, x;
ll a[N], b[N];
int main()
{
scanf("%d %d %d", &n, &m, &x);
for(int i = 0;i < n;i++) scanf("%lld", &a[i]);
for(int i = 0;i < m;i++) scanf("%lld", &b[i]);
int i = 0,j = m - 1;
while(i < n && j >= 0)
{
long long sum = a[i] + b[j];
if(sum < x) i++;
else if(sum > x) j--;
else
{
printf("%d %d\n", i, j);
i++, j--;
}
}
return 0;
}6.3 判断子序列
2816. 判断子序列 - AcWing题库
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int a[N], b[N];
int main()
{
scanf("%d %d", &n, &m);
for(int i = 0;i < n;i++) scanf("%d", &a[i]);
for(int i = 0;i < m;i++) scanf("%d", &b[i]);
int j = 0;
for(int i = 0;i < m;i++)
{
if(j >= n) break;
if(a[j] == b[i]) j++;
}
if(j == n) printf("Yes");
else printf("No");
return 0;
}7、位运算
801. 二进制中1的个数 - AcWing题库
位运算中，主要是两种问题
1. n的二进制表示中第k位是几 n >> k & 1，例如n=15，二进制是1010，左边是高位，右边是低位，下标是3210
2. lowbit(x)：返回x的最后一位1，例如x=15，二进制是1010，lowbit(x)=10
lowbit是如何求的呢？x&-x = x&(~x+1)
lowbit可用于统计x的二进制表示中1的个数，每次将x中的一位1减掉，知道x变成0
使用方法一解题：
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int n, a[N], b[N];
int main()
{
scanf("%d", &n);
for(int i = 0;i < n;i++) scanf("%d", &a[i]);
for(int i = 0;i < n;i++)
{
int sum = 0;
for(int k = 0;k <= 31;k++)
if((a[i] >> k & 1) == 1) sum++;
b[i] = sum;
}
for(int i = 0;i < n;i++) printf("%d ", b[i]);
return 0;
}使用方法二解题：
// 方法二
int lowbit(int x)
{
return x & -x;
}
int main()
{
int n;
scanf("%d", &n);
while(n--)
{
int x;
scanf("%d", &x);
int res = 0;
while(x) x -= lowbit(x), res++;
cout<<res<<" ";
}
cout<<endl;
return 0;
}8、离散化
802. 区间和 - AcWing题库
这道题数轴上的数字是[-10^9, 10^9]，一共是2*10^9个数，会进行n次插入和m次查询，每次查询会输入一个区间，n和m最大都是10^5，也就是说最多会用到3*10^5个数，这与2*10^9比起来是十分小的，如果我们要开一个2*10^9的数组，显然有很多空间是会浪费掉的。于是，这道题使用了离散化
因为值域太大，所以将用到的下标映射到从0开始的自然数(从1开始也行),映射的过程就称为离散化
我们先开一个数组，将用到的下标全部放进这个数组中，然后再进行离散化
离散化时要注意两个问题：
（1）用到的下标可能是存在重复的，所以要先去重
（2）如何将下标映射到从0开始的自然数？此时需要用到二分，利用其在存放数组中的下标，一个数映射后的值就是其在数组中的下标
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 300010;
int n, m;
int a[N], s[N]; // a是存离散化后的值的数组，s是存a的前缀和
vector<int> alls; // 存需要离散化的元素，x、l、r需要离散化，去重就是对alls去重
vector<PII> add, query;
// add存要在x位置增加c的键值对
// query存每次询问的左右区间l和r
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;
}这里使用任何一个二分模板均可
9、区间合并
803. 区间合并 - AcWing题库
这道题就是首先将区间全部读入到一个vector<pair<int, int>>中，然后根据区间的左端点对区间进行排序，然后对所有区间进行遍历，遍历过程中将有交集的区间进行合并，合并好的区间放入一个新的数组中
遍历：维护当前区间，遍历后面的区间，看后面区间与当前区间的关系。因为已经按区间左端点进行排序了，所以关系只有3种
#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int, int> PII;
int n;
vector<PII> segs, res; // segs读入所有区间，res存放合并好的区间
void merge(vector<PII>& segs)
{
sort(segs.begin(), segs.end());
int st = -2e9, ed = -2e9; // 最先开始让维护的区间位于最左边，并且第一次更新区间不能放入res
for(int i = 0;i < n;i++)
{
if(ed < segs[i].first)
{
if(i != 0) res.push_back({st, ed});
st = segs[i].first;
ed = segs[i].second;
}
else ed = max(ed, segs[i].second);
}
if(st != -2e9) res.push_back({st, ed});
// 最后还需要将最后维护的区间放入，此时要判断一下，因为有可能segs中没有任何区间
segs = res;
}
int main()
{
cin>>n;
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;
}