(标签-蓝桥杯|关键词-stream)

Question

蓝桥杯2109统计子矩阵我的通过率只有70%（哭哭

```c++
#include <iostream>
using namespace std;
int arr[501][501];
int k, n, m;
int sum[501][501] = { 0 };
long long num=0;
int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int x = 1; x <= n; x++) {
        for (int y = 1; y <= m; y++) {
            scanf("%d", &arr[x][y]);
            sum[x][y] = sum[x - 1][y] + sum[x][y - 1] - sum[x - 1][y - 1] + arr[x][y];
        }
    }
    for (int x1 = 1; x1 <= n; x1++) {
        for (int x2 = x1; x2 <= n; x2++) {
            int y1 = 1;
            int y2 = 1;
            for (; y1 <= m; y1++) {
                while (y2<=m&&(sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1])<= k) {
                    y2++;

                }
                
                num += (y2 - y1);
                
            }
        }
    }
    printf("%d", num);
    return 0;
}

Answer 1

让【道友老李】来帮你解答，本回答参考gpt编写，并整理提供，如果还有疑问可以点击头像关注私信或评论。

如果答案让您满意，请采纳、关注，非常感谢！

这道题目是统计子矩阵中满足和小于等于k的子矩阵个数。你的代码逻辑是正确的，但是在累加num的时候用的是+=，应该改成+=。另外，可能是因为数据量较大导致运行时间较长，可以考虑优化算法。 这里给出一个代码示例：

#include <iostream>
using namespace std;
int arr[501][501];
int k, n, m;
int sum[501][501] = { 0 };
long long num = 0;
int main() {
    scanf("%d%d%d", &n, &m, &k);
    
    for (int x = 1; x <= n; x++) {
        for (int y = 1; y <= m; y++) {
            scanf("%d", &arr[x][y]);
            sum[x][y] = sum[x - 1][y] + sum[x][y - 1] - sum[x - 1][y - 1] + arr[x][y];
        }
    }
    
    for (int x1 = 1; x1 <= n; x1++) {
        for (int x2 = x1; x2 <= n; x2++) {
            int y1 = 1;
            int y2 = 1;
            for (; y1 <= m; y1++) {
                while (y2 <= m && (sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1]) <= k) {
                    y2++;
                }
                num += (y2 - y1);
            }
        }
    }
    
    printf("%lld", num);
    
    return 0;
}

希望对你有帮助。如果还有问题，请继续问哦。