B3735 题解

残阳如血 · 2023-09-27 19:57:05 · 题解

思路分析

分解问题

简单的一个找规律的题目。

我们可以将整个圣诞树的连边分为两类：从上往下连接和最后一排横向连接的绳子。

其中从上往下连接的定义时：1,2,\cdots,n-1 层的每个星星都向下一层最近的两个星星连的绳子。

接下来我们可以对其分别计数，最后两部分求和即可。

从上往下连接

声明：在这部分中，我们定义第 i\,(1\le i\le n-1) 层的绳子数为第 i 层连接第 i+1 层的绳子数量。

运用大眼观察法，可以发现第 i 层的绳子数为 2\times i，所以可以得出这部分的每层的绳子数构成一个等差数列，为 2,4,6,\cdots,2\times(n-1)。 根据等差数列求和公式，上数列的所有数之和即为 \dfrac{[\,2+2\times(n-1)\,]\times(n-1)}{2}=n\times(n+1)。

最后一排横向连接

很容易发现，这一部分的绳子数即为 n-1。

合并问题

将两部分的值相加，得 n\times(n-1)+(n-1)=(n-1)\times(n+1)。这就是最终的答案了。由于 n\le10^3，所以 (n-1)\times(n+1)\le999999，无需开 long long。

代码演示

#include <iostream>

int main() {
    int n; std::cin >> n;
    std::cout << (n + 1) * (n - 1); // 根据公式直接计算
    return 0;
}