Polycarp and Hay

发表于 更新于 分类于 ，

    给出一个 n * m 的二维数组g，g中元素不超过1e8。

    现在构造一个新的矩阵，矩阵中的值必须不大于原矩阵的值。且所有非0元素都等于原矩阵中的某个值，并且构造的矩阵所有元素值的和等于k。

Polycarp and Hay

Created by LXC on Wed Jun 7 11:57:03 2023

https://codeforces.com/problemset/problem/659/F

ranting: 2000

tag: dfs and similar, dsu, graphs, greedy, sortings

problem

给出一个 n * m 的二维数组g，g中元素不超过1e8。

现在构造一个新的矩阵，矩阵中的值必须不大于原矩阵的值。且所有非0元素都等于原矩阵中的某个值，并且构造的矩阵所有元素值的和等于k。

solution

对原矩阵中的值按照降序排序，并逐个加入并查集中，对于当前元素值为x，如果相邻上下左右的元素值存在大于等于x，则将他们所在集合与x所在集合合并。

在合并后，如果x时k的因子，且k/x小于等于x所在集合的大小，那么可以从x所在集合中选取大小为k/x的连通块，将其所有值改为i，矩阵中其余值改为0，就得到了构造的合法矩阵。

code

卡在第95个测试用例，焯！！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 1005
#define MOD 998244353
using namespace std;

int vis[N][N];

ll g[N][N];

ll n, m, k;

int st[N * N];
ll cnt = 0;

void dfs(int x, int y, ll lm) {
    // if (n == 1000 && m == 1000) {
    //     cout << x << " " << y << " " << lm << endl;
    // }
    if (cnt == 0)
        return;
    cnt--;
    vis[x][y] = 1;
    for (int d = 0; d < 4; d++) {
        int mx = x + (d - 1) % 2;
        int my = y + (d - 2) % 2;
        if (mx < 0 || mx >= n || my < 0 || my >= m || g[mx][my] < lm ||
            vis[mx][my])
            continue;
        dfs(mx, my, lm);
    }
}

void uf_init() {
    memset(st, -1, sizeof(st));
}

int uf_find(int x) {
    return st[x] < 0 ? x : st[x] = uf_find(st[x]);
}

bool uf_union(int x, int y) {
    int fx = uf_find(x), fy = uf_find(y);
    if (fx != fy) {
        st[fx] += st[fy];
        st[fy] = fx;
        return true;
    }
    return false;
}

void sol() {
    uf_init();
    map<ll, vector<pair<int, int>>, greater<ll>> mp;
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> g[i][j];
            mp[g[i][j]].emplace_back(i, j);
        }
    }
    set<pair<ll, ll>> root;  // 区块大小，区块的根
    for (auto& [i, j] : mp) {
        for (auto [x, y] : j) {
            int t = uf_find(x * m + y);
            root.insert({st[t], t});
            for (int d = 0; d < 4; d++) {
                int mx = x + (d - 1) % 2;
                int my = y + (d - 2) % 2;

                if (mx < 0 || mx >= n || my < 0 || my >= m || g[mx][my] < i)
                    continue;
                int fa = uf_find(mx * m + my), fb = uf_find(x * m + y);
                if (root.count({st[fa], fa}))
                    root.erase({st[fa], fa});
                if (root.count({st[fb], fb}))
                    root.erase({st[fb], fb});
                if (uf_union(mx * m + my, x * m + y)) {
                    fa = uf_find(x * m + y);
                    root.insert({st[fa], fa});
                } else {
                    root.insert({st[fa], fa});
                    root.insert({st[fb], fb});
                }
            }
        }
        // cout << i << " " << cnt << ' ' << root.size() << endl;
        // for (int r : root) {
        //     cout << r / m << " " << r % m << "\n";
        // }
        if (k % i == 0 && -i * root.begin()->first >= k) {
            cnt = k / i;
            // cout << i << " " << k << "\n";
            // if (n == 990 && m == 990) {
            //     cout << i << " " << k << " " << root.begin()->first << "\n";
            // }
            cout << "YES\n";

            dfs(j[0].first, j[0].second, i);

            for (int r = 0; r < n; r++) {
                for (int c = 0; c < m; c++) {
                    cout << (vis[r][c] ? i : 0) << " ";
                }
                cout << "\n";
            }
            return;
        }
    }
    cout << "NO\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

改了改实现，还是wa了，目测是continue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 1005
#define MOD 998244353
using namespace std;

int vis[N][N];

ll g[N][N];

ll n, m, k;

int st[N * N];

ll cnt = 0;

void uf_init() {
    memset(st, -1, sizeof(st));
}

int uf_find(int x) {
    return st[x] < 0 ? x : st[x] = uf_find(st[x]);
}

bool uf_union(int x, int y) {
    int fx = uf_find(x), fy = uf_find(y);
    if (fx != fy) {
        st[fx] += st[fy];
        st[fy] = fx;
        return true;
    }
    return false;
}

void dfs(int x, int y, int id) {
    if (cnt == 0)
        return;
    cnt--;
    vis[x][y] = 1;
    for (int d = 0; d < 4; d++) {
        int mx = x + (d - 1) % 2;
        int my = y + (d - 2) % 2;
        if (mx < 0 || mx >= n || my < 0 || my >= m ||
            uf_find(mx * m + my) != id || vis[mx][my])
            continue;
        dfs(mx, my, id);
    }
}

void sol() {
    uf_init();
    vector<pair<ll, ll>> idx;
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> g[i][j];
            idx.emplace_back(i, j);
        }
    }
    sort(idx.begin(), idx.end(), [&](auto& a, auto& b) {
        return g[a.first][a.second] > g[b.first][b.second];
    });
    for (auto [ix, iy] : idx) {
        for (int d = 0; d < 4; d++) {
            int mx = ix + (d - 1) % 2;
            int my = iy + (d - 2) % 2;
            if (mx < 0 || mx >= n || my < 0 || my >= m || g[mx][my] < g[ix][iy])
                continue;
            uf_union(ix * m + iy, mx * m + my);
            if (k % g[ix][iy] == 0 &&
                -st[uf_find(ix * m + iy)] >= k / g[ix][iy]) {
                cnt = k / g[ix][iy];
                dfs(ix, iy, uf_find(ix * m + iy));
                cout << "YES\n";
                for (int r = 0; r < n; r++) {
                    for (int c = 0; c < m; c++) {
                        cout << (vis[r][c] ? g[ix][iy] : 0) << " ";
                    }
                    cout << "\n";
                }
                return;
            }
        }
    }
    cout << "NO\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

wa了17次，终于ac了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 1005
#define MOD 998244353
using namespace std;

int vis[N][N];

ll g[N][N];

ll n, m, k;

int st[N * N];

ll cnt = 0;

void uf_init() {
    memset(st, -1, sizeof(st));
}

int uf_find(int x) {
    return st[x] < 0 ? x : st[x] = uf_find(st[x]);
}

bool uf_union(int x, int y) {
    int fx = uf_find(x), fy = uf_find(y);
    if (fx != fy) {
        st[fx] += st[fy];
        st[fy] = fx;
        return true;
    }
    return false;
}

void dfs(int x, int y, int id) {
    if (cnt == 0)
        return;
    cnt--;
    vis[x][y] = 1;
    for (int d = 0; d < 4; d++) {
        int mx = x + (d - 1) % 2;
        int my = y + (d - 2) % 2;
        if (mx < 0 || mx >= n || my < 0 || my >= m ||
            uf_find(mx * m + my) != id || vis[mx][my])
            continue;
        dfs(mx, my, id);
    }
}

void sol() {
    uf_init();
    vector<pair<ll, ll>> idx;
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> g[i][j];
            idx.emplace_back(i, j);
        }
    }
    sort(idx.begin(), idx.end(), [&](auto& a, auto& b) {
        return g[a.first][a.second] > g[b.first][b.second];
    });
    for (auto [ix, iy] : idx) {
        for (int d = 0; d < 4; d++) {
            int mx = ix + (d - 1) % 2;
            int my = iy + (d - 2) % 2;
            if (mx < 0 || mx >= n || my < 0 || my >= m || g[mx][my] < g[ix][iy])
                continue;
            uf_union(ix * m + iy, mx * m + my);
        }
        if (k % g[ix][iy] == 0 && -st[uf_find(ix * m + iy)] >= k / g[ix][iy]) {
            cnt = k / g[ix][iy];
            dfs(ix, iy, uf_find(ix * m + iy));
            cout << "YES\n";
            for (int r = 0; r < n; r++) {
                for (int c = 0; c < m; c++) {
                    cout << (vis[r][c] ? g[ix][iy] : 0) << " ";
                }
                cout << "\n";
            }
            return;
        }
    }
    cout << "NO\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}