好题没人写
题意
给定一个 \(N\times N\) 的矩阵，里面有 \(0\) 到 \(N\times N-1\) 的数，有两种操作，分别是将第一行重排然后放到最后一行，和把第一列重排放到最后一列。构造一种操作方案，使得操作完后矩阵有序。要求操作次数 \(<3N\)。
思路
先将每个数替换为它最终的位置的二元组 \((x,y)\)，表示这个数最终在 \(x\) 行 \(y\) 列。然后观察操作次数，发现是 \(3N\)，想到整体操作 \(3\) 次。然后可以发现，做 \(N\) 次 D 操作相当于把每行重排，做 \(N\) 次 R 操作相当于每列重排，考虑用 \(3\) 次这样的操作排序整个矩阵。
考虑逆向操作，假设最后一次将每行重排了得到有序矩阵，那么要求操作之前所有列已经有序。再往前一次操作一定是将每列重排，要求每列没有重复的 \(x\)。那么我们的问题转化为将每行重排，使得每列的 \(x\) 不重复。
考虑建图表示这个限制。建二分图，左部点为矩阵内点的坐标，右部点为每行的每个值，每个左部点向所在行的值连边。首先显然存在完美匹配，于是用 Hall 定理，有每个点集的邻域大小大于等于点集大小，整行的限制最严。逐列构造，从中任意取出一列的完美匹配，那么每行的点数和邻域大小都减一，仍然满足 Hall 定理，于是递归构造方案即可。
但是现在我们的操作次数是 \(3N\)，发现前 \(N\) 次操作中可以省掉最后一次，将最后一行换到第一行然后从第二行开始操作，求匹配的时候钦定第一行的点对应的值即可。由于 \(N\le9\)，求匹配时直接枚举排列就能通过。
代码
#include <bits/stdc++.h>
using namespace std;
constexpr int N=10,inf=0x3f3f3f3f;
int n;
pair<int,int>a[N][N],res[N];
int tmp[N],last[N];
int c[N][N],b[N][N];
struct Data{char t;vector<int>res;};
vector<Data>ans;
int calc(pair<int,int>x){return x.first*n+x.second;}
signed main(){clock_t _st=clock();ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n;for(int i=0;i<n;i++){for(int j=0;j<n;j++){int x;cin>>x;a[i][j]={x/n,x%n};}}for(int i=n-1;i;i--)swap(a[i],a[i-1]);ans.resize(3*n);for(int i=1;i<n;i++)ans[i].res.resize(n),ans[i].t='D';for(int i=0;i<n;i++)for(int j=0;j<n;j++)b[i][a[i][j].first]++;for(int j=0;j<n;j++){for(int i=0;i<n;i++)tmp[i]=i;do{bool fl=tmp[0]==a[0][j].first;for(int i=0;fl&&i<n;i++)if(!b[i][tmp[i]]){fl=0;break;}if(fl)break;}while(next_permutation(tmp,tmp+n));for(int i=0;i<n;i++)b[i][c[i][j]=tmp[i]]--;}for(int i=1;i<n;i++){for(int j=0;j<n;j++)last[j]=0;for(int j=0;j<n;j++){for(int k=last[c[i][j]];k<n;k++)if(a[i][k].first==c[i][j]){last[c[i][j]]=k+1,ans[i].res[j]=calc(a[i][k]);break;}}for(int j=0;j<n;j++)a[i][j]={ans[i].res[j]/n,ans[i].res[j]%n};}for(int j=0;j<n;j++){for(int i=0;i<n;i++)tmp[i]=i;stable_sort(tmp,tmp+n,[=](int x,int y){return a[x][j].first<a[y][j].first;});ans[j+n].t='R',ans[j+n].res.resize(n);for(int i=0;i<n;i++)res[i]=a[tmp[i]][j];for(int i=0;i<n;i++)ans[j+n].res[i]=calc(a[i][j]=res[i]);}for(int i=0;i<n;i++){for(int j=0;j<n;j++)tmp[j]=j;for(int j=0;j<n;j++)c[a[i][j].first][j]--;stable_sort(tmp,tmp+n,[=](int x,int y){return a[i][x].second<a[i][y].second;});ans[i+n*2].t='D',ans[i+n*2].res.resize(n);for(int j=0;j<n;j++)res[j]=a[i][tmp[j]];for(int j=0;j<n;j++)c[a[i][j].first][j]++;for(int j=0;j<n;j++)ans[i+n*2].res[j]=calc(a[i][j]=res[j]);}cout<<ans.size()-1<<'\n';for(int i=1;i<n*3;i++){cout<<ans[i].t<<' ';for(int x:ans[i].res)cout<<x<<' ';cout<<'\n';}clock_t _ed=clock();cerr<<(_ed-_st)*1.0/CLOCKS_PER_SEC<<'\n';return 0;
}