Table Recovery

题意

原始表格是 $N\times N$ 的加法表，位置 $(r,c)$ 的值为 $r+c$ 。

Elsie 先交换若干行，再交换若干列，最后对表中出现的值做若干次全局交换。现在给出最终表格，要求恢复“只交换行列后、还没有做值交换前”的一种可能表格，并且要求字典序最小。

思路

先看小数据暴力：枚举行排列和列排列，生成候选加法表，再检查它是否能通过值重命名变成输入表。

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 20:40
 * update_at: 2026-07-11 20:41
 */
// brute.cpp：小数据暴力解，枚举行排列和列排列并检查是否能重命名成输入表。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 8;
const int MAXV = 20;

int n;
int a[MAXN][MAXN];
int p[MAXN], q[MAXN];
int best[MAXN][MAXN];
bool has_best;

bool is_valid() {
    int label[MAXV];
    for (int i = 0; i < MAXV; i++) label[i] = -1;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int x = p[i] + q[j];
            if (label[x] == -1) {
                label[x] = a[i][j];
            } else if (label[x] != a[i][j]) {
                return false;
            }
        }
    }
    return true;
}

bool candidate_is_better() {
    if (!has_best) return true;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int x = p[i] + q[j];
            if (x < best[i][j]) return true;
            if (x > best[i][j]) return false;
        }
    }
    return false;
}

void save_candidate() {
    has_best = true;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            best[i][j] = p[i] + q[j];
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }

    for (int i = 1; i <= n; i++) {
        p[i] = i;
        q[i] = i;
    }

    do {
        for (int i = 1; i <= n; i++) q[i] = i;
        do {
            if (is_valid() && candidate_is_better()) {
                save_candidate();
            }
        } while (next_permutation(q + 1, q + n + 1));
    } while (next_permutation(p + 1, p + n + 1));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (j > 1) cout << ' ';
            cout << best[i][j];
        }
        cout << '\n';
    }

    return 0;
}

暴力的枚举对象很清楚，但 $N$ 最大到 1000，不能枚举排列。

考虑原始加法表中每个值出现了多少次。以 $N=3$ 为例：

值	出现次数
2	1
3	2
4	3
5	2
6	1

行列交换不会改变数值出现次数。类型 3 操作只是把两个值整体交换，所以某个最终值的出现次数也仍然等于它原来对应值的出现次数。

在原始加法表中，只有 2 和 2N 出现 1 次。最终表中也会有两个出现 1 次的值，它们对应原来的 2 和 2N，只是我们不知道谁对应谁。

任选一个出现 1 次的值，设它在输入表中的位置是 (x,y)。

如果它对应原来的 2，那么这个位置在行列交换后的表中就是 $p_x = 1, q_y = 1$ 。此时：

第 x 行的元素形如 1 + q_j，它们的出现次数正好是 q_j；
第 y 列的元素形如 p_i + 1，它们的出现次数正好是 p_i。

所以可以令：

text

1
2row_value[i] = freq[table[i][y]]
col_value[j] = freq[table[x][j]]

得到一个候选答案：

text

1ans0[i][j] = row_value[i] + col_value[j]

如果这个唯一值其实对应原来的 2N，那么会得到互补的另一种候选。原始加法表有一个对称性：

text

1x -> 2N + 2 - x

所以另一个候选为：

text

1ans1[i][j] = 2 * (N + 1) - ans0[i][j]

官方解析说明，合法答案只会是这两种互补候选之一。我们把两张候选表按题目要求的顺序比较，输出字典序更小的那张。

代码

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 20:40
 * update_at: 2026-07-11 20:41
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
const int MAXV = 2005;

int n;
int a[MAXN][MAXN];
int freq_cnt[MAXV];
int row_value[MAXN]; // row_value[i] 表示第 i 行对应的 p_i 或其互补值
int col_value[MAXN]; // col_value[j] 表示第 j 列对应的 q_j 或其互补值

int value0(int i, int j) {
    return row_value[i] + col_value[j];
}

int value1(int i, int j) {
    return 2 * (n + 1) - value0(i, j);
}

int choose_answer_type() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int x = value0(i, j);
            int y = value1(i, j);
            if (x < y) return 0;
            if (x > y) return 1;
        }
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
            freq_cnt[a[i][j]]++;
        }
    }

    int unique_row = 1;
    int unique_col = 1;
    for (int val = 2; val <= 2 * n; val++) {
        if (freq_cnt[val] == 1) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (a[i][j] == val) {
                        unique_row = i;
                        unique_col = j;
                    }
                }
            }
            break;
        }
    }

    for (int i = 1; i <= n; i++) {
        row_value[i] = freq_cnt[a[i][unique_col]];
    }
    for (int j = 1; j <= n; j++) {
        col_value[j] = freq_cnt[a[unique_row][j]];
    }

    int type = choose_answer_type();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (j > 1) cout << ' ';
            if (type == 0) {
                cout << value0(i, j);
            } else {
                cout << value1(i, j);
            }
        }
        cout << '\n';
    }

    return 0;
}

复杂度

统计频次需要扫描整张表。

恢复两种候选并比较也只需要扫描整张表。

时间复杂度为 $O(N^2)$ 。

空间复杂度为 $O(N^2)$ ，用于保存输入表。

总结

本题的突破口是“值重命名不会改变出现次数”。

加法表里每个值的频次具有固定结构，出现一次的两个值定位到极端角落。由这个角落所在行列的频次，就能恢复行值和列值；剩下的不确定性只有整体互补，再取字典序最小即可。

目录

题意

思路

代码

复杂度

总结