自动搬运

查看原文

来自洛谷，原作者为

	ew3www homework不可数说明了什么

搬运于2025-08-24 23:10:59，当前版本为作者最后更新于2025-03-09 20:33:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这是蒟蒻的第一篇题解……

P11871 张灯结彩 题解

原题戳这里

题目分析

本题为一道较简单的数学题，只要找到了规律就可以 A 掉本题。（其实就是一道小学找规律题……）

其实，题目所给的示意图就已经几乎告诉了我们规律……

仔细观察这张图片，可以发现如下规律：

1. 只要不是底部的彩灯，一定会有三根线与下面最相邻的三个彩灯相连。
2. 底部的彩灯之间各有两条线与与它相邻的两个彩灯相连（边缘的彩灯除外）。

因为第 $i$ 行有 $2i-1$ 个彩灯，所以前 $n-1$ 行彩灯的总数为

接着，由于恒等式

可以得到前 $n-1$ 行彩灯的总数为 $(n-1)^2$。

所以，可以发现：

• 上面 $n-1$ 行的电线总数为 $3\times(n-1)^2$。
• 最下面一行的电线总数为 $n-1$。

因此，电线的总数就为

Code

#include <bits/stdc++.h>
using namespace std;

int t, n;

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        long long ans = (n - 1) * (n - 1) * 3 + n * 2 - 2;
        //我之所以不用 pow() 函数，是因为臭名昭著的浮点数精度问题会影响到答案……
        printf("%lld\n", ans);
    }
    return 0;
}

AC 记录

求管理员大大给过！

UPD 2025/4/16

修复了一处公式错误。