2018 蓝桥杯省赛 B 组模拟赛（一）I. 天上的星星

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

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

蒜头君给在天上巧妙的画了一个直角坐标系，让所有的星星都分布在第一象。天上有 $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$ 。

输出格式

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

样例输入

样例输出

因为数据范围很小，利用前缀和可推理到空间和，令dp[i][j]表示（1,1），（1，j），（i，1），（i，j）四个点之间星星亮度的总和，那么（x1,y1）和（x2,y2）之间星星亮度的总和就是dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1],（因为坐标线上也可能存在星星，所以需要考虑一下边界），具体请看代码。

#include <stdio.h>
#include <string.h>
int dp[2005][2005];
int main() {int n;int x, y, w;int q;int x1, y1, x2, y2;int mx = 2005;memset(dp, 0, sizeof(dp));scanf("%d", &n);while(n--) {scanf("%d %d %d", &x, &y, &w);dp[x+1][y+1] += w;  //因为星星可以重复，即亮度可以叠加 }for(int i = 1; i < mx; i++) {for(int j = 1; j < mx; j++) {dp[i][j] += dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];//注意边界 }}scanf("%d", &q);while(q--) {scanf("%d %d %d %d", &x1, &y1, &x2, &y2);int ans = dp[x2+1][y2+1] - dp[x2+1][y1] - dp[x1][y2+1] + dp[x1][y1];//注意边界 printf("%d\n", ans);}return 0;
}

这篇关于2018 蓝桥杯省赛 B 组模拟赛（一）I. 天上的星星的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！