每周学习计划
2026-10-11 10:31:25
发布于：北京
81阅读
0回复
0点赞
唉，我觉得 99% 文章是完成不了的，没完成也别喷了。
Week 1（10.7-10.11）
topic: 前缀和与差分，最短路算法（一） review
前缀和，差分；二维前缀和，二维差分；链式前向星，Floyd，Dijkstra
P8772
思路
将其做整理，得到 。
然后利用前缀和和差分计算即可。
代码
# a1(a_2+a_3+a_4+...a_n)+a2(a_3+...+a_n)+a3(a_4+...a_n)+...an-1(a_n)
n = int(input())
a = list(map(int,input().split()))
s = [a[0]]
for i in range(1,n):
s.append(s[i-1]+a[i])
ans = 0
for i in range(n-1):
ans += a[i] * (s[n-1] - s[i])
print(ans)
Floyd 算法
欸原来我没学过吗。。
有啥难的，轻松水过。一定要记得考虑重边。
@爆米花先生🍿 by bike：
P1359
， 的 Floyd 直接就能水过去。
n = int(input())
dist = [[int(1e18) for yhzakioi in range(n)] for yhzakioj in range(n)]
for i in range(n):
dist[i][i] = 0
#next = [[int(-1) for yhzakioi in range(n)] for yhzakioj in range(n)]
for i in range(n - 1):
a = list(map(int,input().split()))
for j in range(n - i - 1):
dist[i][i + 1 + j] = a[j]
for k in range(n):
for i in range(n):
if dist[i][k] == int(1e18):
continue
for j in range(n):
if dist[k][j] == int(1e18):
continue
if dist[i][j] > dist[i][k] + dist[k][j]:
dist[i][j] = dist[i][k] + dist[k][j]
#next[i][j] = next[i][k]
print(dist[0][n-1])
有帮助，赞一个