侦察兵

　

侦察兵

侦察兵

题目

mxy 沉迷于一个辣鸡游戏不可自拔。

游戏地图是一个 n*n 的矩形，在每个单位格子上有一个数字，代表当前位置的生命体

个数，作为一个侦察兵，mxy 的任务是计算出她所在位置的左上角和右下角的总人数（不包括她所在的行列）。

注意作为一个侦察兵，mxy 是不包括在地图上的生命体个数中的。

输入

第一行 2 个整数 n 和 t。（1≤n≤1000，1≤t≤1000）

接下来 n 行，每行 n 个整数表示每个单位格子上的生命体个数 a。（1≤a≤100）

再下来 t 行，每行两个整数 xi，yi，表示不同时刻 mxy 在地图上的位置。

输出

T 行，每行一个整数，表示当前时刻 mxy 所在位置的左上角和右下角的总人数。

输入样例

4 1
0 1 2 0
3 2 0 0
1 2 3 2
0 0 0 10
3 3

输出样例

16

思路

这道题其实就是一道模拟题，但是要用到前缀和。

我这里用了快读快输，但是其实不用，不过本人懒得删。

代码

#include<cstdio>
using namespace std;
int n,t,f[1001][1001],x,y;
int read()//快读
{
	int te=0;
	char c;
	c=getchar();
	while (c>='0'&&c<='9')
	{
		te=te*10+c-48;
		c=getchar();
	}
	return te;
}
void write(int ans)//快输
{
	if (ans>9) write(ans/10);
	putchar(ans%10+48);
}
int main()
{
	n=read();t=read();//读入
	for (register int i=1;i<=n;++i)
	for (register int j=1;j<=n;++j)
	{
		x=read();//读入
		f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+x;//求前缀和
	}
	for (register int hhd=1;hhd<=t;++hhd)
	{
		x=read();y=read();//读入
		write(f[x-1][y-1]+f[n][n]-f[x][n]-f[n][y]+f[x][y]);//输出
		putchar('\n');//输出
	}
	return 0;
}

相关阅读