计蒜客 - 天上的星星 (二维前缀和)

2023-11-27 02:59

本文主要是介绍计蒜客 - 天上的星星 (二维前缀和),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

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

现在,蒜头君问自己 qq 次,每次他问自己每个矩形区域的星星的亮度和是多少(包含边界上的星星)。

输入格式

第一行输入一个整数 n(1≤n≤50000) 表示星星的数量。

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

接下来一行输入一个整数 q(1≤q≤50000),表示查询的次数。

接下来 qq 行,每行输入四个整数 x1​,y1​,x2​,y2​,其中 (x1​,y1​) 表示查询的矩形的左下角的坐标(x2​,y2​) 表示查询的矩形的右上角的坐标,20000≤x1​≤x2​≤2000, 20000≤y1​≤y2​≤2000。

输出格式

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

样例输入复制

5
5 0 6
7 9 7
8 6 13
9 7 1
3 0 19
4
0 8 7 9
0 0 7 10
2 7 10 9
5 4 7 5

样例输出复制

7
32
8
0

题解:  裸的二维前缀和 (求蓝色区域), 处理处理边界, 下图中的粉色粗线最后查询时不能减去这条线上的 . 

#include <iostream>
#include <cstdio>
using namespace std ;
const int MAX = 5010 ;
int a[MAX][MAX] ;
int main(){int n ;cin >> n ;int xb = 0 ; //int yb = 0 ;for(int i = 1 ;i<=n ;i++ ){int x ,y ,w ;cin >>x >>y >>w ;x++ ;y++ ;xb = max(xb,x) ;yb = max(yb,y);a[x][y]+=w ; // 一个点可能有多个星星}for(int i = 1 ; i<=2001 ; i++ ) {for(int j = 1 ;j<=2001 ; j++ ){a[i][j] +=a[i-1][j] + a[i][j-1] -a[i-1][j-1] ;}}int q ;cin >>q;while(q--){int x1,y1 , x2,y2 ;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);x1++ ;y1++ ;x2++ ;y2++ ;int ans = a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1] ;printf("%d\n",ans);}return 0 ;
}

 

这篇关于计蒜客 - 天上的星星 (二维前缀和)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:https://blog.csdn.net/qq_41661809/article/details/90299072
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/426897

相关文章

正则表达式r前缀使用指南及如何避免常见错误

《正则表达式r前缀使用指南及如何避免常见错误》正则表达式是处理字符串的强大工具,但它常常伴随着转义字符的复杂性,本文将简洁地讲解r的作用、基本原理,以及如何在实际代码中避免常见错误,感兴趣的朋友一... 目录1. 字符串的双重翻译困境2. 为什么需要 r?3. 常见错误和正确用法4. Unicode 转换的

Java如何根据文件名前缀自动分组图片文件

《Java如何根据文件名前缀自动分组图片文件》一大堆文件(比如图片)堆在一个目录下,它们的命名规则遵循一定的格式,混在一起很难管理,所以本文小编就和大家介绍一下如何使用Java根据文件名前缀自动分组图... 目录需求背景分析思路实现代码输出结果知识扩展需求一大堆文件(比如图片)堆在一个目录下,它们的命名规

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

CSS3 最强二维布局系统之Grid 网格布局

《CSS3最强二维布局系统之Grid网格布局》CS3的Grid网格布局是目前最强的二维布局系统,可以同时对列和行进行处理,将网页划分成一个个网格,可以任意组合不同的网格,做出各种各样的布局,本文介... 深入学习 css3 目前最强大的布局系统 Grid 网格布局Grid 网格布局的基本认识Grid 网

poj2576(二维背包)

题意:n个人分成两组,两组人数只差小于1 , 并且体重只差最小 对于人数要求恰好装满,对于体重要求尽量多,一开始没做出来,看了下解题,按照自己的感觉写,然后a了 状态转移方程:dp[i][j] = max(dp[i][j],dp[i-1][j-c[k]]+c[k]);其中i表示人数,j表示背包容量,k表示输入的体重的 代码如下: #include<iostream>#include<

hdu2159(二维背包)

这是我的第一道二维背包题,没想到自己一下子就A了,但是代码写的比较乱,下面的代码是我有重新修改的 状态转移:dp[i][j] = max(dp[i][j], dp[i-1][j-c[z]]+v[z]); 其中dp[i][j]表示,打了i个怪物,消耗j的耐力值,所得到的最大经验值 代码如下: #include<iostream>#include<algorithm>#include<

HDU 2159 二维完全背包

FATE 最近xhd正在玩一款叫做FATE的游戏,为了得到极品装备,xhd在不停的杀怪做任务。久而久之xhd开始对杀怪产生的厌恶感,但又不得不通过杀怪来升完这最后一级。现在的问题是,xhd升掉最后一级还需n的经验值,xhd还留有m的忍耐度,每杀一个怪xhd会得到相应的经验,并减掉相应的忍耐度。当忍耐度降到0或者0以下时,xhd就不会玩这游戏。xhd还说了他最多只杀s只怪。请问他能

计蒜客 Skiing 最长路

In this winter holiday, Bob has a plan for skiing at the mountain resort. This ski resort has MM different ski paths and NN different flags situated at those turning points. The ii-th path from the

计蒜客 Half-consecutive Numbers 暴力打表找规律

The numbers 11, 33, 66, 1010, 1515, 2121, 2828, 3636, 4545 and t_i=\frac{1}{2}i(i+1)t​i​​=​2​​1​​i(i+1), are called half-consecutive. For given NN, find the smallest rr which is no smaller than NN

【LeetCode热题100】前缀和

这篇博客共记录了8道前缀和算法相关的题目,分别是:【模版】前缀和、【模版】二维前缀和、寻找数组的中心下标、除自身以外数组的乘积、和为K的子数组、和可被K整除的子数组、连续数组、矩阵区域和。 #include <iostream>#include <vector>using namespace std;int main() {//1. 读取数据int n = 0, q = 0;ci