Codeforces Round #345 (Div. 1) C. Table Compression

看到此文,是否觉得体内洪荒之力爆发,饥渴难耐想吐槽、情不自禁想捐赠
本文为原创文章,尊重辛勤劳动,可以免费摘要、推荐或聚合,亦可完整转载,但完整转载需要标明原出处,违者必究。

支付宝微  信

原题

C. Table Compression
time limit per test

4 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Little Petya is now fond of data compression algorithms. He has already studied gz, bz, zip algorithms and many others. Inspired by the new knowledge, Petya is now developing the new compression algorithm which he wants to name dis.

Petya decided to compress tables. He is given a table a consisting of n rows and m columns that is filled with positive integers. He wants to build the table a' consisting of positive integers such that the relative order of the elements in each row and each column remains the same. That is, if in some row i of the initial table ai, j < ai, k, then in the resulting table a'i, j < a'i, k, and if ai, j = ai, k then a'i, j = a'i, k. Similarly, if in some column j of the initial table ai, j < ap, j then in compressed table a'i, j < a'p, j and if ai, j = ap, j then a'i, j = a'p, j.

Because large values require more space to store them, the maximum value in a' should be as small as possible.

Petya is good in theory, however, he needs your help to implement the algorithm.

Input

The first line of the input contains two integers n and m (, the number of rows and the number of columns of the table respectively.

Each of the following n rows contain m integers ai, j (1 ≤ ai, j ≤ 109) that are the values in the table.

Output

Output the compressed table in form of n lines each containing m integers.

If there exist several answers such that the maximum number in the compressed table is minimum possible, you are allowed to output any of them.

Examples
input
2 2
1 2
3 4
output
1 2
2 3
input
4 3
20 10 30
50 40 30
50 60 70
90 80 70
output
2 1 3
5 4 3
5 6 7
9 8 7
Note

In the first sample test, despite the fact a1, 2 ≠ a21, they are not located in the same row or column so they may become equal after the compression.

分析

第一次看到这个题的反应就是,参考答案。找到若干个网上的答案后,试着尝试读懂程序。2个小时后的感受就是“智商”不够,先补补课。

目前为止,我终于搞懂了该题的解法思路。在这里分享下鄙见。

首先,题意大家都明白了,不再赘述。如果你不懂题意,请自行按下如下按键:Command + d(Windows:ctrl + d)。

好,你懂题意了。为了分析,先简化下。给原题增加个条件:矩阵中的元素保持唯一。所以,我们解决的思路似乎会更简明。

我们将n*m的矩阵分成n*m个子集,也就是说每个子集仅包含一个元素,且各不相同。此时,我们要保证同行和同列相对关系相等。所以,此时我们需要建立一个数组来维护所有子集(一个元素)的大小关系。我们只维护每行和每列的。比如第一行的维护关系如下:

e[3] = {1} // 代表下标为3的子集大于下标为1的子集(注元素下标我们从1开始计)

e[1] = {2} // 同上

这样我们在计算结果时利用动态规划的思想来取得每个压缩后的子集,如下:

dp[3] = max(1, dp[1] + 1); // 因为3集合要比1集合大,所以我们3集合的最小值为1何dp[1] + 1的其中最大的一个

此时你已经动了大致的思路了,这时放开题的条件,允许原始矩阵的元素相同。那么,我们仍然要在之前分析的基础上来进行求解。那么,我们利用并查集的方式来维护每个独立的子集。简单的说,就是原始数据中的第3个元素和第6个元素对我们来说,是属于同一个子集,只不过这个子集里面有两个元素而已。那么我们用p来维护元素的所属子集关系。

程序范例

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

const int N = 1e6 + 10; // 矩阵中每一个数的上限
int n, m; // n -> 行数 m -> 列数
int ar[N]; // 用一维数组存储原始矩阵数据
int pos[N]; // 存某一行(或者列)的所有元素的索引下标(从1开始记)
int cnt; // n * m
vector<int> e[N]; // 多源有向图,维护集合之间的大小关系
vector<int> se[N]; // 每一个集合的元素
int ans[N]; // 压缩后的矩阵数据
int dp[N]; // 动态规划
int p[N]; // 并查集数组

/**
 * 迭代找爹,一直找到祖宗.
 */
int find(int x)
{
    return p[x] == x ? p[x] : p[x] = find(p[x]);
}

/**
 * 比较函数,正序排序.
 */
bool cmp(int x, int y)
{
    return ar[x] < ar[y];
}

/**
 * 干活.
 */
void work(int x, int y)
{
    // 如果原始矩阵中x和y位置的元素不等,那么让x所在位置的元素值为相对大的那个
    if (ar[x] < ar[y]) {
        swap(x, y);
    }
    if (ar[x] == ar[y]) {
        // 让并查集的x的祖宗服从y的祖宗
        p[find(x)] = find(y);
        return;
    }
    e[x].push_back(y);
}

int dfs(int x)
{
    x = find(x);
    if (dp[x]) {
        return dp[x];
    }
    dp[x] = 1;
    // 独立的子集数
    for (int i = 0; i < se[x].size(); i++) {
        // 遍历每个子集里面的所有元素,比如子集1里面只有一个元素20
        for (int j = 0; j < e[se[x][i]].size(); j++) {
            int to = e[se[x][i]][j];
            dp[x] = max(dp[x], dfs(to) + 1);
        }
    }
    return dp[x];
}

int main()
{
    // 输入行数与列数
    cin>>n;
    cin>>m;

    // 初始化原始矩阵数组
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cnt++;
            cin>>ar[cnt];
        }
    }

    // 初始化并查集数组
    for (int i = 1; i <= cnt; i++) {
        p[i] = i;
    }

    // 看里面注释
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            // 在某一行的前提下,取每一列的位置
            pos[j] = (i - 1) * m + j;
        }
        // 将每一行的元素正序排序
        sort(pos + 1, pos + 1 + m, cmp);
        for (int j = 1; j < m; j++) {
            work(pos[j], pos[j + 1]);
        }
    }

    // 遍历所有每一行的元素
    for (int j = 1; j <= m; j++) {
        // 获取每一行的元素,pos的值为数组索引
        for (int i = 1; i <= n; i++) {
            pos[i] = (i - 1) * m + j;
        }
        sort(pos + 1, pos + 1 + n, cmp);
        // 进行并查集运算,处理p数组,分成若干子集合,同时建立多元有向图集合e(用于维护哪个集合和哪个集合的大小关系)
        for (int i = 1; i < n; i++) {
            work(pos[i], pos[i + 1]);
        }
    }

    // 获取每个集合里面的所有元素
    for (int i = 1; i <= cnt; i++) {
        int fa = find(i);
        se[fa].push_back(i);
    }

    // 计算结果,利用动态规划的思想。即当前元素x的最小值,为max(1, dp[x - 1])。
    // 其中x - 1 即为 e[x]的值
    for (int i = 1; i <= cnt; i++) {
        ans[i] = dfs(i);
    }

    // 输出结果
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cout<<ans[(i - 1) * m + j]<<' ';
        }
        cout<<endl;
    }

    return 0;
}

文章来源:胡旭博客 => Codeforces Round #345 (Div. 1) C. Table Compression
参考文章:


这是一篇原创文章,如果您觉得有价值,可以通过捐赠来支持我的创作~
捐赠者会展示在博客的某个页面,钱将会用在有价值的地方,思考中...

发表评论

电子邮件地址不会被公开。