专栏文章

题解：P11871 张灯结彩

eew3www
P11871题解参与者 3已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@mipyutxa
此快照首次捕获于
2025/12/03 20:11
3 个月前
此快照最后确认于
2025/12/03 20:11
3 个月前
查看原文
这是蒟蒻的第一篇题解……

P11871 张灯结彩 题解

原题戳这里

题目分析

本题为一道较简单的数学题，只要找到了规律就可以 A 掉本题。（其实就是一道小学找规律题……）
其实，题目所给的示意图就已经几乎告诉了我们规律……
仔细观察这张图片，可以发现如下规律：
  1. 只要不是底部的彩灯，一定会有三根线与下面最相邻的三个彩灯相连。
  2. 底部的彩灯之间各有两条线与与它相邻的两个彩灯相连（边缘的彩灯除外）。
因为第 ii 行有 2i−12i-1 个彩灯，所以前 n−1n-1 行彩灯的总数为
1+3+5+⋯+(2×n−1)1+3+5+\cdots+(2 \times n-1)
接着，由于恒等式
1+3+5+⋯+(2×n−1)=n21+3+5+\cdots+(2 \times n-1)=n^2
可以得到前 n−1n-1 行彩灯的总数为 (n−1)2(n-1)^2。
所以，可以发现：
  • 上面 n−1n-1 行的电线总数为 3×(n−1)23\times(n-1)^2。
  • 最下面一行的电线总数为 n−1n-1。
因此，电线的总数就为
3×(n−1)2+n−13\times(n-1)^2+n-1

Code

CPP
#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

修复了一处公式错误。

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...