题意
给定 n × n ( 2 ≤ n ≤ 2000 ) n \times n(2 \leq n \leq 2000) n×n(2≤n≤2000) 的矩阵，每格中有一个权值。初始时权值全部为 0 0 0，mxjz666 对其举行若干次操作，每次选定一行或一列，对于这一行或这一列加上某个正整数，末了给你操作后的矩阵并将其中一个数字改成 − 1 -1 −1，求这个数原来是多少
思路
等效替代，将一行（列）的多次等效看成加了一次，记第 i i i 行一共加上了 x i x_i xi,第 j j j 列一共加上了 y j y_j yj，则 更改后的数为 x i + y j x_i + y_j xi+yj。记上述式子的结果为 a i , j a_{i,j} ai,j。
不妨令 i , j < 0 i,j < 0 i,j<0，有
a i , j = x i + y i = x i + y i + x i + 1 + y i + 1 − x i + 1 − y i + 1 = a i , j + 1 + a i + 1 , j − a i + 1 , j + 1 a_{i,j} = x_i + y_i = x_i + y_i + x_{i+1} + y_{i+1} - x_{i+1} - y_{i+1}=a_{i,j + 1} + a_{i+1,j}- a_{i+1,j+1} ai,j=xi+yi=xi+yi+xi+1+yi+1−xi+1−yi+1=ai,j+1+ai+1,j−ai+1,j+1
因此，有对于恣意一个边长为 2 的矩阵，都有对角相加和相称的结论。
鼎力大举分讨即可。
代码
- #include<bits/stdc++.h>
- #define int long long
- using namespace std;
- int n,a[2005][2005],x,y;
- signed main() {
- scanf("%lld",&n);
- for(int i = 1;i <= n;i++) {
- for(int j = 1;j <= n;j++) {
- scanf("%lld",&a[i][j]);
- if(a[i][j] == -1) x = i,y = j;
- }
- }
- if(x < n and y < n) {
- printf("%lld\n",a[x + 1][y] + a[x][y + 1] - a[x + 1][y + 1]);
- }
- else if(x == 1 and y == n) {
- printf("%lld\n",a[x + 1][y] + a[x][y - 1] - a[x + 1][y - 1]);
- }
- else if(x == n and y == 1) {
- printf("%lld\n",a[x - 1][y] + a[x][y + 1] - a[x - 1][y + 1]);
- }
- else {
- printf("%lld\n",a[x - 1][y] + a[x][y - 1] - a[x - 1][y - 1]);
- }
- return 0;
- }
|
