codeforces C. The Trail

 

目录

题目： 

思路分析： 

总代码：

---

题目： 

https://codeforces.com/contest/2055/problem/C

C. 山径
每个测试时间限制：2秒
每个测试内存限制：256兆字节

佛罗里达没有山，佛罗里达人无法理解山的存在。因此，他急需你的帮助来解决这个问题。

在一片荒野中，有一片由 n 行 m 列的矩形网格表示的山区地形。每个网格单元的位置用 (i,j) 表示，其中 i 是行索引，j 是列索引。单元格 (i,j) 的海拔高度记为 ai,j。

然而，这片区域被人为改动过。一条从左上角 (1,1) 到右下角 (n,m) 的路径上的所有单元格的海拔被设置为 0。这条路径由 n+m−1 个单元格组成，移动方式严格为向下（D）或向右（R）。

为了将地形恢复至原始状态，已知在未被改动前，这片区域具有一种神奇的特性：所有行和所有列的海拔高度之和相同。更正式地说，存在一个整数 x，使得对于所有 1≤i≤n，∑mj=1ai,j=x；且对于所有 1≤j≤m，∑ni=1ai,j=x。

你的任务是为路径上的单元格重新分配海拔高度，使得这一神奇特性得以恢复。可以证明解一定存在。如果有多个解满足条件，输出其中任意一个即可。

输入
每个测试包含多个测试用例。第一行包含测试用例的数量 t（1≤t≤104）。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 n 和 m（2≤n,m≤1000）——网格的行数和列数。

第二行包含一个长度为 n+m−2 的字符串 s（si=D 或 si=R）——表示从 (1,1) 到 (n,m) 的路径移动步骤。字符 D 表示向下移动，R 表示向右移动。

接下来的 n 行，每行包含 m 个整数 ai,1,ai,2,…,ai,m（−106≤ai,j≤106）——网格中每个单元格的海拔高度。保证如果单元格 (i,j) 位于路径上，则 ai,j=0。

保证所有测试用例的 n⋅m 之和不超过 106。

输出
对于每个测试用例，输出 n 行，每行 m 个整数，表示恢复后的海拔高度网格 bi,j。海拔高度需满足 −1015≤bi,j≤1015，并且如果 (i,j) 不在路径上，则 ai,j=bi,j。如果有多个解，输出其中任意一个。

思路分析： 

本题很明显是一个构造题，答案有多个，通过之前做的一些构造题，我发现各个答案中间是有一些参数是固定的，比如B. Binary Colouringhttps://codeforces.com/contest/1977/problem/B构造数组，数组长度可以固定，本题说的是构造一个二维数组使其各个行列的和相等，我们发现值可正可负，所以我们就可以把这个和固定，固定成0，往后的构造都往0，上面靠即可；

本题我们应该明确的一个点是：一个点的更改既会影响行也会影响列，因此我们考虑的时候要兼顾的考虑，题目说的是更改路径上的值，如果D意味着向下移动，意味着当前这一行往后就不能更改了，所以如果是D那么就必须要更改当前点的值，使其等于当前行的和的相反数，同样如果是R，代表当前列往后不会考虑了。

总代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000 + 10;
int a[N][N];
int sumh[N], suml[N];//sumh是每个行的和，suml是每个列的和
void solve(){int n, m; cin >> n >> m;string s; cin >> s;for(int i = 1; i <= max(n,m); i ++){sumh[i] = 0;suml[i] = 0;}样例有多个，每解决一个样例都得复原一下，防止前一个样例干扰后一个样例for(int i = 1; i <= n; i ++){for(int j = 1; j <= m; j ++){cin >> a[i][j];sumh[i] += a[i][j];suml[j] += a[i][j];
//计算原始数组的不同行和不同列的和}}int sz = s.size();int x=1,y=1;for(int i = 0; i < sz; i ++){if(s[i]=='D'){a[x][y] = -sumh[x];}else{a[x][y] = -suml[y];}suml[y] += a[x][y];sumh[x] += a[x][y];if(s[i] == 'R') y ++;else x ++;}a[n][m]-=sumh[n];for(int i = 1; i <= n; i ++){for(int j = 1; j <= m; j ++){cout << a[i][j] << ' ';}cout << '\n';}
}
signed main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int q; cin >> q;while(q--){solve();}return 0;
}