C++:第九讲前缀和与差分

发布时间:2023年12月23日

Everyday English

Your optimal career is simply this: Share the real you with physical world through th e process of creative self-expression.
你的最佳职业很简单,就是这样:通过创造性自我表达的途径和世界分享真实的你。

前言

这节课带你们学习一下怎么优化程序。

前缀和

前缀和是指某序列的前n项和,可以把它理解为数学上的数列的前n项和,而差分可以看成前缀和的逆运算。合理的使用前缀和与差分,可以将某些复杂的问题简单化。

前缀和也指一个数组的某下标之前的所有数组元素的和(包含其自身)。前缀和分为一维前缀和,以及二维前缀和。前缀和是一种重要的预处理,能够降低算法的时间复杂度。可以快速地求出某一段的和。

当然了,前缀和也分为一维前缀和和二维前缀和。

前缀和可以简单理解为「数列的前??项的和」,是一种重要的预处理方式,能大大降低查询的时间复杂度。

C++ 标准库中实现了前缀和函数?,定义于头文件?<numeric>?中。

前缀和的好处

而且前缀和时间复杂度:预处理O(n),查询O(1),效率比较高效,后续也会有一些其他的解法,比如说线段树,树状数组等,前缀和的运行时间是最短的。

洛谷小课堂P1387最大正方形

题目描述

在一个 n*m的只包含 0?和 1?的矩阵里找出一个不包含 0的最大正方形,输出边长。

输入格式:

输入文件第一行为两个整数 n,m(1<=n,m<=100),接下来 $n$ 行,每行 $m$ 个数字,用空格隔开,0?或 1。

输出格式:

一个整数,最大正方形的边长。

样例输入?
4 4
0 1 1 1
1 1 1 0
0 1 1 0
1 1 0 1

?样例输出?
2

c++ AC:

#include <algorithm>
#include <iostream>
using namespace std;
int a[103][103];
int b[103][103];  // 前缀和数组,相当于上文的 sum[]
int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      cin >> a[i][j];
      b[i][j] =
          b[i][j - 1] + b[i - 1][j] - b[i - 1][j - 1] + a[i][j];  // 求前缀和
    }
  }
  int ans = 1;
  int l = 2;
  while (l <= min(n, m)) {  // 判断条件
    for (int i = l; i <= n; i++) {
      for (int j = l; j <= m; j++) {
        if (b[i][j] - b[i - l][j] - b[i][j - l] + b[i - l][j - l] == l * l) {
          ans = max(ans, l);  // 在这里统计答案
        }
      }
    }
    l++;
  }
  cout << ans << endl;
  return 0;
}

python AC:

n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
b = [a[0]] + [[i[0]] + [0] * (m - 1) for i in a[1:]]
ans = 0
for i in range(1, n):
    for j in range(1, m):
        if a[i][j]:
            b[i][j] = min(b[i-1][j], b[i][j-1], b[i-1][j-1]) + 1
            ans = max(ans, b[i][j])
print(ans)

差分

当对某些不确定的区间多次进行加减操作时,如果每次都是对这些区间遍历操作,那么时间复杂度是O(nm)。而如果我们采用差分法来求解,就是先构造一个差分数组,然后转化为对区间端点的操作,这样的话时间复杂度就转化为O(n)。

差分的好处

它可以维护多次对序列的一个区间加上一个数,并在最后询问某一位的数或是多次询问某一位的数。注意修改操作一定要在查询操作之前。

C++ 标准库中实现了差分函数,定义于头文件?<numeric>?中。

注意:

差分法只能用于区间的加减的运算。

洛谷小课堂P3397 地毯

?地毯

题目描述

在 n*n?的格子上有m个地毯。

给出这些地毯的信息,问每个点被多少个地毯覆盖。

输入格式

第一行,两个正整数 n,m。意义如题所述。

接下来 m?行,每行两个坐标 (x_1,y_1)?和 (x_2,y_2),代表一块地毯,左上角是 (x_1,y_1),右下角是 (x_2,y_2)。

?输出格式

输出n行,每行n个正整数。

第i行第i列的正整数表示 (i,j)这个格子被多少个地毯覆盖。

样例输入?
5 3
2 2 3 3
3 3 5 5
1 2 1 4

样例输出 #1
0 1 1 1 0
0 1 1 0 0
0 1 2 1 1
0 0 1 1 1
0 0 1 1 1

提示

样例解释

覆盖第一个地毯后:

00000
01100
01100
00000
00000
思路点拨

差分的主要思想其实就是用O(1)复杂度来表示O(N)的覆盖——用B[I]表示A[I]-A[I-1],所以当覆盖A[L]至A[R]时,只需B[L]++,B[R+1]--即可。最后,再用O(N^2)的复杂度复原A数组,然后输出就行了。

c++AC:

#include<bits/stdc++.h>
using namespace std;
int a[1001][1001],m,n;
int main(){
	cin>>n>>m;
	int b,c,d,e;
	for(int i=1;i<=m;i++){
		cin>>b>>c>>d>>e;
		for(int j=b;j<=d;j++){
			for(int k=c;k<=e;k++){
				a[j][k]++;
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cout<<a[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
}

结尾

本篇文章共2570字,如果你能支持一下我,我十分感谢!!!

如果你喜欢或想了解一下其他的算法,可以看看以下这些:

贪心:

C++:第八讲贪心算法1-CSDN博客

排序:

C++:第七讲冒泡排序-CSDN博客

函数:

C++第6讲max和min函数_c++ min函数-CSDN博客

C++第五讲函数初步-CSDN博客

for循环&数组:

C++第四讲for循环及数组-CSDN博客

if语句&else语句及运算:

C++第三讲:C++中的逻辑运算符及if else语句-CSDN博客

基础:

C++第二讲输入与输出-CSDN博客

C++第一讲认识C++编译器-CSDN博客

最后认识一下,我是爱编程的喷火龙廖,我们有缘再见!

文章来源:https://blog.csdn.net/2301_81328824/article/details/135157348
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。