Table Recovery (USACO Silver 2025 January)

Table Recovery (USACO Silver 2025 January)

可以比较行与行，每行应该有N-1个数与下一行重合，所以这样可以把整个排列反推出来。具体来说：

  1. 一共2N-1个数，2个数只出现一次，
  2. 2个数只出现2次，在排列中与只出现一次的数相邻。
  3. 依次类推，在排列中间的1个数，出现在所有行中。
  4. 从两个可能的排列中选择一个字典序最小的。
3 4 2
5 2 3
6 3 5
  1. 在所有行中，出现一次的是4和6，所以 4 _ _ _ 6
  2. 出现两次的是2, 5， 所以 4 2 _ 5 6
  3. 出现三次的是3， 所以 4 2 3 5 6 -> 2 3 4 5 6

排列也可以倒过来，这里正序是字典序小的。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n;
int a[1001][1001];
int cnt[2001];
int perm[2001]; // i in final table maps to perm[i] in original table
 
int main() {
    scanf("%d",&n);
    for (int i=0; i<n; i++) 
        for (int j=0; j<n; j++) {
            scanf("%d",&a[i][j]);
            cnt[a[i][j]]++;
        }
    if (n == 1) {
        printf("2\n");
        return 0;
    }
    // 1st and last number should appear only once
    int first = 0, last = 0;
    for (int i=2; i<=2*n; i++) {
        if (cnt[i] == 1) {
            if (first == 0) first = i;
            else last = i;
        }
    }
    // find line with first and last
    int firstline, lastline;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            if (a[i][j] == first) firstline = i;
            if (a[i][j] == last) lastline = i;
        }
    }
    // fill out the permutation
    for (int j=0; j<n; j++) {
        perm[a[firstline][j]] = cnt[a[firstline][j]]+1;
        perm[a[lastline][j]] = 2*n-cnt[a[lastline][j]]+1;
    }
    // this should hold after the loop: perm[first] = 2; perm[last] = 2*n;
 
    // test which direction is lexically smaller
    if (perm[a[0][0]] > n+1 || perm[a[0][0]] == n+1 && perm[a[0][1]] > n+1) {
        // reverse the permutation
        for (int i = 2; i <= 2*n; i++)
            perm[i] = 2*n+2-perm[i];        // 2 becomes 2*n
    }
 
    // output
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            printf("%d%s", perm[a[i][j]], j==n-1?"":" ");
        }
        printf("\n");
    }
 
    return 0;
}