牛客春招刷题训练营 - 2025.4.18 题解

活动地址：牛客春招刷题训练营 - 编程打卡活动

Easy 小红的正整数计数

简要题意

数区间 内的偶数。

Solution

对偶数长度区间，答案就是长度的一半。

对奇数长度区间，如果左右端点都是奇数，答案就是长度一半的下取整；否则就是上取整。

Code

void R()
{
	int l,r,ans;
	cin>>l>>r;
	ans=r-l+1;
	if ((ans&1)&&(l%2==0)) ans++;
	cout<<ans/2;
	return;
}

Medium 【模板】堆

简要题意

要求实现堆支持的操作。

Solution

堆是一种支持 插入， 弹出， 查询最值的数据结构。

STL 中的 priority_queue 实现了堆的功能。

Code

void R()
{
	int n;
	cin>>n;
	priority_queue<int> q;
	while (n--)
	{
		string op;
		cin>>op;
		if (op=="push")
		{
			int x;
			cin>>x;
			q.push(x);
		}
		else
		{
			if (q.empty()) cout<<"empty\n";
			else
			{
				cout<<q.top()<<'\n';
				if (op=="pop") q.pop();
			}
		}
	}
	return;
}

Hard 【模板】二维差分

简要题意

给定矩阵，进行若干次子矩阵加操作，求最后的矩阵。

Solution

参考前面学习过的差分和二维前缀和，我们把一次区间加拆成二维差分数组上的四个位置的修改，最后做一次二维前缀和即可。

Code

void R()
{
	int n,m;
	cin>>n>>m;
	vector<i64> a(n),b(n+1);
	for (i64 &x:a) cin>>x;
	for (int i=0;i<m;i++)
	{
		int l,r,k;
		cin>>l>>r>>k;
		b[l-1]+=k;
		b[r]-=k;
	}
	partial_sum(b.begin(),b.end(),b.begin());
	for (int i=0;i<n;i++)
		cout<<a[i]+b[i]<<" \n"[i+1==n];
	return;
}