首页 > 试题广场 >

牛牛数星星

[编程题]牛牛数星星

热度指数：1708 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

一闪一闪亮晶晶，满天都是小星星，牛牛晚上闲来无聊，便躺在床上数星星。

牛牛把星星图看成一个平面，左上角为原点(坐标为(1, 1))。现在有n颗星星，他给每颗星星都标上坐标(x_i，y_i)，表示这颗星星在第x行，第y列。

现在，牛牛想问你m个问题，给你两个点的坐标(a1, b1)(a2，b2)，表示一个矩形的左上角的点坐标和右下角的点坐标，请问在这个矩形内有多少颗星星（边界上的点也算是矩形内）。

输入描述:

第一行输入一个数字n(1≤n≤100000)，表示星星的颗数。
接下来的n行，每行输入两个数x_i和y_i(1≤x_i，y_i≤1000），表示星星的位置。
然后输入一个数字m(1≤m≤100000), 表示牛牛询问问题的个数。
接下来m行，每行输入四个数字a1，b1，a2，b2(1≤a1＜a2≤1000), (1≤b1＜b2≤1000）
题目保证两颗星星不会存在于同一个位置。

输出描述:

输出一共包含m行，每行表示与之对应的每个问题的答案。

示例1

输入

输出

算法知识视频讲解

Felix&

#include<stdio.h>
int N,T,sum;
int vis[1001][1001];
int main()
{
    scanf("%d",&N);
    for(int i=0;i<N;i++)
    {
        int x,y;scanf("%d%d",&x,&y);
        for(int k=y;k<=1000;k++)
            vis[x][k]++;
    }
    scanf("%d",&T);
    while(T--)
    {
        int a1,a2,b1,b2;
        scanf("%d%d%d%d",&a1,&b1,&a2,&b2);
        sum=0;
        for(int i=a1;i<=a2;i++)
            sum+=(vis[i][b2]-vis[i][b1-1]);
        printf("%d\n",sum);
    }

    return 0;
}

发表于 2018-06-26 11:07:11 回复(7)

求天求地求Offer

//多谢 zhuqin 的答案和Intmain的点拨
import java.util.*;
public class Main{
    public static void main(String[] str){
        Scanner sc=new Scanner(System.in);
        int star[][]=new int[1001][1001];
        int n=sc.nextInt();
        for(int i=0;i<n;i++){
            int x=sc.nextInt();
            int y=sc.nextInt();
            for(int j=y;j<=1000;j++){//表示的是 star[x][y]这个点到这个star[x][0]中包含星星的格式
                star[x][j]++;
            }
        }
        int m=sc.nextInt();
        for(int i=0;i<m;i++){
            int x1=sc.nextInt();
            int y1=sc.nextInt();
            int x2=sc.nextInt();
            int y2=sc.nextInt();
            int sum=0;
            for(int x=x1;x<=x2;x++){
                sum+=star[x][y2]-star[x][y1-1];//起始点为 1.1 不会出现越界
            }
            System.out.println(sum);
        }
    }
}

/*
//用矩阵是AC不了的
import java.util.*;
public class Main{
    public static void main(String[] str){
        Scanner sc=new Scanner(System.in);
        int [][]array=new int[1001][1001];
        int n=sc.nextInt();
        for(int i=0;i<n;i++){
            int x=sc.nextInt();
            int y=sc.nextInt();
            array[x][y]=1;
        }
        for(int i=1;i<array.length;i++){
            for(int j=1;j<array[0].length;j++){
                array[i][j]=array[i][j]+array[i][j-1]+array[i-1][j]-array[i-1][j-1];
            }
        }
        int m=sc.nextInt();
        for(int i=0;i<m;i++){
            int x1=sc.nextInt();
            int y1=sc.nextInt();
            int x2=sc.nextInt();
            int y2=sc.nextInt();
            int num=array[x2][y2]-array[x1-1][y2]-array[x2][y1-1]+array[x1-1][y1-1];
            System.out.println(num);
        }
    }
}
*/

发表于 2018-07-06 22:26:21 回复(1)

zhangbw_

二维前缀和

#include <bits/stdc++.h>

using namespace std;
int arr[1005][1005] = {};

int main() {
    int n, x, y;
    cin >> n;
    while (n--) {
        cin >> x >> y;
        arr[x][y] = 1;
    }
    for (int i = 1; i <= 1000; ++i) {    // 预处理：arr[i][j]: 前i行，前j列矩阵的元素和
        for (int j = 1; j <= 1000; ++j) {
            arr[i][j] = arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1] + arr[i][j];
        }
    }
    int m, a1, b1, a2, b2, cnt;
    cin >> m;
    while (m--) {
        cin >> a1 >> b1 >> a2 >> b2;
        cnt = arr[a2][b2] - arr[a1 - 1][b2] - arr[a2][b1 - 1] + arr[a1 - 1][b1 - 1];
        printf("%d\n", cnt);
    }
    return 0;
}

发表于 2022-08-19 20:43:03 回复(0)

C/C++

愢怡

二维前缀和，大家可以自行百度一下，讲的会更清楚。

#include<iostream>
using namespace std;
const int N = 1005;
int a[N][N];
int flag[N][N];
int ans[100010];
int t;
int main()
{
int n, m, C;
cin >> n;
int x1, y1, x2, y2, x, y;
for (int i = 1; i <= n; i++)
{
cin >> x >> y;
flag[x][y] = 1;
}
for (int i = 1; i < N; i++)
for (int j = 1; j < N; j++)
a[i][j] = a[i][j - 1] + a[i - 1][j] - a[i - 1][j - 1] + flag[i][j];

cin >> m;
for (int i = 1; i <= m; i++)
{
cin >> x1 >> y1 >> x2 >> y2;
C = a[x2][y2] - a[x2][y1-1] - a[x1-1][y2] + a[x1-1][y1-1];
ans[t++] = C;
}
for (int i = 0; i < t; i++)
cout << ans[i] << endl;
}

编辑于 2019-05-17 13:41:19 回复(1)

Java

OFFER死哪去了

好像超时了。。。
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int[][] res = new int[1001][1001];
        while(sc.hasNext()){
            int n = sc.nextInt();
            for(int i=0;i<n;i++){
                int a = sc.nextInt();
                int b = sc.nextInt();
                res[a][b]=1;
            }
            int len = res.length;
            for(int i=1;i<len;i++){
                for(int j=1;j<len;j++){
                    res[i][j]=res[i][j]+res[i-1][j]+res[i][j-1]-res[i-1][j-1];
                }
            }
            int m = sc.nextInt();
            int count=0;
            for(int i=0;i<m;i++){
                int c = sc.nextInt();int d = sc.nextInt();int e = sc.nextInt();int f = sc.nextInt();
                count=res[e][f]-res[c-1][f]-res[e][d-1]+res[c-1][d-1];
                System.out.println(count);
            }
        }
        sc.close();
    }
}

发表于 2018-06-26 20:21:53 回复(2)

擅长CRUD的男人

importjava.util.*;

publicclassMain {

//动态规划

publicstaticvoidmain(String []args){

Scanner sc=newScanner(System.in);

intres[][]=newint[1024][1024]; //构建结果集数组，将res[i][j]的值，看做是B点位于i,j时候，

//能包含多少星星数量

intn=sc.nextInt();

for(inti=0;i<n;i++){ //输入n个点，将n个点对应数组位置置为1

intx=sc.nextInt();

inty=sc.nextInt();

res[x][y]=1;

}

for(inti=2;i<1024;i++){

res[i][1]+=res[i-1][1]; //当B点位于数组的第一列，必定A点也位于第一列，因此根据上一行的值，得到该行值

res[1][i]+=res[1][i-1]; //当B点位于数组的第一行，必定A点也位于第一行，同理

}

for(inti=2;i<1024;i++){

for(intj=2;j<1024;j++){

res[i][j]+=res[i-1][j]-res[i-1][j-1]+res[i][j-1]; //计算B点位于其它位置时候的星星数量

} //注意这里要减去res[i-1][j-1],因为加上res[i-1][j]，res[i][j-1]时候，存在重叠位置，具体自己画图理解

}

intcount=sc.nextInt(); //下面开始根据输入的点A，点B，返回答案

intindex=0;

while(index<count){

intx1=sc.nextInt();

inty1=sc.nextInt();

intx2=sc.nextInt();

inty2=sc.nextInt();

if(x1==1&&y1==1) System.out.println(res[x2][y2]);

else{

System.out.println(res[x2][y2]+res[x1-1][y1-1]-res[x2][y1-1]-res[x1-1][y2]);

}

index++;

}

编辑于 2018-06-24 12:47:57 回复(0)

hello201903261057737



	#include<bits/stdc++.h>
using namespace std;



	int main(){
    int n, m;
    cin>>n;
    int x[n], y[n];
    int sum[1001][1001];
    memset(sum, 0, sizeof(sum));
    int i = 0;
    for(i = 0; i < n; i++){
        cin>>x[i]>>y[i];
        sum[x[i]][y[i]] = 1;
    }
    for(i = 1; i < 1001; i++){
        for(int j = 1; j < 1001; j++){
            sum[i][j] = sum[i][j - 1] + sum[i][j];
        }
    }
    cin>>m;
    while(m--){
        int a1, b1, a2, b2;
        cin>>a1>>b1>>a2>>b2;
        int s = 0;
        for(i = a1; i <= a2; i++){
            s += sum[i][b2] - sum[i][b1 - 1];
        }
        cout<<s<<endl;
    }
    return 0;
}

发表于 2019-07-16 21:24:29 回复(0)

Charms

import java.io.*;

public class Main
{
    static int[][] map=new int[1001][1001];
    public static void main(String[] args)
    {
        try
        {
            BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
            PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
            int n=Integer.parseInt(in.readLine());
            for(int i=0;i<n;i++)
            {
                String[] str=in.readLine().split(" ");
                int row=Integer.parseInt(str[0]);
                int column=Integer.parseInt(str[1]);
                for(int j=column;j<1001;j++) map[row][j]++;
            }
            int m=Integer.parseInt(in.readLine());
            for(int i=0;i<m;i++)
            {
                int sum=0;
                String[] str=in.readLine().split(" ");
                int leftRow=Integer.parseInt(str[0]);
                int leftColumn=Integer.parseInt(str[1]);
                int rightRow=Integer.parseInt(str[2]);
                int rightColumn=Integer.parseInt(str[3]);
                for(int j=leftRow;j<=rightRow;j++)
                {
                    sum+=map[j][rightColumn]-map[j][leftColumn-1];
                }
                out.println(sum);
            }
            out.flush();
            in.close();
            out.close();
        }
        catch(IOException e)
        {
            System.out.println(e.getStackTrace());
        }
    }
}

发表于 2019-05-27 15:08:41 回复(0)

COffer++

个人理解的是每次统计星星个数，记从这点开始到该行的起始点之间出现过几个星星；
最后计算的时候，对每一行进行减法求出这一区间的星星数，然后累加结果。 #include <iostream>
using namespace std;
int star[1001][1001];
int main(){     int n, x, y, i;     cin >> n;         while (n--){         cin >> x >> y;         for (i = y;i < 1001 ;++i){             star[x][i]++;                 }     }     int m;     cin >> m;     while (m--){         int sum = 0;         int a1, b1, a2, b2;         cin >> a1 >> b1 >> a2 >> b2;         for (int i = a1; i <= a2; ++i){             sum +=( star[i][b2] - star[i][b1-1]);         }         cout << sum << endl;     }     return 0;
}

发表于 2019-05-16 11:27:13 回复(0)

为啥要起名字

def main():
    n=int(raw_input().strip())
    if n==0:
        return 
    stars=[[0]*(1001) for i in range(1001)]
    dp=[[0]*(1001) for i in range(1001)]
    for i in range(n):
        x,y=map(int,raw_input().strip().split())
        stars[x][y]=1
    for i in range(1,1001):
        for j in range(1,1001):
            dp[i][j]=dp[i-1][j]+dp[i][j-1]+stars[i][j]-dp[i-1][j-1]
    m=int(raw_input())
    for i in range(m):
        x1,y1,x2,y2=map(int,raw_input().strip().split())
        print(dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1])
if __name__=='__main__':
    main()  您的代码已保存 运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。 case通过率为90.00%

编辑于 2018-07-24 14:46:41 回复(0)

[留线请离言]

#include<bits/stdc++.h>
using namespace std;
int s[1010][1010],ss[1010][1010];
int main()
{
    int n,m,a,b,c,d;
    int i,j,k;
    ios::sync_with_stdio(false);
    while(cin>>n)
    {
        memset(s,0,sizeof s);
        memset(ss,0,sizeof ss);
        for(i=0;i<n;i++)
        {
            cin>>a>>b;
            s[a][b]=1;
        }
        for(i=1;i<1010;i++)
        {
            for(j=1;j<1010;j++)
            {
                ss[i][j]=s[i][j]+ss[i-1][j]+ss[i][j-1]-ss[i-1][j-1];
            }
        }
        /*
        for(i=0;i<10;i++)
        {
            for(j=0;j<10;j++)
            {
                cout<<s[i][j]<<" ";
            }
            cout<<endl;
        }
        for(i=0;i<10;i++)
        {
            for(j=0;j<10;j++)
            {
                cout<<ss[i][j]<<" ";
            }
            cout<<endl;
        }
        */
        cin>>m;
        for(i=0;i<m;i++)
        {
            cin>>a>>b>>c>>d;
            cout<<ss[c][d]+ss[a-1][b-1]-ss[c][b-1]-ss[a-1][d]<<endl;
        }
    }
    return 0;
}

简单的二维前缀和

发表于 2018-06-25 22:10:50 回复(0)

麦垛上的守望者

public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] data = new int[1001][1001];
        for(int i=0;i<n;i++){
            data[in.nextInt()][in.nextInt()] = 1;
        }
        //累加data，data[i][j]表示(i,j)和(1,1)构成的矩形阵列中的星星总数
        for(int i=1;i<data.length;i++){
            for(int j=1;j<data.length;j++){
                data[i][j]+=data[i][j-1]+data[i-1][j]-data[i-1][j-1];
            }
        }

        int m = in.nextInt();
        for(int i=0;i<m;i++){
            int a1 = in.nextInt();
            int b1 = in.nextInt();
            int a2 = in.nextInt();
            int b2 = in.nextInt();
            //分割出来所需的矩形阵列
            int sum=data[a2][b2]-data[a2][b1-1]-data[a1-1][b2]+data[a1-1][b1-1];
            System.out.println(sum);
        }

        in.close();
    }

发表于 2018-06-23 23:36:16 回复(6)