UDP广播协议叫吃饭

用户名：Mustenaka

访问量：149506

签　名：

个人博客www.mustenaka.cn

等　　级
排　　名	13
经　　验	25377
参赛次数	8
文章发表	197
年　　龄	3
在职情况	学生
学　　校	Sky_box
专　　业	NE

　　自我简介：

欢迎光临我的博客www.mustenaka.cn，Python，C#，U3D，C/C++开发合作可以找我

TA的其他文章

C语言训练-计算t=1+1/2+1/3+...+1/n （C++代码）
浏览：740

C语言训练-邮票组合问题* （C++代码）其实只需要结果输出19就可以了
浏览：464

蓝桥杯算法提高VIP-删除数组中的0元素（C++代码）正经の描述
浏览：442

你可能喜欢

A+B for Input-Output Practice (I) （C++代码）

C语言程序设计教程（第三版）课后习题10.7 （C++代码）（都说了scanf和gets一般不要混着用）

2664: 蓝桥杯2022年第十三届省赛真题-求和

　　作者: UDP广播协议叫吃饭　　　　发表时间：2022-09-05 11:22:46 浏览：679　|　评论：0　

原题链接：蓝桥杯2022年第十三届省赛真题-求和

# 解题思路
拿部分分思维：直接按照规矩，两两相乘再相加：
````cpp
#include<bits/stdc++.h>

using namespace std;

const int maxn = 200005;

int n;
int arr[maxn];

long long result = 0;

int main() {
	// 给数据io加速
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

// 输入数据
	cin>>n;
	for(int i = 0; i < n; i++) {
		cin>>arr[i];
	}

// 计算数据
	for(int i = 0; i < n; i++) {
		for(int j = i+1; j< n; j++) {
			result += (arr[i]*arr[j]);
		}
	}

// 输出结果 
	cout<<result<<endl;
}
````

在计算数据中直接粗暴相乘并且相加，很显然时间复杂度过高，O(n^2)，导致只能拿下30%的分数。
## 改进方法
观察公式：
result = a1*a2 + a1*a3 + a1*a4 + a2*a3 + a2*a4 + a3*a4
对每一项可以提取公因式变为：
result = a1*(a2+a3+a4) + a2*(a3+a4) + a3*(a4)
可以发现规律为：每一项乘与该项右侧的余项相加，于是可以想到用记忆化的思维存储右边的部分，时间复杂度变为O(n)，通过一个数组mem存储，并且逆向记忆从an到an+an-1+......+a1的过程;

```cpp
#include<bits/stdc++.h>

using namespace std;

const int maxn = 200005;

int n;
long long arr[maxn];

long long result;
long long mem[maxn];

int main() {
	// 给数据io加速
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

// 初始化数据
	memset(arr, 0, sizeof(arr));
	memset(mem, 0, sizeof(mem));
	result = 0;

// 输入数据
	cin>>n;
	for(int i = 1; i <= n; i++) {
		cin>>arr[i];
	}

// 倒序-记忆化存储(a1+a2+a3...+an)
	mem[n] = arr[n];
	for(int i = n-1; i >= 0; i--) {
		mem[i] = arr[i] + mem[i+1];
	}

for(int i = 1; i <= n-1; i++) {
		result += (arr[i] * mem[i+1]);
	}

// 输出结果
	cout<<result<<endl;
}
```
特别注意：第11行请使用long，只用int会炸。

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

UDP广播协议叫吃饭

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.7 （C++代码）

C语言程序设计教程（第三版）课后习题6.7 （C++代码）

A+B for Input-Output Practice (I) （C++代码）

产生数（C++代码）（大数乘法也是可以避免的么hhhh）

C语言程序设计教程（第三版）课后习题10.7 （C++代码）（都说了scanf和gets一般不要混着用）

2664: 蓝桥杯2022年第十三届省赛真题-求和

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）scanf后面加个getchar（），收掉回车符，就可以用gets了

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

震宇大神的杀毒软件（C++代码）

C语言程序设计教程（第三版）课后习题8.9 （Java代码）

printf基础练习2 （C语言代码）

循环入门练习6 （C语言代码）

Hello, world! （C语言代码）

杨辉三角（C语言代码）

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

UDP广播协议叫吃饭

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.7 （C++代码）

C语言程序设计教程（第三版）课后习题6.7 （C++代码）

A+B for Input-Output Practice (I) （C++代码）

产生数 （C++代码）（大数乘法也是可以避免的么hhhh）

C语言程序设计教程（第三版）课后习题10.7 （C++代码）（都说了scanf和gets一般不要混着用）

2664: 蓝桥杯2022年第十三届省赛真题-求和

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）scanf后面加个getchar（），收掉回车符，就可以用gets了

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

震宇大神的杀毒软件 （C++代码）

C语言程序设计教程（第三版）课后习题8.9 （Java代码）

printf基础练习2 （C语言代码）

循环入门练习6 （C语言代码）

Hello, world! （C语言代码）

杨辉三角 （C语言代码）

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

产生数（C++代码）（大数乘法也是可以避免的么hhhh）

　　评论区

震宇大神的杀毒软件（C++代码）

杨辉三角（C语言代码）