蓝桥杯 2018 H 天上的星星

2024-02-29 23:30

文章标签 蓝桥 2018 星星天上

本文主要是介绍蓝桥杯 2018 H 天上的星星，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在一个星光摧残的夜晚，蒜头君一颗一颗的数这天上的星星。

蒜头君给在天上巧妙的画了一个直角坐标系，让所有的星星都分布在第一象。天上有 $n$ 颗星星，他能知道每一颗星星的坐标和亮度。

现在，蒜头君问自己 $q$ 次，每次他问自己每个矩形区域的星星的亮度和是多少（包含边界上的星星）。

输入格式

第一行输入一个整数 $\le n \le 50000)$ 表示星星的数量。

接下里 $n$ 行，每行输入三个整数 $\le x, y, w\le 2000)$ ，表示在坐标 $(x, y)$ 有一颗亮度为 $w$ 的星星。注意一个点可能有多个星星。

接下来一行输入一个整数 $\le q \le 50000)$ ，表示查询的次数。

接下来 $q$ 行，每行输入四个整数 $x_1, y_1, x_2, y_2$ ，其中 $x_1, y_1)$ 表示查询的矩形的左下角的坐标， $x_2, y_2)$ 表示查询的矩形的右上角的坐标， $\le x_1 \le x_2 \le 2000$ ， $\le y_1 \le y_2 \le 2000$ 。

输出格式

对于每一次查询，输出一行一个整数，表示查询的矩形区域内的星星的亮度总和。

样例输入

样例输出

解题思路：对已有信息进行处理用 a[i][j] 表示从左下角（0，0）到右上角（i，j）所有星星的总亮度。

用 a[i][j]+=a[i][j-1]+a[i-1][j]-a[i-1][j-1];

当右下角坐标的值不同做出不一样的处理看代码很好理解。^^

#include<stdio.h>
#include<string.h>
int a[2005][2005];
int n,x,y,w,x2,y2;
int main()
{while(~scanf("%d",&n)){memset(a,0,sizeof(a));for(int i=0;i<n;i++){scanf("%d%d%d",&x,&y,&w);a[x][y]+=w;}for(int i=1;i<=2000;i++){a[i][0]+=a[i-1][0];a[0][i]+=a[0][i-1];}for(int i=1;i<=2000;i++){for(int j=1;j<=2000;j++){a[i][j]+=a[i][j-1]+a[i-1][j]-a[i-1][j-1];//printf("%d ",a[i][j]);}//printf("\n");}int q;scanf("%d",&q);while(q--){scanf("%d%d%d%d",&x,&y,&x2,&y2);if(x>0&&y>0)printf("%d\n",a[x2][y2]-a[x-1][y2]-a[x2][y-1]+a[x-1][y-1]);else if(x==0&&y>0){printf("%d\n",a[x2][y2]-a[x2][y-1]);}else if(x>0&&y==0){printf("%d\n",a[x2][y2]-a[x-1][y2]);}else{printf("%d\n",a[x2][y2]);}}}return 0;
}

这篇关于蓝桥杯 2018 H 天上的星星的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！