本文主要是介绍[总结]2022-8-13模拟赛，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

[总结]2022-8-13模拟赛

P1 赛时情况

T1感觉好像很简单，但只会50分的暴力。

T2想到了建图，然后对于环的情况似乎很难处理（前两天刚学的拓扑排序就忘了） ，于是打了41分的不带环的情况。

T3、T4准备xjb搞。

结果T1的暴力打了将近两个小时（主要是细节没处理好，只好重构代码）。

T2草草打完过了自出数据和样例。

T3不知道怎么乱搞。

T4 1分暴力结果没有 mod2。

T2的捆绑烦死了，1分没拿。

最后考T1的50分，rank15。

P2 赛后总结

T1没有想着进一步优化，而且没有分类讨论。

T2贪心应该是错的，要往DP方面想想。

T3估计要比T2容易得分（主要是没捆绑），但T1花的时间太多了，所以没有打。

T4审题错误，1分丢掉。

P3 题目解法

T1

考虑如何把 \(O(n^2) \to O(n)\)。

首先枚举一个晴天中心 \(i\) ，显然当前的贡献是 \(\sum (d-(i-j-1))^2 \cdot s_j+ \sum (d-(j-i))^2 \cdot s_j\)。前面的部分是第 \(i\) 个点前面的区间，后面的是后面的区间。

以前面的为例，考虑化简。

\[\begin {aligned} (d-(i-j-1))^2 \cdot s_j &=(d-i+j+1)^2 \cdot s_j \\ &=((d-i+1)+j)^2 \cdot s_j \\ &=s_j \cdot (d-i+1)^2 + s_j \cdot 2j \cdot (d-i+1)+s_j \cdot j^2 \end {aligned} \]

于是前面的部分成了

\[\sum s_j \cdot (d-i+1)^2 + s_j \cdot 2j \cdot (d-i+1)+s_j \cdot j^2. \]

对于枚举的 \(i\) ，已知的 \(d\) ，已经确定了 \((d-i+1)\) 。而且只考虑当前的枚举出来的 \(i\) ，那么可以用分配律。也就是说，式子进一步变形。

\[(d-i+1)^2 \cdot \sum s_j+ (d-i+1) \cdot \sum s_j \cdot 2j+ \sum s_j+j^2. \]

那么就是三个前缀和了。

对于后面的部分，同理可得。

这篇关于[总结]2022-8-13模拟赛的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！