题解：P11871 张灯结彩

· · 题解

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

P11871 张灯结彩 题解

原题戳这里

题目分析

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

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

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

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

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

1+3+5+\cdots+(2 \times n-1)

接着，由于恒等式

1+3+5+\cdots+(2 \times n-1)=n^2

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

所以，可以发现：

因此，电线的总数就为

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

修复了一处公式错误。