ARC071B题解

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

题面

题意：
有 \(n\) 条横线段分别为 \(x=x_i\) ， \(m\) 条纵线段分别为 \(y=y_i\) ，求他们围成的所有矩形的面积和。

首先，我们定义 \(dx_{i,j}\) 为第 \(i\) 条横线段与第 \(j\) 条横线段之间的距离，\(dy_{i,j}\) 为第 \(i\) 条纵线段与第 \(j\) 条纵线段之间的距离。
则答案为 \(\sum_{1\leq i<j\leq n} \sum_{1\leq k<l\leq m} dx_{i,j}\times dy_{k,l}\) 。
那么通过一些因式分解我们可以把答案变为 \(\sum_{1\leq i<j\leq n}dx_{i,j} \times \sum_{1\leq k<l\leq m} dy_{k,l}\) 。
然后去考虑每一条 \(x_i\to x_{i+1}\) 的边的贡献。通过小学知识可知他对答案的贡献是 \(i\times(n-i)\) 。
这样就可以算出来 \(\sum_{1\leq i<j\leq n}dx_{i,j}=\sum_{1\leq i< n}dx_{i,i+1}\times i\times(n-i)\) 。
所以答案就是 \((\sum_{1\leq i< n}dx_{i,i+1}\times i\times(n-i))\times(\sum_{1\leq i< m}dy_{i,i+1}\times i\times(m-i))\) 。左右两边分别 \(O(n)\) 计算即可。

代码

这篇关于ARC071B题解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！