cf 996 div2 C

C 题意：
n 行m 列,单元格(i j ) 的高度用aij 表示。
从左上角 (1,1) 开始，到右下角 (n,m) 结束，由 n+m−1 个单元格组成的路径已被清除。路径上的每个单元格 (i,j) 的高度 aij 都被设置为 0。该路径严格按照向下( D )或向右( R )的步骤移动

已知，满足每一行每一列的和相同。现在我们要确定被清除的位置数值是多少

假设这个每一行每一列的和为S
那么有
S * N=S * M
对于一般的N !=M 的情况，之后当S==0 的时候，才可以使得等式成立。
现在我们的任务就变成 怎样以一种合理的顺序去求解。
（我求解当前位置 必须保证 我行/ 列 只有这一个未知的位置）
可以发现，因为我只能 D 或者 R .所以我的路径顺序其实就是一种可行的顺序。我到达某一个位置，我要么通过行要么通过这一列。如果我到达这个位置之后是D，那么我通过行。else t通过列

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
#define int long long 
int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = (x << 1) + (x << 3) + ch - '0';
        ch = getchar();
    }
    return x * f;
}

void solve()
{
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    vector<vector<int>> a(n, vector<int>(m));
    vector<int> s1(n);
    vector<int> s2(m);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> a[i][j];
            s1[i] += a[i][j];
        }
    }
    for (int j = 0; j < m; j++)
    {
        for (int i = 0; i < n; i++)
        {

            s2[j] += a[i][j];
        }
    }
    int nx = 0;
    int ny = 0;

    for (auto i : s)
    {
        if (i == 'D')
        {
            a[nx][ny] = -s1[nx];
        }
        else
        {
            a[nx][ny] = -s2[ny];
        }
        s1[nx] += a[nx][ny];
        s2[ny] += a[nx][ny];
        if (i == 'D')
            nx++;
        else
            ny++;
    }
    a[n-1][m-1]=-s1[n-1];
    for (int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cout<<a[i][j]<<" ";
        }
        cout<<"\n";
    }

}
signed main()
{
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

原文地址：https://blog.csdn.net/x1653673086/article/details/145199028

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！