题解：CF2055C The Trail

114514xxx · 2025-01-16 20:50:57 · 题解

思路

设 n 行 m 列的矩阵每行之和或每列之和为 x，那么 nx=mx，当 n=m。

当 n \ne m 时，注意到当且仅当 x=0 时唯一的解。当 n=m 时，x=0 同样也是成立的。

因此我们只要让每一列和每一行的和为 0 即可。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e3 + 25;
const int inf = 2e9;
int a[N][N], q[N], n, m, k, x, y, sum, b[N], c, d;
bool vis[N][N];
map<int, int> mp;
map<int, int> mp1;
int rc[N], lc[N];
int sum1[N], sum2[N];
inline void solve(){
    memset(sum1,0,sizeof(sum1));   
    memset(sum2,0,sizeof(sum2));  
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
            sum1[i] += a[i][j];
            sum2[j] += a[i][j];
        }
    }
    int x = 1, y = 1;
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] != 'D')
        {
            a[x][y] = -sum2[y];
            sum1[x] -= sum2[y];
            sum2[y] = 0;
            y++;
        }
        else
        {
            a[x][y] = -sum1[x];
            sum2[y] -= sum1[x];
            sum1[x] = 0;
            x++;
        }
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (i == n && j == m)
                a[i][j] = -sum2[m];
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
}
int t;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> t;
    while (t--)
        solve();
}