蓝桥杯2022省A题C-创新互联
题目链接:https://www.luogu.com.cn/problem/P8772
目前创新互联建站已为1000多家的企业提供了网站建设、域名、网站空间、网站托管运营、企业网站设计、屏边网站维护等服务,公司将坚持客户导向、应用为本的策略,正道将秉承"和谐、参与、激情"的文化,与客户和合作伙伴齐心协力一起成长,共同发展。我是在洛谷里做到这题的。
因为刚接触算法在练习前缀和,我直接再洛谷上搜索了关于前缀和的题看到这个题。
由于我一开始就知道这题要用前缀和做,所以我做起来就不难了,关键是怎么找到里面运用了前缀和的地方。
题目只给了一个式子,我们首先看不到任何破解之法,就可以带入特定的值,就像题中的案例带入的是4,将4带入后写出完整的式子是
s = a1*a2 + a1*a3 + a1*a4
+ a2*a3 + a2* a4
+a3*a4
将公因式提取出来就是
s = a1*(a2 + a3 + a4)
+ a2*(a3 + a4)
+a3*a4
可以看到括号内就是一个前缀和的形式,这样就和前缀和联系起来了。
但是说实话,我还是不清楚怎么一看到题目就知道要运用到前缀和,如果有网友知道的话可以在评论区告知一声吗?提前说声谢谢啦。
我用的是java写的,代码如下
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n + 10];
long[] s = new long[n + 10];
long sum = 0;
for(int i = 1; i<= n; i++){
a[i] = sc.nextInt();
s[i] = s[i - 1] + a[i];
}
for(int i = 1; i<= n; i++){
sum += a[i] * (s[n] - s[i]);
}
System.out.println(sum);
}
}
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
网站题目:蓝桥杯2022省A题C-创新互联
转载注明:http://scyanting.com/article/csohhh.html