acwing week2 基础算法3总结

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;
}

热门相关:甜妻动人,霸道总裁好情深   宝贝轻轻:总裁的独家宠爱   全系灵师:魔帝嗜宠兽神妃   惊世第一妃   甜妻动人,霸道总裁好情深