警钟长鸣
查看原帖
警钟长鸣
1199153
Nahia楼主2024/4/6 20:04

看看我的教训吧,不要再走我的老路了 我一看到这道题:哇!这么简单!然后用暴力来写

for(int i=1;i<=n;i++){
	for(int j=i+1;j<=n;j++){
		s+=a[i]*a[j];
	}
}

恭喜我,获得30分!
照这样计算,时间复杂度就是o(n2n^2)
最坏结果是(2×105)×(2×105)(2\times10^5)\times(2\times10^5)也就是4×101⁡04\times 10^1 ⁡^0!
必定超时!

所以我换了一个思路,用前缀和来写,但是我没开long long,所以这样了

千万记住这句话

“十年OI一场空,不开long long见祖宗。”

尽量都开long long,不会对内存有多大影响(毕竟这道题的内存限制是128MB)

2024/4/6 20:04
加载中...