国土分割 (Land Division)
推销我的洛谷博客。
题意
给定一个 \(n \times m\) 的矩阵 \(a\)，你需要选择在横向或纵向分割至少一次，使得每个分割出来的小矩阵的 \(a_{i,j}\) 之和相等。
数据范围
- \(1 \leqslant n,m \leqslant 50\)。
- \(1 \leqslant a_{i, j} \leqslant 10^5\)。
思路
闲话
老师给我们复现了一下，场切了，心路历程如下。
第一眼：好像有些难度啊。
第二眼：\(1\leqslant n,m \leqslant 50\)，这不是水题吗。
第三眼：欸如果 \(a_{i,j}=0\) 怎么办。
第四眼：哦 \(a_{i,j} \geqslant 1\)，那没事了。
正题
看起来挺吓唬人，但数据范围太小，所以考虑枚举。
枚举最左上角的小矩阵的大小，假设这个矩阵的右下角为 \((x,y)\)，那么我们就知道了每个矩阵的 \(a_{i,j}\) 之和。
那么对于列的分割方法，你可以通过前 \(x\) 行的信息推出要在哪些列进行分割。同理，你可以推出要在哪些行进行分割，判断是否合法即可。
-
对于一组 \((x,y)\) 有几种分割方式呢？正如闲话中所说的，\(a_{i,j}\) 都为正数，那么可以发现对于每一组 \((x,y)\) 都至多有一种分割方案。
-
对于求一个矩阵的 \(a_{i,j}\) 之和，不难想到二维前缀和优化。
详细见代码。
复杂度
- 时间：\(O(n^2\times m^2)\)。
- 空间：\(O(n\times m)\)。
Code
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int n, m, a[55][55], sum[55][55], cnt, stk[55], top, ans;
int C (int x, int y, int a, int b) { // 二维前缀和求解矩阵和
return sum[a][b] - sum[x - 1][b] - sum[a][y - 1] + sum[x - 1][y - 1];
}
void Solve (int i, int j) { // 对于一组 (i, j)，判断是否具有合法的分割方案
cnt = C(1, 1, i, j), top = 1, stk[1] = j; // cnt 为每个矩阵的和，stk 用于记录在哪些列需要分割
for (int k = j + 1; k <= m; k++) { // 利用前 i 行推出在哪些列需要分割
if (C(1, stk[top] + 1, i, k) == cnt) { // 找出来了一个矩阵
stk[++top] = k;
} else if (C(1, stk[top] + 1, i, k) > cnt) { // 不合法
return ;
}
}
if (stk[top] != m) { // 最右上角的矩阵和没有达到 cnt
return ;
}
int lst = i;
for (int k = i + 1; k <= n; k++) { // 已知在哪些列需要分割，推在哪些行需要分割
bool f = 0;
for (int l = 1; l <= top; l++) {
if (C(lst + 1, stk[l - 1] + 1, k, stk[l]) < cnt) { // 这一行还不够
f = 1;
} else if (C(lst + 1, stk[l - 1] + 1, k, stk[l]) > cnt) { // 这一行有矩阵和已经超过了 cnt，不可能合法
return ;
}
}
if (!f) { // 找到了满足要求的一行
lst = k;
}
}
if (lst != n) { // 最下方的矩阵还不合法
return ;
}
// cout << i << ' ' << j << '\n';
ans++;
}
int main () {
ios::sync_with_stdio(0), cin.tie(0);
//freopen("div.in", "r", stdin);
//freopen("div.out", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j], sum[i][j] = sum[i][j - 1] + a[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
sum[i][j] += sum[i - 1][j]; // 逐维前缀和
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
Solve(i, j);
}
}
cout << ans - 1; // 由于题目要求至少分割一次，则需要减去 (n, m) 这一组
return 0;
}