Add to Square
2022/2/18 23:27:57
本文主要是介绍Add to Square,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题意
ARC135D
给出 \(n \times m (n,m\leq 500)\) 的矩阵 \(A\)。
可以进行以下操作任意次:
- 选择一个 \(2 \times 2\) 的矩阵加一个任意的整数 \(c\)。
求最小的权值和 \(\sum_{i=1}^{n}\sum_{j=1}^{m}|A_{i,j}|\)
特征化
令 \(B\) 为操作完后的矩阵。
\(2 \times 2\) 的矩阵通常满足一些奇偶性,
考虑到答案求的是绝对值,对正负号没有影响。
将其结合就能得到关于行和列的特殊的恒等式:
对于任意行 \(i\):
\[\sum_{j=1}^{m}(-1)^{i+j}A_{i,j} = \sum_{j=1}^{m} (-1)^{i + j} B_{i,j} \]对于任意列 \(j\):
\[\sum_{i=1}^{n}(-1)^{i+j}A_{i,j} = \sum_{i=1}^{n} (-1)^{i + j} B_{i,j} \]也就是同一行同一列的加入的连续的两个数 \(x\) 互为相反数,相加相互抵消。
就能得到限制 \(B\) 矩阵的不变量。
- 换句话说,只要 \(B\) 满足上面的性质,那么 \(A\) 就一定能变成 \(B\)。
转化
现在问题变成了:
将全零矩阵 \(B\) 变成 满足每行每列的和与 \(A\) 相同的矩阵,满足 \(\sum_{i=1}^{n}\sum_{j=1}^{m}|B_{i,j}|\) 最小。
这同把 \(A\) 变为全零矩阵, 同时在 \(B\) 做相反操作是等价的。
令 \(x_i\) 为 \(A\) 矩阵第 \(i\) 行的和, \(y_j\) 为第 \(j\) 列的和,\(X = \sum_i |x_i|, Y = \sum_j |y_j|\)。
可以发现一次操作最多会使 \(X, Y\) 减去 \(|c|\)。
那么最小的和 \(\text{min} \geq \max\{X,Y\}\)
具体的步骤是:
- 如果 \(x_i > 0, y_j > 0\), 对 \(x_i, y_j\), 减去 \(\min{x_i, y_j}\)。
- 如果 \(x_i < 0, y_j < 0\), 对 \(x_i, y_j\), 减去 \(\max{x_i, y_j}\)。
- 如果 \(x_i > 0, x_j < 0\), 对 \(x_i, 1\), 减 \(\min\{x_i,-x_j\}\), 对 \(x_j, 1\) 减 \(-\min\{x_i,-x_j\}\)。
- 如果 \(y_i > 0, y_j < 0\), 对 \(1, y_i\), 减 \(\min\{y_i,-y_j\}\), 对 \(1, y_j\) 减 \(-\min\{y_i,-y_j\}\)。
对于第 1 和 2 点,因为总有 \(\sum_i x_i = \sum_j y_j\) 成立,总能找到同号的两个数做。
这样做到不能做后,肯定有 \(\forall i, x_i = 0 / \forall j,y_j = 0\)。
那么剩下两步就是对多余的进行处理,变成全零矩阵。
这样的构造是也是最优的构造。
代码
#include<bits/stdc++.h> using namespace std; #define ll long long const int MAXN = 510; int n, m; ll X[MAXN], Y[MAXN], b[MAXN][MAXN]; void upd(int x, int y, ll c) { X[x] -= c, Y[y] -= c; b[x][y] += (( (x + y) & 1 ) ? -1 : 1) * c; } int main() { cin >> n >> m; for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++) { ll x; cin >> x; if ((i + j) & 1) X[i] += -x, Y[j] += -x; else X[i] += x, Y[j] += x; } for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++) { if (X[i] < 0 && Y[j] < 0) upd(i, j, max(X[i], Y[j])); if (X[i] > 0 && Y[j] > 0) upd(i, j, min(X[i], Y[j])); } for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++) if (X[i] > 0 && X[j] < 0) { ll c = min(X[i], - X[j]); upd(i, 1, c); upd(j, 1, -c); } for (int i = 1; i <= m; i ++) for (int j = 1; j <= m; j ++) if (Y[i] > 0 && Y[j] < 0) { ll c = min(Y[i], -Y[j]); upd(1, i, c); upd(1, j, -c); } ll ans = 0; for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++) ans += abs(b[i][j]); cout << ans << endl; for (int i = 1; i <= n; i ++, cout << endl) for (int j = 1; j <= m; j ++) cout << b[i][j] << ' '; return 0; }
这篇关于Add to Square的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)