自动搬运

查看原文

来自洛谷，原作者为

	Lavaloon zzzzzzzzzzzz4

搬运于2025-08-24 23:09:22，当前版本为作者最后更新于2025-02-04 20:23:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

由于笔者认为本题过于 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;
}