题目概述
给你一个$n \times m$的矩阵，你每次可以选择一列，这个矩阵的每一行会按照这一列进行稳定排序（相同元素相对位置不变），问$A$矩阵如何进行操作能变成$B$矩阵.
数据范围
分析与解
这个题还是从最终的局面入手考虑。
我们考虑B矩阵的某一列$p$，如果这一列是有序的，那么不妨假定这一列进行了排序操作。考察这一列的每个相邻行，如果某个相邻行的两个元素并不相等，那么意味着这两个行的位置由这次排序唯一确定。
那么我们放眼于这两行的其他列。如果其他列$q$在这两行是逆序的，意味着一种可能：就是之前$q$列发生过排序，本来是顺序的，但是由于$p$列后来的排序导致$q$列某些位置逆序了。由此可见，如果$q$列要进行排序，那么必须在$p$列之前。这样以来，我们就得到了不同列排序的依赖关系。我们可以用一个拓扑排序来得到所有列的依次排序顺次。
需要注意的是，$p$列相邻行的位置确定只能用一次，之后拓扑过程中其他列即便也是这两行有不等元素的顺序关系，也不能减少依赖了。这是因为，相当于由$p$列遍历的其他列的逆序关系指定由$p$列的排序来造成的。
最终我们在A数组上验证一下能不能通过顺次执行这些排序来得到B即可。显然，执行的次数不会超过总列数$m$。排序过程相当于手写桶排序。
代码
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
| #include <bits/stdc++.h>
using namespace std;
int mread() {
int ret=0,f=1;
char c=getchar();
while(c<'0' || c>'9') {
if(c=='-')f=-1;
c=getchar();
}
do {
ret=ret*10+c-'0';
c=getchar();
} while('0'<=c && c<='9');
return ret*f;
}
#define MAXN 2020
vector<int> G[MAXN],srt;
queue<int> Q;
int n,m;
int a[MAXN][MAXN],b[MAXN][MAXN];
int deg[MAXN];
bool vis[MAXN];
int pos[MAXN][MAXN];
int num[MAXN];
int main() {
int u,k;
n=mread(),m=mread();
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)a[i][j]=mread();
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)b[i][j]=mread();
for(int i=1; i<=m; i++) {
for(int j=1; j<n; j++)
if(b[j][i] > b[j+1][i]) {
G[j].push_back(i);
deg[i]++;
}
if(!deg[i])Q.push(i);
}
while(!Q.empty()) {
u=Q.front();
Q.pop();
srt.push_back(u);
for(int i=1; i<n; i++) {
if(!vis[i] && b[i][u] < b[i+1][u]) {
for(auto v:G[i]) {
deg[v]--;
if(!deg[v])
Q.push(v);
}
vis[i]=true;
}
}
}
reverse(srt.begin(),srt.end());
for(int i=1; i<=n; i++)pos[0][i]=i;
k=srt.size();
for(int i=0; i<k; i++) {
u=srt[i];
for(int j=1; j<=n; j++)num[j]=0;
for(int j=1; j<=n; j++)num[a[pos[i][j]][u]]++;
for(int j=1; j<=n; j++)num[j]+=num[j-1];
for(int j=n; j>=1; j--)pos[i+1][num[a[pos[i][j]][u]]--]=pos[i][j];
}
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
if(a[pos[k][i]][j]!=b[i][j]) {
printf("-1\n");
return 0;
}
printf("%d\n",k);
for(auto x : srt)printf("%d ",x);
printf("\n");
return 0;
}
|