B4157 [厦门小学生 C++ 2023] 数据核心

题目背景

本试题为 2023 年厦门市小学生 C++ 语言复赛试题，数据为洛谷自造。

初赛为笔试。

题目描述

Sora 有一块神奇的数据核心，这块数据核心里有 $n\times m$ 个数据块，这些数据块组成了一个 $n\times m$ 的矩阵。

在数据核心中，每个数据块都有一个强度 $a_{i,j}$，代表这个数据块存在数据核心中时会提供多少的运算力。但是随着时间的推移，数据核心中有一些数据块出现了硬件老化，有些数据块的强度是一个负数，继续保留过多的老化数据块会影响数据核心的使用效率，所以 Sora 决定从原本的数据核心的矩阵中，先确定一个数据块作为新数据核心的左上角，其位置为 $(x,y)$ ，向右下方切割出一块数据核心（子矩阵），以保证其使用效率。

但是 Sora 是一个有着天马行空想象力的科学家，她想知道在确定了新的数据核心左上角的数据块的情况下，其位置为 $(x,y)$，新的数据核心（子矩阵）能够获得的最大运算力是多少。

当然她的问题很多，有 $Q$ 次询问，每次询问都会给出一个位置 $(x,y)$，你需要算出以这个位置为左上角的新数据核心对应的最大运算力。

输入格式

第一行两个整数 $n,m$，表示原始数据核心的大小。

接下来 $n$ 行，每行 $m$ 个整数，对应的是每个数据块的强度 $a_{i,j}$。

第 $n+2$ 行一个整数 $Q$，表示询问次数。
接下来 $Q$ 行，每行两个整数 $x,y$，表示新数据核心的左上角数据块在原数据核心中位于第 $x$ 行第 $y$ 列。

输出格式

输出 $Q$ 行，每行一个整数，表示对应询问的最大运算力。

输入输出样例 #1

输入 #1

5 5
1 -1 1 -1 1
2 2 2 -1 2
1 1 2 -1 -1
-1 -1 2 2 1
1 1 1 1 -1
6
1 1
2 2
3 3
2 4
5 1
5 5

输出 #1

16
12
7
2
4
-1

说明/提示

样例解释

• 第一个询问对应的新数据核心是 $(1,1)$ 到 $(5,5)$。
• 第二个询问对应的新数据核心是 $(2,2)$ 到 $(5,5)$。
• 第三个询问对应的新数据核心是 $(3,3)$ 到 $(5,4)$。
• 第四个询问对应的新数据核心是 $(5,1)$ 到 $(5,4)$。
• 第五个询问对应的新数据核心是 $(5,5)$ 到 $(5,5)$。

数据范围

• 对于 $20\%$ 的数据，$n\times m\le 500$，$Q\le 500$，$|a_{i,j}|\le 10^5$。
• 对于 $50\%$ 的数据，$n\times m\le 5000$，$Q\le 5000$，$|a_{i,j}|\le 10^5$。
• 对于 $80\%$ 的数据，$n\times m\le 10000$，$Q\le 10000$，$|a_{i,j}|\le 10^5$。
• 对于 $100\%$ 的数据，$n\times m\le 100000$，$Q\le 100000$，$|a_{i,j}|\le 10^9$。

C++实现

#include <bits/stdc++.h>
using namespace std;
#define int long long
unordered_map<int,int> a[100005],qzh[100005],anss[100005];
int n,m,Q,x,y;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	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++)
			qzh[i][j]=qzh[i-1][j]+qzh[i][j-1]-qzh[i-1][j-1]+a[i][j];
	cin>>Q;
	while(Q--){
		int ans=-1e18;
		cin>>x>>y;
		if(anss[x][y]){
			cout<<anss[x][y]<<'\n';
			continue;
		}
		for(int i = x;i<=n;i++){
			for(int j = y;j<=m;j++){
				ans=max(ans,qzh[i][j]-qzh[x-1][j]-qzh[i][y-1]+qzh[x-1][y-1]);
			}
		}
		cout<<ans<<'\n';
		anss[x][y]=ans;
	}
	return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容