洛谷P1111 修复公路P8783统计子矩阵

P1111 修复公路

题目背景

A 地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。

 题目描述

给出 A 地区的村庄数 $N$，和公路数 $M$，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）。

输入格式

第 1 行两个正整数 N,M。

下面 M 行，每行 3 个正整数 x,y,t，告诉你这条公路连着 x,y 两个村庄，在时间t时能修复完成这条公路。

 输出格式

如果全部公路修复完毕仍然存在两个村庄无法通车，则输出 -1，否则输出最早什么时候任意两个村庄能够通车。

分析

这道题考察的是并查集,俩村是否有修好路就是看这两村是否在同一个集合里,即根结点是否相同

在这里可以先把路按修路时间排序在进行判断两个村子有没有通车即有没有相同结点

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
 
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
 
    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            if self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            elif self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1
            return True
        return False
 
def earliestAllConnected(N, M, roads):
    dsu = DSU(N)
    roads.sort(key=lambda x: x[2])  # 按修复时间排序
    latestTime = 0
    connectedComponents = N
 
    for x, y, t in roads:
        if dsu.union(x - 1, y - 1):
            latestTime = max(latestTime, t)
            connectedComponents -= 1
            if connectedComponents == 1:  # 所有村庄都连接起来了
                return latestTime
 
    if connectedComponents > 1:
        return -1  # 仍然存在无法通车的村庄
    return latestTime
 
# 从标准输入读取数据
N, M = map(int, input().split())
roads = [tuple(map(int, input().split())) for _ in range(M)]
 
# 输出结果
print(earliestAllConnected(N, M, roads))

P8783 统计子矩阵

 题目描述

给定一个 N * M 的矩阵 A，请你统计有多少个子矩阵 (最小 1 *1, 最大 N *M) 满足子矩阵中所有数的和不超过给定的整数 K。

 输入格式

第一行包含三个整数 N, M 和 K。

之后 N 行每行包含 M 个整数, 代表矩阵 A。

输出格式

一个整数代表答案。

分析

这一题首先要把前缀矩阵和求出,这样才能求出子矩阵和

前缀矩阵和:    s[i][j] = a[i][j] + s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1];

原始矩阵a:
1  2  3  4
5  6  7  8
9  10 11 12
13 14 15 16
 
前缀和矩阵S:
1   3   6   10
6   14  24  36
15  33  54  78
28  60  96  136

现在，我们想计算从(2,2)到(3,3)的子矩阵的和。根据前缀和矩阵，我们可以这样计算：

• 整个矩形(1,1)到(3,3)的和：S[3][3] = 54
• 左边矩形(1,1)到(3,1)的和：S[3][1] = 15
• 上面矩形(1,1)到(1,3)的和：S[1][3] = 6
• 左上角重叠部分(1,1)的和：S[1][1] = 1

而子矩阵和=大矩阵和-左边矩阵和-上边矩阵+(左边矩阵与上边矩阵重和部分)

所以，从(2,2)到(3,3)的子矩阵的和是：54 - 15 - 6 + 1 = 34，这正好是6+7+10+11的和。

#include <stdio.h>
 
const int MAXN = 507;
int a[MAXN][MAXN];
int s[MAXN][MAXN];
 
int main() {
    int n, m, k;
    long long ans = 0; // 用于存储最终的答案
    scanf_s("%d%d%d", &n, &m, &k); // 输入n, m, k
 
    // 输入矩阵并计算前缀和
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            scanf_s("%d", &a[i][j]);
            // 计算前缀和
            s[i][j] = a[i][j] + s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1];
        }
    }
 
    // 枚举所有可能的子矩阵，并统计满足条件的子矩阵数量
    for (int i = 1; i <= n; ++i) {
        for (int j = i; j <= n; ++j) {
            for (int l = 1, r = 1; r <= m; ++r) {
                // 调整左边界l，使得子矩阵的和不超过k
                while (l <= r && s[j][r] - s[j][l - 1] - s[i - 1][r] + s[i - 1][l - 1] > k) {
                    ++l;
                }
                // 统计数量
                ans += (r - l + 1);
            }
        }
    }
 
    // 输出结果
    printf("%lld\n", ans);
    return 0;
}