19_07_08校内训练[grid]

Love The Way You Lie 2021-10-29 11:26 246阅读 0赞

# 题意 #

现有n\*m的长方形网格，每个格子中写着一个数，并构成了\[0,n\*m)的排列。每次可以将一行循环平移x格，也可以将一列循环平移x格。给出初始状态，给出一个到达给定状态的方案。n\*m<=10000，n,m>=2。

--------------------

# 思考 #

发现存在一种方法，能够使任意三个方格进行顺时针或逆时针改变位置。其中有一个方格的行和列由剩余两个方格决定。

这样一来，我们可以将前n-1行排成有序的，只剩下最后一行是无序的。

通过第一张改变位置的方式，我们也可以将同一行的任意三个方格进行循环平移。这样可以将最后一行的前m-2个排成有序的，剩下的两个不一定有序。

这种方法虽然不能判断出是否能够达到有序状态，但是在随机情况下会以一定概率达到。因此可以重复打乱原始序列，进行多次判断。

总复杂度O(Tnm)，T为随机次数。

--------------------

# 代码 #

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
      2 using namespace std;
      3 typedef unsigned long long ull;
      4 const int maxn=1E2+5;
      5 int X[maxn*maxn],Y[maxn*maxn];
      6 int a[maxn][maxn],n,m,wait[maxn];
      7 ull seed=233;
      8 inline int R(int l,int r)
      9 {
     10     seed^=seed<<13;
     11     seed^=seed>>7;
     12     seed^=1;
     13     return seed%(r-l+1)+l;
     14 }
     15 struct note
     16 {
     17     int opt,x,y;
     18     note(int a=0,int b=0,int c=0)
     19     {
     20         opt=a,x=b,y=c;
     21     }
     22 };
     23 vector<note>ans;
     24 inline void swap(int x1,int y1,int x2,int y2,int x3,int y3)
     25 {
     26     swap(X[a[x1][y1]],X[a[x3][y3]]);
     27     swap(Y[a[x1][y1]],Y[a[x3][y3]]);
     28     swap(X[a[x1][y1]],X[a[x2][y2]]);
     29     swap(Y[a[x1][y1]],Y[a[x2][y2]]);
     30     swap(a[x1][y1],a[x3][y3]);
     31     swap(a[x3][y3],a[x2][y2]);
     32     int len1=y2-y1,len2=x2-x3;
     33     if(len1<0)
     34         len1+=m;
     35     if(len2<0)
     36         len2+=n;
     37     ans.push_back(note(1,x1,len1));
     38     ans.push_back(note(2,y2,len2));
     39     ans.push_back(note(1,x1,m-len1));
     40     ans.push_back(note(2,y2,n-len2));
     41 }
     42 inline void swapRow(int x,int y1,int y2,int y3)
     43 {
     44     swap(x,y1,x,y2,x-1,y2);
     45     swap(x,y1,x,y2,x-1,y2);
     46     swap(x,y3,x,y2,x-1,y2);
     47 }
     48 void out()
     49 {
     50     for(int i=1;i<=n;++i,cout<<endl)
     51         for(int j=1;j<=m;++j)
     52         {
     53             cout.width(4);
     54             cout<<a[i][j];
     55         }
     56 }
     57 void work()
     58 {
     59     for(int i=1;i<=n-1;++i)
     60     {
     61         for(int j=1;j<=m;++j)
     62         {
     63             int num=(i-1)*m+j-1;
     64             if(a[i][j]==num)
     65                 continue;
     66             if(i==X[num])
     67                 swap(X[num],Y[num],i,j,i+1,j);
     68             else if(j==Y[num])
     69                 swap(X[num],j==1?m:1,X[num],Y[num],i,j);
     70             else
     71             {
     72                 int x=X[num],y=Y[num];
     73                 swap(x,y,x,j,i,j);
     74                 swap(x,y,x,j,i,j);
     75             }
     76         }
     77     }
     78     for(int i=1;i<=m-2;++i)
     79     {
     80         int num=(n-1)*m+i-1;
     81         if(a[n][i]==num)
     82             continue;
     83         if(Y[num]==i+1)
     84             swapRow(n,i,i+1,i+2);
     85         else
     86         {
     87             int G=Y[num];
     88             swapRow(n,i,i+1,G);
     89             swapRow(n,i,i+1,G);
     90         }
     91     }
     92 }
     93 void row(int x,int y)
     94 {
     95     ans.push_back(note(1,x,y));
     96     for(int i=1;i<=m;++i)
     97         wait[i]=a[x][i-y>=1?i-y:i-y+m];
     98     for(int i=1;i<=m;++i)
     99         a[x][i]=wait[i],Y[wait[i]]=i;
    100 }
    101 void col(int x,int y)
    102 {
    103     ans.push_back(note(2,x,y));
    104     for(int i=1;i<=n;++i)
    105         wait[i]=a[i-y>=1?i-y:i-y+n][x];
    106     for(int i=1;i<=n;++i)
    107         a[i][x]=wait[i],X[wait[i]]=i;
    108 }
    109 bool check()
    110 {
    111     for(int i=1;i<=n;++i)
    112         for(int j=1;j<=m;++j)
    113             if(a[i][j]!=(i-1)*m+j-1)
    114                 return false;
    115     return true;
    116 }
    117 int main()
    118 {
    119     srand(time(0));
    120     ios::sync_with_stdio(false);
    121     cin>>n>>m;
    122     for(int i=1;i<=n;++i)
    123         for(int j=1;j<=m;++j)
    124         {
    125             cin>>a[i][j];
    126             X[a[i][j]]=i,Y[a[i][j]]=j;
    127         }
    128     int T=10;
    129     while(T--)
    130     {
    131         work();
    132         if(check())
    133             break;
    134         int t=10;
    135         row(n,1);
    136     }
    137     if(!check())
    138     {
    139         cout<<-1<<endl;
    140         return 0;
    141     }
    142     cout<<ans.size()<<endl;
    143     for(int i=0;i<ans.size();++i)
    144         cout<<ans[i].opt<<" "<<ans[i].x<<" "<<ans[i].y<<endl;
    145     return 0;
    146 }

NOTE：最好要多随机几行和几列，防止极端数据。

转载于:https://www.cnblogs.com/GreenDuck/p/11152115.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211029/21712e2df2e745e986af1c8a048065f9.png