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

2022/8/15 6:25:22

本文主要是介绍[总结]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模拟赛的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程