P11672 [USACO25JAN] Table Recovery S 题解

· · 题解

由于笔者认为本题过于 Ad-hoc，故在此给出一种非官解的、硬分析的解法。笔者认为其更加系统且无脑。

首先考察一个表格可以通过操作 1,2 变换成原始矩阵的充要条件。

模拟这个过程，初始表格 A_{i,j}=i+j，经过一次行交换（不妨设交换了第 s 行和第 t 行），那么 A_{s,j}=t+j，而 A_{t,j}=s+j。

在这一部分，读者可以感觉到，将行重新排列后（不妨设新表格的第 i 行为原表格的第 p_i 行），A_{i,j}=p_i+j。

同理在此基础上模拟列交换（不妨设新表格的第 i 列为原表格的第 q_i 列），A_{i,j}=p_i+q_j。

这实际上是说，p,q 两排列可以与一个进行完行列交换的表格一一对应。

于是我们仅需检查能否将给定表格进行操作 3 后是否存在这样的 p,q 即可。

其次考察一个表格可以通过操作 3 变换成给定矩阵的充要条件。

那显然是，之前不同色的，后来仍不能同色；而之前同色的，后来必定同色。

这个条件第一眼好像没有提示我们任何东西。

你此时可以直接选择另一种思考角度，比如出现次数最小的数一定在原表格中是 1 或 2n+2，出现次数最大的数一定在原表格中是 n+1（此时你也可以发现原值为 n+1 的必定在每行每列均有恰好一个，故在确定 p,q 之一后就可以推出另一个，这是依据 A_{i,j}=p_i+q_j=n+1 的性质得到的。这实际上可以用于合法性检查）。

联系上面的那个结论，我们推广得：出现次数为 k 次的数在原表格中一定是 k+1 或 2n+1-k。

那么给定表格中的每个数有两种候选的原值，现在我们欲使其满足通过操作 1,2 变换成原始矩阵的充要条件的同时最小化字典序。

通过操作 1,2 变换成原始矩阵的充要条件仍然难以判定，那么我们考虑弱化条件，去考虑满足该条件的表格具有的性质。

感性理解层面，可以将这个充要条件理解为，两个一维数组搞出来了一个二维数组，且只与 i,j 相关。这说明其势必具有更加优秀的性质。

通过观察样例或直接进行分析，可以得出：位于同一列且位于相邻两行的数的差恒定，位于同一行且位于相邻两列的数的差恒定。

证明非常容易：A_{i,j}-A_{i-1,j}=p_i+q_j-p_{i-1}-q_j=p_i-p_{i-1}，与 j 完全无关。

在此基础上，结合“每个数有两种候选的原值”的推论，一个约束可以把 p_{i}-p_{i-1} 和 q_i-q_{i-1} 的可取的值缩小到不多于 4 个，其中有两对必为相反数。

举个例子：在第三组样例中，10 的原值是 5 或 9，而 5 的原值是 6 或 8，那么这给出，q_3-q_2=5-6 或 5-8 或 9-6 或 9-8。

那么就容易想到把所有对应约束取交，求得完全可行的 p_{i}-p_{i-1} 和 q_i-q_{i-1} 的取值。

而对于一个确定的 i，对 p_{i}-p_{i-1} 或 q_i-q_{i-1} 的限制互不相同。这意味着，所有约束可取的值取交后，真正可行的值恰为 2 个且互为相反数。如下图的橙色字体所示。

接下来你要做的就是，为这些橙色部分选择合适的正负号，使得生成的表格合法且字典序最小。

上图中画出的黄绿色路径代表了所有可行的转移，其具有启发意义。实际上就是走出一条合法的黄绿色路径且最小化字典序。比如答案走出的路径为：7\rightarrow 5\rightarrow 8\rightarrow 9\rightarrow 10\rightarrow 6。

事实上黄绿色路径的形式是非常单一的，在两数之间，其往往是两条或者四条边，且对于两数之间恰有两条边的情况，这两条边一定由不同的数指向不同的数，而对于两数之间恰有四条边的情况，这种情况很少，在一行中不会出现超过两次。因为若出现这种路径，则边的一侧必然为 n+1，然而给定表格中每行必然不存在重复数字，否则一定无解。或者你也可以直接把上图中红色和蓝色的 7 当成一个点，这样直接规避掉了两数之间恰有四条边的情况。

综上我们证明了，合法路径数量是 \mathcal{O}(1) 级别的，因此可以直接爆搜出来检查合法性。找到字典序最小的路径同样是简单的。

总结算法流程：

综上，时间复杂度 \mathcal{O}(N^2)。 

#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<array>
#include<unordered_map>
#include<vector>
#include<bitset>
#include<queue>
#include<set>
#include<map>
#include<ctime>
#include<random>
#include<numeric>
using namespace std;
#define int long long
#define ll long long
#define ull unsigned long long
#define lc (x<<1)
#define rc (x<<1|1)
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
const int Mx=2005;
int read(){
    char ch=getchar();
    int Alice=0,Aya=1;
    while(ch<'0'||ch>'9'){
        if(ch=='-') Aya=-Aya;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
        Alice=(Alice<<3)+(Alice<<1)+(ch^48),ch=getchar();
    return (Aya==1?Alice:-Alice);
}
int n;
int a[Mx][Mx],A[Mx][Mx];
int cnt[Mx];
int rev[Mx][2];
int d[Mx];
vector<pii>pos[Mx];
int D;
int p[Mx],q[Mx];
int vis[Mx];
int f[Mx][2];
void Check(){
    for(int i=1;i<=n+n+2;i++) vis[i]=0;
    int mn=1e9;
    for(int i=1;i<=n;i++){
        mn=min(mn,p[i]);
        if(vis[p[i]]) return;
        vis[p[i]]=1;
    }
    for(int i=1;i<=n;i++){
        p[i]-=mn-1;
    }
    for(pii _:pos[D]) q[_.fi]=n+1-p[_.se];
    for(int i=2;i<=n+n;i++){
        int v=q[pos[i][0].fi]+p[pos[i][0].se];
        for(pii _:pos[i]) if(q[_.fi]+p[_.se]!=v){
            for(int o=1;o<=n;o++) p[o]+=mn-1;
            return;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<n;j++){
            cout<<q[i]+p[j]<<" ";
        }
        cout<<q[i]+p[n]<<endl;
    }
    exit(0);
}
vector<int>now;
void dfs(int i,int op){
    int v=rev[a[1][i]][op];
    p[i]=v;
    if(i==n){
        Check();
        return;
    }
    for(int o=0;o<2;o++){
        int nxt=rev[a[1][i+1]][o];
        if(abs(nxt-v)==d[i]) dfs(i+1,o);
    }
}
signed main(){
    n=read();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            a[i][j]=A[i][j]=read();
            cnt[A[i][j]]++;
            pos[A[i][j]].push_back({i,j});
            if(cnt[A[i][j]]==n) D=A[i][j];
        }
    }
    for(int i=2;i<=n+n;i++){
        for(int j=2;j<=n+n;j++){
            if(cnt[i]==min(j-1,n+n-j+1)){
                rev[i][0]=j;
                rev[i][1]=n+n+2-j;
                break;
            }
        }
    }
    for(int i=1;i<n;i++){
        for(int j=1;j<=n+n+2;j++) vis[j]=0;
        for(int j=1;j<=n;j++){
            int w[4]={0};
            for(int x:{0,1}){
                for(int y:{0,1}){
                    int v=rev[a[j][i]][x]-rev[a[j][i+1]][y];
                    w[x*2+y]=v;
                }
            }
            for(int o=0;o<4;o++){
                bool ok=1;
                for(int t=o+1;t<4;t++){
                    if(w[o]==w[t]){
                        ok=0;
                        break;
                    }
                }
                if(ok&&w[o]>0) vis[w[o]]++;
            }
        }
        for(int j=1;j<=n+n+2;j++) if(vis[j]==n){
            d[i]=j;
            break;
        }
    }
    dfs(1,0),dfs(1,1);
    return 0;
}