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

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

Easy 藻类植物

简要题意

对数列 ，有 ，给定首项与 ，求后十项。

Solution

按题意递推即可。

Code

void R()
{
	int r,d,x;
	cin>>r>>d>>x;
	for (int i=0;i<10;i++)
	{
		x=r*x-d;
		cout<<x<<'\n';
	}
	return;
}

Medium 小红的蛋糕切割

简要题意

给一个正整数构成的矩阵，找一个子方阵，使得子方阵内的数之和与子方阵外的数之和绝对差尽量小，求这个最小绝对差。

Solution

设全矩阵的数字和为 ，子方阵的数字和为 ，即最小化 。

枚举子方阵左上角， 随子方阵边长单调递增，二分出 最接近 的位置贡献即可。

Code

void R()
{
	int n,m;
	cin>>n>>m;
	vector<vector<i64>> a(n+1,vector<i64>(m+1));
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
		{
			cin>>a[i][j];
			a[i][j]+=a[i-1][j];
		}
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			a[i][j]+=a[i][j-1];

	auto S=[&](int xl,int yl,int xr,int yr)->i64
	{
		return a[xr][yr]+a[xl][yl]-a[xl][yr]-a[xr][yl];
	};

	i64 ans=1e18;
	for (int i=0;i<n;i++)
		for (int j=0;j<m;j++)
		{
			int l=1,r=min(n-i,m-j);
			while (l<r)
			{
				int mid=(l+r)/2;
				if (S(i,j,i+mid,j+mid)*2<a[n][m])
					l=mid+1;
				else r=mid;
			}
			ans=min(ans,abs(S(i,j,i+l,j+l)*2-a[n][m]));
			if (l>1) l--;
			ans=min(ans,abs(S(i,j,i+l,j+l)*2-a[n][m]));
		}
	cout<<ans;
	return;
}

Hard 【模板】整数域三分

简要题意

给一个由 个平移后的绝对值函数之和构成的函数 ，求 在 上的最小值。

Solution

凹函数求和是保凹性的，而 不会出现最值左右斜率均为 的情况，可以整数三分求最值。

Code

void R()
{
	int n,l,r;
	cin>>n>>l>>r;
	vector<array<i64,3>> f(n);
	for (auto &[k,a,b]:f)
		cin>>k>>a>>b;

	auto chk=[&](i64 x)->i64
	{
		i64 res=0;
		for (auto [k,a,b]:f)
			res+=abs(k*x+a)+b;
		return res;
	};

	while (l<r)
	{
		int d=(r-l)/3,lm=l+d,rm=r-d;
		if (chk(lm)>=chk(rm)) l=lm+1;
		else r=rm-1;
	}
	cout<<chk(l)<<'\n';
	return;
}