题解：P3016 [USACO11FEB] The Triangle S

furina_yyds · 2025-01-15 21:03:33 · 题解

思路

一道模拟题。

先考虑枚举三角形的顶点，然后枚举三角形的边长，计算三角形中每一层数的和。直接模拟会 T 掉，怎么办呢？

这里每一层数的和可以预处理其前缀和，在后续枚举中 O(1) 得到。总的时间复杂度也就是 O(n^2k)，一旦发现枚举的三角形超出了三角形的边界就可以直接结束枚举边长的循环，这样也能干掉不少不满足题意的。

这题真的是黄题吗？

代码

#include <iostream>
#include <vector>

// 定义一个函数来比较并更新最大值
template<typename T>
void updateMax(T& maxVal, const T& newVal) {
    if (newVal > maxVal) {
        maxVal = newVal;
    }
}

int main() {
    int n, d;
    std::cin >> n >> d;

    // 使用 vector 存储二维数组，避免固定大小的数组
    std::vector<std::vector<long long>> a(n + 1, std::vector<long long>(n + 1, 0));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            std::cin >> a[i][j];
        }
    }

    long long ans = -1e15;

    // 遍历二维数组
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            long long res = 0;
            long long num = 0;

            // 向右下方向计算
            for (int k = 1; k <= (2 * d); ++k) {
                int tx = i + k - 1;
                int ty = j + k - 1;
                if (tx > n || ty > tx) break;
                // 计算当前子区域的元素和
                for (int m = j; m <= ty; ++m) {
                    res += a[tx][m];
                    num++;
                }
                if (k >= d) {
                    updateMax(ans, res / num);
                }
            }

            res = 0;
            num = 0;

            // 向左上方向计算
            for (int k = 1; k <= (2 * d); ++k) {
                int tx = i - k + 1;
                int ty = j - k + 1;
                if (tx < 1 || ty < 1 || j > tx) break;
                // 计算当前子区域的元素和
                for (int m = ty; m <= j; ++m) {
                    res += a[tx][m];
                    num++;
                }
                if (k >= d) {
                    updateMax(ans, res / num);
                }
            }
        }
    }
    std::cout << ans << std::endl;
    return 0;
}