【题集】一维前缀和-二维前缀和-数星星问题-反复运行时如何降低时间复杂度

目录

1前缀和

1.1一维前缀和

1.2二维前缀和

2.题目

2.1输入描述:

2.2输出描述:

2.3输入

2.4输出

3.题目理解

3.1思路

4.程序

4.1运行结果

1前缀和

1.1一维前缀和

1.2二维前缀和

求D=（A+B+C+D）-(A+B)-(A+C)+A

D=a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1]

a[][]这里代表的是二维前缀和

for(int i=1;i<=n;i++){

for(int j=1;j<=m;j++)

a[i][j]+=a[i][j-1]+a[i-1][j]-a[i-1][j-1];

}

假如我想求a[2][4]的前缀和，我得先加上a[1][4]的前缀和，再加上a[2][3]的前缀和，然后这个时候我们发现实际上a[1][3]这个部分我们加了两遍，所以我们需要再减去一遍a[1][3]，于是得出公式a[i][j]+=a[i][j-1]+a[i-1][j]-a[i-1][j-1]。

2.题目

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

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

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

2.1输入描述:

第一行输入一个数字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） 题目保证两颗星星不会存在于同一个位置。

2.2输出描述:

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

2.3输入

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 4 2 2

3.题目理解

刚开始读题目的时候，我还以为是

但是阅读示例后，发现 并不是这个样子！

这个棋盘等于说是有空格地方，不是满的，我们需要对其进行统计

3.1思路

该怎么做这道题？

看了示例数据

第一行输入一个数字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）

题目保证两颗星星不会存在于同一个位置。

4.程序

#include

using namespace std;

int const N = 1000;

int a[N][N];

int flag[N][N];

int ans[100010];

int t;

int main()

{

int n, m, C;

cout << "请您输入n的值：\n";

cin >> n;

int x1, y1, x2, y2, x, y;

for (int i = 1; i <= n; i++)

{

cout << "请输入x,y的值（示例 ： 5 3）" << endl;

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];

}

}

cout << "请输入m的值：" << endl;

cin >> m;

for (int i = 1; i <= m; i++)

{

cout << "请输入x1,y1,x2,y2的值（示例：1 1 3 3）：" << endl;

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;

}

return 0;

}

4.1运行结果

参考：

前缀和、二维前缀和与差分的小总结 （讲的不错）

二维前缀和详解

数据结构

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。