首页 > > 程序设计 > C/C++ >

Luogu P2807 三角形计数

2018-06-17 22:06:10来源：未知阅读 ()

题目背景

三角形计数(triangle) 递推

题目描述

把大三角形的每条边n等分，将对应的等分点连接起来（连接线分别平行于三条边），这样一共会有多少三角形呢？编程来解决这个问题。

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

1
5
13

说明

n(≤500)

t(≤100)

题解：

不妨设正 △ABC 的边长为 n ，首先考虑“头朝上”的三角形，即平行于水平线的那条边在其对角顶点下方的三角形。
边长为 1 的“头朝上”的三角形有

边长为 2 的“头朝上”的三角形有

边长为 n 的“头朝上”的三角形只有 1 个。
从而得出，“头朝上”的三角形共有

然后考虑“头朝下”的三角形，即平行于水平线的那条边在其对角顶点上方的三角形。
边长为1的“头朝下”的三角形有

边长为2的“头朝下”的三角形有

边长为m的“头朝下”的三角形有

故当 n 为奇数时，“头朝下”的三角形有

当n为偶数时，“头朝下”的三角形有

综上所述，一共产生的三角形的个数为

#include <iostream>
#include <cstdio>
using namespace std;
int t , n , ans[501];
int main()
{
    scanf ( "%d", &t );
    for ( int i = 1 ; i <= t ; i++ )
    {
        scanf ( "%d", &n );
        if ( n % 2 == 1 )
        ans[i] = ( n + 1 ) * ( 2 * n * n + 3 * n - 1 ) / 8;
        else
        ans[i] = n * ( n + 2 ) * ( 2 * n + 1 ) / 8;
    }
    for ( int i = 1 ; i <= t ; i++ )
    cout << ans[i] << endl;
    return 0;
}

　　作者：xuxing