题解：P11357 [eJOI 2023] Square Grid Puzzle

· · 题解

~好题没人写~

同步发表于博客园

题意

给定一个 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;
}