三角形计数

角形计数"/>

三角形计数

三角形计数

题目描述

    快码佳编四兄弟姐妹来到了明代，这天他们看到一个很有学术风范的老者在地上画着东西，一打听，原来是
著名的数学家徐光启。徐光启在数学方面的最大贡献当推《几何原本》(前6卷)翻译。徐光启提出了实用的“度数
之学“的思想，同时还撰写了《勾股义》和《测量异同》两书。他们看到徐先生在地上画着好多三角形。把大三角形的每条边n等分，将对应的等分点连接起来（连接线分别平行于三条边），这样一共会有多少三
角形呢？编程来解决这个问题

输入

 第一行为整数t(≤100)，表示测试数据组数；接下来t行，每行一个正整数n(≤500)。

输出

 对于每个n，输出一个正整数，表示三角形个数

样例输入

3
1
2
3

样例输出

1
5
13

题解：

这道题一眼望去就觉得是一道要找规律的题，所以直接暴力打表，表如下

 

  1        |         2         |        3         |        4        |         5          |       6         |        7        |         8        |         9

——————————————————————————————————————————————

  1        |         5         |        13       |       27       |       48         |      78        |      118       |       170       |      235

 

通过分析表我们看不出什么，那么我们看他们的差，4，8，14，21，30，40，52，65，觉得有些规律，再做差，4，6，7，9，10，12，13，感觉快出来了，再做差，2，1，2，1，2，1，好，规律找出来了我们可预先计算出最后一组数组，在从后往前推，直至推到初始数列即可，再在询问时O(1)输出即可；时间：0ms。

源代码：

#include<bits/stdc++.h>
using namespace std;
long long a1[600],a2[600],a3[600],a4[600],t,n;
int main(){memset(a1,0,sizeof(a1));memset(a2,0,sizeof(a2));memset(a3,0,sizeof(a3));memset(a4,0,sizeof(a4));a3[1]=a2[1]=4,a4[1]=1;for(int i=1;i<=499;i+=2) a1[i]=2,a1[i+1]=1;for(int i=2;i<=500;i++) a2[i]=a2[i-1]+a1[i-1];for(int i=2;i<=500;i++) a3[i]=a3[i-1]+a2[i-1];for(int i=2;i<=500;i++) a4[i]=a4[i-1]+a3[i-1];scanf("%lld",&t);while(t--){scanf("%lld",&n);printf("%lld\n",a4[n]);}return 0;
}

AC