洛谷:B3994:周长与面积计算


洛谷:B3994:周长与面积计算

题目

B3994:周长与面积计算

分析

本题难度正如题目所称,是标准的GESP 2级难度,不涉及循环、分支、数组的综合应用,但对基本操作有要求。

首先是分析图形,最终可以得到:

  • 面积:就是边长1, 2, 3, 4, ..., n的各个正方形的面积的和
  • 周长:虽然初看很不规律,但可以得到:\(c=\sum_{i=1}^{n} i \times 2 + n \times 2\)

有了这两个公式,配合循环就可以得到结果:

long long c = 2 * n;
long long s = 0;

for (int i = 1; i <= n; i++)
{
    c += 1ll * 2 * i;
    s += 1ll * i * i;
}

根据题意,n最大可以到100,000(十万,\(10^5\)),虽然上面的代码中没有明确表明,但我们知道,面积(i * i)最大会是\(10^5\times 10^5 = 10^{10}\),已经超出int的范围,周长也一样,因为\(\sum_{i=1}^{n} i=\frac{n(n+1)}{2}\),还是在\(10^{10}\)这个量级。所以结果应该用long long表示。

另外,看上面代码中的累加过程,我们用了1ll * 2 * i这样的形式,将累加的数值强制转换到了long long。如果直接写成2 * i,临时表达式可能溢出,就会出错。

答案

Solution

思考

闭式公式与校验

面积可直接用公式:\(S=\sum_{i=1}^{n} i^2=\frac{n(n+1)(2n+1)}{6}\);周长本题推导为:\(C=2n+\sum_{i=1}^{n}2i=2n+n(n+1)=n(n+3)\);利用闭式公式可以在提交前交叉校验循环结果,确保无误。

性能与实现取舍

循环实现是O(n),闭式公式是O(1)。在竞赛环境,优先用闭式(更快、无误差),但要注意中间计算也需long long。这也是GESP 2级一个重要考点:善于用公式一步求结果

Previous Next