三角形计数(Counting Triangles) 题解

思路分析

设边长 $n$ 等分时的三角形总数为 $f(n)$。当从 $n-1$ 层在底部新增第 $n$ 层时：以新底边为底的正立三角形新增 $1 + 2 + \dots + n = \frac{n(n+1)}{2}$ 个；顶点落在底边上的倒立三角形新增 $\lfloor \frac{n^2}{4} \rfloor$ 个。因此递推式为 $f(n) = f(n - 1) + \frac{n(n + 1)}{2} + \lfloor \frac{n^2}{4} \rfloor$（也可直接用通项公式 $\lfloor \frac{n(n + 2)(2n + 1)}{8} \rfloor$）。预处理 $f(1..500)$ 后每次询问 $O(1)$ 输出。

参考代码

#include <iostream>
using namespace std;

long long f[505];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    for (long long n = 1; n <= 500; ++n)
    {
        f[n] = f[n - 1] + n * (n + 1) / 2 + (n * n) / 4;
    }
    int t;
    if (!(cin >> t)) return 0;
    while (t--)
    {
        int n;
        cin >> n;
        cout << f[n] << "\n";
    }
    return 0;
}