当前位置:首页 > 动态规划 > 2018 蓝桥杯省赛 B 组模拟赛(一) 天上的星星-计蒜客

2018 蓝桥杯省赛 B 组模拟赛(一) 天上的星星-计蒜客

https://nanti.jisuanke.com/t/20689

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

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

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

输入格式

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

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

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

接下来 q 行,每行输入四个整数 x_1, y_1, x_2, y_2,其中 (x_1, y_1) 表示查询的矩形的左下角的坐标,(x_2, y_2) 表示查询的矩形的右上角的坐标,0 \le x_1 \le x_2 \le 20000 \le y_1 \le y_2 \le 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

dp[i][j]表示从原点到x=i  y=j 的矩形内所包含的和

#include <stdio.h>
#include <algorithm>
using namespace std;
long long dp[2005][2005];
struct p{
    int x,y,w;
}val[50005];

bool cmp(p a,p b){
    if(a.y!=b.y) return a.y<b.y;
    return a.x<b.x;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d %d %d",&val[i].x,&val[i].y,&val[i].w);
        val[i].x++;
        val[i].y++;
    }
    sort(val,val+n,cmp);
    int t=0;
    for(int j=1;j<=2002;j++){
        for(int i=1;i<=2002;i++){
            while(t<n&&val[t].x<=i&&val[t].y<=j){
                dp[i][j]+=val[t].w;
                t++;
            }
            dp[i][j]+=dp[i-1][j];
            dp[i][j]+=dp[i][j-1];
            dp[i][j]-=dp[i-1][j-1];
        }
    }
    int k,x1,y1,x2,y2;
    scanf("%d",&k);
    while(k--){
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
        x1++;y1++;x2++;y2++;
        printf("%lld\n",dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]);
    }
    return 0;
}


除特别注明外,本站所有文章均为whppmy原创,转载请注明出处来自http://www.dengwenhuo.cn/?id=464

发表评论

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。