P6070 『MdOI R1』Decrease
题目
给定一个 \(n \times n\) 的矩阵，你可以进行若干次操作。
每次操作，你可以将一个 \(k \times k\) 的 连续 子矩阵里的所有数全都加上 \(1\) 或者全都减去 \(1\)。
初始时，矩阵中有 \(m\) 个位置上的数不为 \(0\)，其它位置上的数均为 \(0\)。
请你求出至少需要多少次操作，可以将矩形中所有数都变为 \(0\)。
输入
第一行三个整数 \(n,m,k\)，分别表示矩阵大小，非 \(0\) 格数和每次修改的连续子矩阵大小。
接下来 \(m\) 行，每行三个整数 \(x,y,z\)，表示初始时矩阵的第 \(x\) 行第 \(y\) 列上的数为 \(z\)。
输出
一行一个整数，表示最少操作次数。
特别地，如果无法使矩阵中所有数都变为 \(0\)，输出 -1。
样例 #1
输入
4 14 3
1 1 1
1 2 1
1 3 1
2 1 1
2 2 3
2 3 3
2 4 2
3 1 1
3 2 3
3 3 3
3 4 2
4 2 2
4 3 2
4 4 2
输出
3
样例 #2
输入
3 1 2
1 1 1
输出
-1
样例 #3
输入
4 5 1
1 1 5
2 2 -3
2 3 -4
3 3 1
4 4 2
输出
15
提示
【样例 1 解释】:
给出的矩阵为：
1 1 1 0
1 3 3 2
1 3 3 2
0 2 2 2
具体步骤：
先将以第一行第一列为左上角的连续子矩阵执行 减 1 操作 一次；
再将以第二行第二列为左上角的连续子矩阵执行 减 1 操作 两次。
总共三次。
1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
1 3 3 2 0 2 2 2 0 1 1 1 0 0 0 0
1 3 3 2 0 2 2 2 0 1 1 1 0 0 0 0
0 2 2 2 0 2 2 2 0 1 1 1 0 0 0 0
【样例 2 解释】：
给出的矩阵为：
1 0 0
0 0 0
0 0 0
只通过 \(2\times 2\) 的连续子矩阵操作不可能使得所有格子上的数都变为 \(0\)。
【数据范围】
本题采用捆绑测试。
| 子任务编号 | \(n\leq\) | \(k\leq\) | 分值 |
|---|---|---|---|
| 1 | \(10^3\) | \(1\) | 11 |
| 2 | \(20\) | \(20\) | 14 |
| 3 | \(100\) | \(100\) | 17 |
| 4 | \(10^3\) | \(10^3\) | 34 |
| 5 | \(5\times 10^3\) | \(10^3\) | 24 |
对于所有数据，\(1\leq n\leq 5\times 10^3\)，\(1\leq m\leq \min(n^2,5\times 10^5)\)，\(1\leq k\leq \min(n,10^3)\)，\(1\leq x,y\leq n\)，每对 \((x,y)\) 至多出现一次，\(1 \le |z| \leq 10^9\)。
数据保证如果有解，答案不超过 \(2^{63}-1\)。
【提示】
本题读入量较大，建议使用较快的读入方式。
思路
分析数据范围，时间复杂度为 \(O(n^2k^2)\) 的暴力写法只能拿部分分数。题目中“可以将一个 \(k \times k\) 的子矩阵全部加上 \(1\) 或者全部减去 \(1\)”。借鉴二维差分的思想：连续位置数值增减修改。假设矩阵中每个值为 \(f_{i,j}\)，如果想对 \(f_{1,1}\) 做修改，就只能对 \(f_{1,1}\) 到 \(f_{k,k}\) 这一个大矩阵进行修改。如果想对 \(f_{1,2}\) 做修改，由于不能改变 \(f_{1,1}\) 的值，所以只能改动 \(f_{1,2}\) 到 \(f_{k,k+2}\) 这个矩阵的值。以此类推，只要把当前数消为 \(0\) 就可以了。假设差分数组为 \(cf \lbrack \rbrack\)，要将 \((i,j)\) 位置的数字消为 \(0\)，则
\[cf_{i+k,j+k}-=cf_{i,j},cf_{i+k,j}+=cf_{i,j},cf_{i,j+k}+=cf_{i,j}(i+k \le n,j+k \le n) \]\(cf_{i,j}\) 表示将 \((i,j)\) 位置数字消为 \(0\) 的操作数，将其绝对值进行累加即为总操作数。最后判断是否矩阵中所有的数字都被消为 \(0\) 即可。
代码
#include <bits/stdc++.h>
using namespace std;
int n, m, k, x, y, z, a[5010][5010], cf[5010][5010];
long long ans;
int main()
{
scanf("%d %d %d", &n, &m, &k);
while (m -- )
{
scanf("%d %d %d", &x, &y, &z);
a[x][y] = z;
}
for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= n; j ++ )
cf[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1];
}
for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= n; j ++ )
{
ans += abs(cf[i][j]); // 记得加绝对值
if (i + k <= n + 1 && j + k <= n + 1)
{
cf[i + k][j] += cf[i][j];
cf[i][j + k] += cf[i][j];
cf[i + k][j + k] -= cf[i][j];
cf[i][j] -= cf[i][j]; // 注意：放在循环最后
}
}
}
for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= n; j ++ )
{
if (cf[i][j] != 0)
{
puts("-1");
return 0;
}
}
}
printf("%lld", ans);
return 0;
}