Java教程

练习记录

本文主要是介绍练习记录，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

CF R728 Div2 B

找 \(a_ia_j=i+j\) 的对数，\(a_i\ne a_j,n\leq10^5\)。

排序后枚举，由于 \(a_ia_j\) 会很大但是 \(i+j\) 会很小，所以枚举的效率是高的。

CF R728 Div2 C

已知单源最短路径长，求边权和的最小值。

尽量少安排正权边，多安排负权边，且要满足三角形不等式。

\(d(v)+cost(u,v)\ge d(u)\)

要让 \(cost(u,v)\) 尽量小，显然要取等号。

因此，从小到大排序，正权边连成一条链，每个点 \(i\) 都往前面的点 \(j\) 连一条 \(d(j)-d(i)\) 的边。

这个东西用前缀和瞎维护就ok了。

CF R728 Div2 D

这篇关于练习记录的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航