解析

神仙題
我想到了一部分，但是由于沒想到倒著做，后面越想越復雜…

本題的關鍵是要倒著想
考慮最后一次排序的列x
必須是單調不增的
否則直接錯
然后倒數第二列y
必須在x列相等的段內單調不增，因為這些地方x無法起到排序的作用
同理再到倒數第三列…

那么這個怎么實現呢？
拓撲排序！
考慮一列中肯定有一些相鄰的逆序對
如果這個逆序對已經被前面的覆蓋過，就沒關系
一個列如果所有的逆序對都被覆蓋，就可以使用了

考慮將列操作和相鄰行分別看作點，連邊即可
逆序對只要被遍歷到即可入隊
列操作只有入度減為0才能入隊

代碼

#include<bits/stdc++.h>const int N=1550; const int mod=1e9+7; #define ll long long #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) using namespace std; inline ll read() {ll x(0),f(1);char c=getchar();while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }const int key=13331;int n,m;struct node{int to,nxt; }p[N*N*2]; int fi[N<<2],cnt; inline void addline(int x,int y){p[++cnt]=(node){y,fi[x]};fi[x]=cnt;return; } bool vis[N<<2]; int du[N<<2],q[N<<2],st,ed;int a[N][N],b[N][N]; ull h1[N],h2[N]; void Hash(){for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) h1[i]=h1[i]*key+a[i][j];}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) h2[i]=h2[i]*key+b[i][j];}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(b[j][m+1]) continue;if(h1[i]==h2[j]){b[j][m+1]=i;break;}if(j==n){printf("-1\n");exit(0);}}}return; } int ans[N],num; int main(){ #ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout); #endifmemset(fi,-1,sizeof(fi));cnt=-1;n=read();m=read();for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) a[i][j]=read();}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) b[i][j]=read();}Hash();//debug("OK\n");//for(int i=1;i<=n;i++){//for(int j=1;j<=m+1;j++) printf("%d ",b[i][j]);//putchar('\n');//}for(int i=1;i<n;i++){for(int j=1;j<=m+1;j++){if(b[i][j]<b[i+1][j]) addline(j+n,i);else if(b[i][j]>b[i+1][j]){//printf("(%d %d)\n",i,j);addline(i,j+n),du[j+n]++;}}}st=1;for(int i=n+1;i<=n+m+1;i++){//printf("i=%d du=%d\n",i-n,du[i]);if(!du[i]) q[++ed]=i,vis[i]=1;}while(st<=ed){int now=q[st++];if(now==n+m+1) break;if(now>n&&now<=n+m) ans[++num]=now-n;for(int i=fi[now];~i;i=p[i].nxt){int to=p[i].to;if(vis[to]) continue;if(to<n) q[++ed]=to,vis[to]=1;if(to>n&&--du[to]==0) q[++ed]=to,vis[to]=1;}}if(!vis[n+m+1]){printf("-1\n");return 0;}else{printf("%d\n",num);while(num) printf("%d ",ans[num--]);return 0;}return 0; } /*5 37 1 4 1 9 1 3 5 31 1 4 22 3 5 */

總結

以上是生活随笔為你收集整理的CF1500C Matrix Sorting（拓扑排序）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。