一闪一闪亮晶晶,满天都是小星星,牛牛晚上闲来无聊,便躺在床上数星星。
牛牛把星星图看成一个平面,左上角为原点(坐标为(1, 1))。现在有n颗星星,他给每颗星星都标上坐标(xi,yi),表示这颗星星在第x行,第y列。
现在,牛牛想问你m个问题,给你两个点的坐标(a1, b1)(a2,b2),表示一个矩形的左上角的点坐标和右下角的点坐标,请问在这个矩形内有多少颗星星(边界上的点也算是矩形内)。
第一行输入一个数字n(1≤n≤100000),表示星星的颗数。
接下来的n行,每行输入两个数xi和yi(1≤xi,yi≤1000),表示星星的位置。
然后输入一个数字m(1≤m≤100000), 表示牛牛询问问题的个数。
接下来m行,每行输入四个数字a1,b1,a2,b2(1≤a1<a2≤1000), (1≤b1<b2≤1000)
题目保证两颗星星不会存在于同一个位置。
输出一共包含m行,每行表示与之对应的每个问题的答案。
4 1 1 2 2 3 3 1 3 4 1 1 2 2 1 1 3 3 2 2 3 3 1 2 2 3
2 4 2 2
//多谢 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); } } } */
#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; }
二维前缀和,大家可以自行百度一下,讲的会更清楚。#include<iostream>
好像超时了。。。 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(); } }
}
#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;
}
个人理解的是每次统计星星个数,记从这点开始到该行的起始点之间出现过几个星星; 最后计算的时候,对每一行进行减法求出这一区间的星星数,然后累加结果。 #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; }
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%
#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; }简单的二维前缀和