C++知识点总结(9):前缀和

2023-12-16 21:55:03

一、前缀和

1. 意义

数列1520305065
下标12345
前缀和153565115180

2. 表示

前缀和:用数组表示,因为每一项的前缀和都能算出来。

3. 公式

前缀和数组
a [ 1 ] a[1] a[1] s [ 1 ] s[1] s[1]
s [ 1 ] + a [ 2 ] s[1]+a[2] s[1]+a[2] s [ 2 ] s[2] s[2]
s [ 2 ] + a [ 3 ] s[2]+a[3] s[2]+a[3] s [ 3 ] s[3] s[3]
. . . ... ... . . . ... ...
s [ i ? 1 ] + a [ i ] s[i-1]+a[i] s[i?1]+a[i] s [ i ] s[i] s[i]

4. 程序

#include <iostream>
using namespace std;

int main()
{
	int n; // 项数 
	int a[100005] = {}; // 数组 
	int s[100005] = {}; // 前缀和数组 
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		s[i] = s[i-1] + a[i]; // 求前缀和公式,存入数组 
	}
	
	int m; // m个求前缀和的数据
	int r;
	cin >> m;
	for (int i = 1; i <= m; i++)
	{
		cin >> r; // 输入前r项 
		cout << s[r] << endl;
	}
	return 0;
}

简化前思想时间复杂度 O ( n 2 ) O(n^2) O(n2) ,简化后时间复杂度 O ( n ) O(n) O(n)

二、区间和

1. 小节一下

知识点公式
前缀和 s u m = s [ r ? 1 ] + a [ i ] sum =s[r-1] + a[i] sum=s[r?1]+a[i]
区间和 s u m = s [ r ] ? s [ l ? 1 ] sum = s[r] - s[l-1] sum=s[r]?s[l?1]

2. 程序

#include <iostream>
using namespace std;

int main()
{
	int n; // 项数 
	int a[100005] = {}; // 数组 
	int s[100005] = {}; // 前缀和数组 
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		s[i] = s[i-1] + a[i]; // 求前缀和公式,存入数组 
	}
	
	int m; // m个求前缀和的数据
	int l, r; // l~r区间范围 
	cin >> m;
	for (int i = 1; i <= m; i++)
	{
		cin >> l >> r; // 输入区间l和r 
		cout << s[r] - s[l-1] << endl; // 区间和公式,直接输出 
	}
	return 0;
}

三、喧闹的会议

1. 审题

一共有 N N N 个席位,并视作一条直线,并且每个位置上的人都会和剩下的 N ? 1 N-1 N?1 个位置上的所有人对线,第 A A A 个位置的人和第 B B B 个位置的人之间需要 ∣ A ? B ∣ |A-B| A?B 的音量才可以沟通。求总音量。

2. 思路

下表省略了 a b s abs abs

12345
1-11-21-31-41-5
2-12-22-32-42-5
3-13-23-33-43-5
4-14-24-34-44-5
5-15-25-35-45-5

注意:

∣ x ? y ∣ = ∣ y ? x ∣ |x-y| = |y-x| x?y=y?x ,所以只用求下半部分。
而且,绝对值也可以去除了!

3. 优化

步骤公式
举例 ( 5 ? 1 ) + ( 5 ? 2 ) + ( 5 ? 3 ) + ( 5 ? 4 ) + ( 5 ? 5 ) (5-1) + (5-2) + (5-3) + (5-4) + (5-5) (5?1)+(5?2)+(5?3)+(5?4)+(5?5)
相当于 s [ 5 ] = 5 × 5 ? s [ 5 ] s[5] = 5 \times 5 - s[5] s[5]=5×5?s[5]
行和公式 r o w s u m = i × a [ i ] ? s [ i ] rowsum = i \times a[i] - s[i] rowsum=i×a[i]?s[i]

4. 程序

#include <iostream>
using namespace std;

int main()
{
	int n; // 项数 
	long long a[100005] = {}; // 数组 
	long long s[100005] = {}; // 前缀和数组 
	long long sum = 0; // 会议总音量 
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		s[i] = s[i-1] + a[i]; // 求前缀和公式,存入数组 
		
		// 计算每人音量和
		sum += (i * a[i] - s[i]);
	}
	cout << sum * 2;
	return 0;
}

四、被 m m m 整除的最长区间

1. 同余定理

序号等式
1 x ÷ a = . . . b x \div a = _ ... b x÷a=.?..b
2 y ÷ a = . . . b y \div a = _ ... b y÷a=.?..b
3 ( x ? y ) ÷ a = . . . 0 (x-y) \div a = _ ... 0 (x?y)÷a=.?..0

2. 审题

【题目描述】

给定一个正整数序列 A A A ,其中包含 N N N 个正整数,现请你找到在序列 A A A 中存在的某一区间,使得该区间的区间和能够被 M M M 整除,求出满足能够被 M M M 整除的最长区间长度。若不存在则输出 0 0 0

【输入描述】

共两行,第一行包含 2 2 2 个正整数 N N N M M M ,代表有 N N N 个正整数以及除数M。

【输出描述】

一行,满足条件的最长区间长度。

【输入样例】

10 5
3 4 6 6 2 14 10 15 16 7

【输出样例】

9

【提示】

1 < = N < = 50000 , 1 < = M < = 100 1 <= N <= 50000, 1 <= M <= 100 1<=N<=50000,1<=M<=100

3. 思路

前缀和属于区间和,是一个特殊的区间和,范围也就是 1 1 1 n n n

数组34662141015167
下标12345678910
前缀和371319213545607683
余数3234100013
下标12345678910

我们可以增加一个 p r [ ] pr[] pr[] 数组,表示每个余数第一次出现的位置。

pr[1] = 5;

如上,表示余数 1 1 1 第一次出现的位置在下标 5 5 5 的位置。
那么,得出了公式:

pr[r[i]] = i; // 桶的思想

晕了的童鞋,请看下面程序的注释。

4. 顺着代码捋

#include <iostream>
using namespace std;

int main()
{
	int n; // 项数 
	int m; // 除数 
	int a[50005] = {}; // 数组 
	int s[50005] = {}; // 前缀和数组 
	int r[50005] = {}; // 余数数组 
	int pr[50005] = {}; // 每个余数第一次出现的位置 
	int ans = 0; 
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		s[i] = s[i-1] + a[i]; // 求前缀和 
		r[i] = s[i] % m; // 得到余数 
		
		if (r[i] == 0)
		{
			ans = max(ans, i); // 更行结果 
		}
		else
		{
			if (pr[r[i]] == 0) // 说明位置仍然为空 
			{
				pr[r[i]] = i; // 存储下标 
			}
			else
			{
				ans = max(ans, i - pr[r[i]]); 
			}
		}
	}
	
	cout << ans;
	return 0;
}

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