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

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

Easy 小红的正整数构造

简要题意

求区间 内一个 的倍数或报告无解。

Solution

数据范围极小，枚举判断即可。

Code

void R()
{
	int l,r,x;
	cin>>l>>r>>x;
	for (int i=l;i<=r;i++)
		if (i%x==0)
		{
			cout<<i;
			return;
		}
	cout<<-1;
	return;
}

Medium 数独数组

简要题意

定义数独数组为每相邻 项都构成 排列的数组，判断一个数组能否重排得到数独数组。

Solution

数独数组显然以 为周期，所以 个数分别出现 或 次，判断一下是否满足就好。

Code

void R()
{
	int n;
	cin>>n;
	vector<int> cnt(9),need(9);
	for (int i=0;i<n;i++)
	{
		int x;
		cin>>x;
		cnt[x-1]++;
	}
	sort(cnt.begin(),cnt.end());
	for (int i=0;i<9;i++)
	{
		need[i]=n/(9-i);
		n-=need[i];
	}
	if (cnt==need) cout<<"YES";
	else cout<<"NO";
	return;
}

Hard 【模板】二维前缀和

简要题意

给定矩阵，若干次询问子矩阵和。

Solution

如上图，考虑二维前缀和 就是左上顶点为 ，右下顶点为 的子矩阵和。

则答案为 ，也就是“右下=全-上-左+左上”。

Code

void R()
{
	int n,m,q;
	cin>>n>>m>>q;
	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];
	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];
	for (int i=0;i<q;i++)
	{
		int x,y,z,w;
		cin>>x>>y>>z>>w;
		cout<<a[z][w]-a[x-1][w]-a[z][y-1]+a[x-1][y-1]<<'\n';
	}
	return;
}