acwing week2 基础算法3总结
总结点1：双指针算法
//常用模版框架
for (int i = 0, j = 0; i < n; i ++ )
{
while (j < i && check(i, j)) j ++ ;
}
常见问题分类：
(1) 对于一个序列，用两个指针维护一段区间
(2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作
题1：最长连续不重复子序列
我们用指针i指向子序列的终点，j指向子序列的起点。
每次指针i后移时，这个序列中重复的那个数只可能是s[i],所以我们判断一下s[i]出现的次数是否大于1，
如果大于1，说明子序列中s[i]这个数重复了，那么就更新答案和起点，继续循环。
判断出现的次数，我们用数组a做标记。
代码：
#include <iostream>
using namespace std;
int n;
const int N = 100010;
int s[N], a[N];
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> s[i];
}
int ans = 0;
for (int i = 0, j = 0; i < n; i++)//i指向终点，j指向起点
{
a[s[i]]++;//新加值的次数+1；
while (j < i && a[s[i]]>1)//如果重复(a[s[i]]>1) 就更新起点，直到a[s[i]] == 1;
{
a[s[j]]--;//删除数的次数--
j++;//起点指针后移
}
ans = max(ans, i - j + 1);//更新答案
}
cout << ans << endl;
return 0;
}
题2,3都是双指针算法，不做讲解，直接看代码
题2：
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
int n, m, x;
const int N = 100010;
int a[N], b[N];
int main()
{
cin >> n >> m >> x;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
for (int i = 0; i < m; i++)
{
cin >> b[i];
}
for (int i = 0, j = m - 1; i < n; i++)
{
while (a[i] + b[j] > x)
{
j--;
}
if (a[i] + b[j] == x)
{
cout << i << ' ' << j << endl;
break;
}
}
return 0;
}
题3:
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
int n, m;
const int N = 100010;
int a[N], b[N];
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
for (int i = 0; i < m; i++)
{
cin >> b[i];
}
int ans = 0;
for (int i = 0, j = 0; i < n&&j<m; i++)
{
while (a[i] != b[j])
{
j++;
if (j == m)
{
j--;
break;
}
}
if(a[i] ==b[j])ans++,j++;
}
if (ans == n) cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}
总结点2：离散化
离散化的题乍一看感觉和前缀和和差分很像，但是在数据的范围上有很大的区别。
一般离散化数据的跨度非常大，但是真正使用的数据点的个数比较少，而前缀和和差分，一般数据的跨度是多少，使用的数据点的个数就是多少。
题1：区间和
这道题原本是前缀和和差分的例题，但是修改了l,r的范围，这时继续使用前缀和就会超时，那么我们就需要使用离散化。
首先我们将所有用到的点输入到alls数组中，然后对alls数组进行排序，然后去重。
这时我们可以将alls数组看作是一个数轴，左右使用的坐标，都按次序排好了。
这时我们将alls数组中坐标的对应的下标作为他的这个坐标对应的新坐标，然后将每个坐标下的数字，按照新坐标的次序输入到a[]数组中。
这时我们想求原坐标下A-B的区间和，可以转换为新坐标下As-Bs的和；
因为新坐标的范围比较小，此时就可以用前缀和和差分左进一步处理。
代码：
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 300010;
int n, m;
vector<int> alls;
vector<pair<int, int >> 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 l + 1;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
{
int x, c;
cin >> x >> c;
add.push_back({ x, c });
//x是需要用到的坐标
alls.push_back(x);
}
for (int i = 0; i < m; i++)
{
int x, c;
cin >> x >> c;
query.push_back({ x,c });
alls.push_back(x);
alls.push_back(c);
}
//对alls数组进行排序并去重
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
//将原坐标对应的数据，储存到新坐标中
for (int i = 0; i < n; i++)
{
int x = find(add[i].first);
a[x] += add[i].second;
}
//前缀和模版
for (int i = 1; i <= alls.size(); i++)
{
s[i] = s[i - 1] + a[i];
}
for (int i = 0; i < m; i++)
{
int l = find(query[i].first), r = find(query[i].second);
cout << s[r] - s[l - 1] << endl;
}
return 0;
}
总结点3：区间合并
题1：区间合并
情况1：
对于这种情况，两个区间不需要合并。
情况2：
这种情况下，合并后的区间就是长的区间。
情况3：
这种情况合并后，区间是上面区间的左端点，和下面区间的右端点。
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
using namespace std;
int n;
vector<pair<int, int>> segs;//用segs去储存初始时的各个区间
void merge(vector<pair<int, int>> &segs)//注意对segs加&,因为需要修改segs的值
{
vector<pair<int, int>> res;//创建数组，储存新区间
sort(segs.begin(), segs.end());//先将原区间按照左端点排序
int l = -2e9, r = -2e9;//分别控制新区间的左右端点
for (auto seg : segs)
{
if (seg.first > r)//第一种情况
{
if (l != -2e9) res.push_back({l,r});//如果不是初始值，就将区间放入新数组
l = seg.first, r = seg.second;//更新左右端点
}
else//第二三种情况
{
r = max(r, seg.second);
}
}
if (l != -2e9) res.push_back({ l,r });//放入最后一个区间
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;
}