2021.10.18 模拟赛总结

裂开。。。

T1

求逆元见 https://www.cnblogs.com/lytql/p/15021752.html

然后我们考虑期望的线性性,求出每一个点都期望答案的贡献。

一个点被选中的概率其实只和第一个点\(A_1\)和当前点\(A_x\)有关,和其它的\(A\)无关。

2021.10.18 模拟赛总结


T2

前30分随便做。

50:

发现填的数肯定单调不上升。那么之后和当前数相同的点不会产生逆序对其它都会产生。

于是我们把问题转化为:

已知:

\[\sum_{i-1}^{k}x_i=n \]

求以下式子的最大值:

\[\sum_{i=1}^ka_i(n-a_i) \]

显然这个式子可以化简:

\[=\sum_{i=1}^ka_in+a_i^2 \]

\[=n\sum a_i-\sum a_i^2 \]

\[=n^2-\sum a_i^2 \]

那么我们肯定让\(a_i\)平均分配,答案最大。

70:暴力dp

2021.10.18 模拟赛总结

100:发现这个式子可以斜率优化。优化就完了

上一篇:Ka波段卫星通信终端市场现状及未来发展趋势


下一篇:408算法练习——排列序列(回溯法)