Matrix Transformation codechef 数学题

https://www.codechef.com/problems/MTRNSFRM

我只能说codechef的题好劲爆，这题居然是easy的题，太可怕了。而且还有一点就是codechef的题解很难看懂╮(￣▽￣")╭

这题可以这样做，首先把两个矩阵合并在一起，然后就是变成了在一个矩阵C中，操作行和列的+1或者-1,最终使得整个矩阵为0。

那么。对于每一行，的操作，我设为row[i]，意思就是这一行进行的是什么操作，要么+，要么-，不可能又加又减的，因为都是整行的操作。然后同理设出col[j]。

然后，如果有解，那么需要每个c[i][j] + row[i] + col[j] == 0恒成立。

在上面的方程中，有两个未知数，因为其是互相独立的，那么特殊值一个先，先设i = 1

有col[j] = -row[1] - c[1][j] ① （这个就是col[j]的方程，因为只有j这个未知数）row[1]可以暴力出来，或者二分出来，反正是常数，那么带入去原来的式子，有：row[i] = row[1] + c[1][j] - c[i][j]

同样是因为独立，所以特殊值那个j = 1，所以row[i] = row[1] + c[1][1] - c[i][1] ②

有了上面两条式子，要判定c[i][j] + row[i] + col[j] == 0是否成立就简单了，带进去即可。

求解：

解的大小是sigma abs(row[i]) + sigma abs(col[j])

目标是最小化这个函数。

其中有一个x（row[1]）是还没确定的呢。

把公式拆开，就是sigma(abs(c[i][1] - c[1][1] - x)) + sigma(-c[1][j] - x)

那么就是求一个点x，到c[i][1] - c[1][1] 和 -c[1][j] 这n + m个点的总和最小。

中间值即可。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <assert.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <bitset>

const int maxn = 1e5 + ;

vector<LL>a[maxn], ta[maxn];

vector<LL>vc;

void work() {

    int n, m;

    scanf("%d%d", &n, &m);

    vc.clear();

    for (int i = ; i <= n; ++i) {

        a[i].clear();

        ta[i].clear();

        a[i].push_back();

    }

    for (int i = ; i <= ; ++i) {

        for (int j = ; j <= n; ++j) {

            for (int k = ; k <= m; ++k) {

                LL x;

                if (i == ) {

                    scanf("%lld", &x);

                    a[j].push_back(x);

                } else {

                    scanf("%lld", &x);

                    a[j][k] -= x;

                }

            }

        }

    }

    for (int i = ; i <= n; ++i) ta[i] = a[i];

    for (int i = ; i <= n; ++i) {

        for (int j = ; j <= m; ++j) {

            if (a[i][j] + a[][] - a[i][] - a[][j] != ) {

                cout << - << endl;

                return;

            }

        }

    }

    vc.push_back(-((1LL) << ));

    for (int i = ; i <= n; ++i) {

        vc.push_back(a[i][] - a[][]);

    }

    for (int j = ; j <= m; ++j) {

        vc.push_back(-a[][j]);

    }

    sort(vc.begin(), vc.end());

    LL ans = ;

    for (int i = ; i < vc.size(); ++i) {

        ans += abs(vc[i] - vc[(n + m + ) / ]);

    }

    cout << ans << endl;

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    int t;

    scanf("%d", &t);

    while (t--) work();

    return ;

}

巴特西

Matrix Transformation codechef 数学题

最新文章

热门文章