题解 P8221 [WFOI - 02] I wanna reverse to reserve（翻转）

· · 题解

题意

对输入矩阵进行行/列翻转操作，使其变换成行值递增且列值相等的矩阵，操作数不超过 n×m，输出操作。

思路

这篇题解为赛时思路，灵感来源于魔方，并且部分解释与魔方相关。

下文可能看上去很复杂很高级，其实一点即通，毫无思维难度可言。

Step 1 性质

不难发现，对于任意一个点 (x,y) ，经过行/列翻转操作之后，只可能处于四个位置，分别见下图；

\begin{bmatrix} (x,y) & (x,m+1-y) \\ (n+1-x,y) & (n+1-x,m+1-y) \end{bmatrix}

能看出，单进行行翻转操作，就相当于上述位置左右互换；单进行列翻转操作，就相当于上述位置上下互换。

现称这四个相对位置为一组变换位，其值在翻转变换中不会改变。

将题意再翻译一下，可以得出最终需要将矩阵中所有的变换位翻转成同一形式。若用 0 和 1 标注目标变换位的值格式，即为下式。具体地说，0 代表值 y0，1 代表值 y1。

\begin{bmatrix} (x0,y0) & (x0,y1) \\ (x1,y0) & (x1,y1) \end{bmatrix}= \begin{bmatrix} 0 & 1 \\ 0 & 1 \end{bmatrix}, \begin{pmatrix} x0+x1=n+1 \\ y0+y1=m+1 \end{pmatrix}

由上文性质和值格式可得，若单组变换位满足其中两值等于 y0、两值等于 y1，即可通过翻转变换得到目标变换位，否则不可能（直接输出“NO”就行了）。而满足条件的变换位又有以下五种形式：

\begin{bmatrix} 0 & 0 \\ 1 & 1 \end{bmatrix}, \begin{bmatrix} 1 & 1 \\ 0 & 0 \end{bmatrix}, \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}, \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}, \begin{bmatrix} 1 & 0 \\ 1 & 0 \end{bmatrix}

下面我们分类讨论将这五种形式翻转成目标变换位的操作方案。

Step 2 方案

对于一组变换位，定义 U,D,L,R 分别为翻转上行、下行、左列、右列，翻转完成后值会对调。（有魔方基础的应该能很快很顺的理解）

在考虑单组变换位的翻转方案时，有两点需要注意：

  1. 行翻转次数为偶数，列翻转次数不限。因为奇数次行反转会影响同行其它已转好的变换位元素顺序，而已转好的变换位列值相等，翻转没有影响。

  2. 翻转次数尽量控制在 4 次及以内。因为变换位组数为 \frac 1 4 (n×m)，而总操作次数最多为 n×m，均摊下每组为 4 次。

接下来在满足上述条件的前提下考虑前文五种情况（从左到右分别对应上面的矩阵）：

想要真正理解方案妙处的可以手动模拟推演过程（毕竟是结论题）。

至此思路的核心要素已经叙述完毕，然后就是代码实现和细节处理了。

P.S.听说变换完后还可以对操作序列离线处理压一下操作数，或许有所帮助，不过在这里就没必要。

代码

记录

  1. 枚举变换位可先枚举左上位置点再推导，参考 main 函数里的 for 循环；

  2. 处理变换位可先用位运算提取信息存入二进制再判断，参考 deal 函数；

  3. 注意 NO 情况的判断有两处，第一处判断值是否符合，第二处判断个数是否满足，见 flag 变量；

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
const int N=101;
int n,m,cnt,a[N][N];//基础矩阵
string str[N][N];//操作序列
bool flag;//NO标记
inline void fip(int &rer){//快读
    register char ch;
    for(ch=0;ch<'0'||ch>'9';ch=getchar());
    for(rer=0;ch>='0'&&ch<='9';ch=getchar())
        rer=(rer<<3)+(rer<<1)+(ch^48);
}
void reverse(int col){//列翻转
    register int i,j;
    for(i=1,j=n;i<j;++i,--j)
        swap(a[i][col],a[j][col]);
}
void deal(int x0,int y0,int x1,int y1){//变换位处理
    register int s=0;
    s|=(a[x0][y0]==y0? 0:1),s<<=1;
    s|=(a[x1][y0]==y0? 0:1),s<<=1;
    s|=(a[x0][y1]==y0? 0:1),s<<=1;
    s|=(a[x1][y1]==y0? 0:1);
    if(s==0x3)return;//0011
    else cnt+=4;
    switch(s){
        case 0x5:str[x0][y0]="DRDR";return;//0101
        case 0x6:str[x0][y0]="RDRD";return;//0110
        case 0x9:str[x0][y0]="RURU";return;//1001
        case 0xA:str[x0][y0]="URUR";return;//1010
        case 0xC:reverse(y0),reverse(y1);
                 str[x0][y0]="ULRU";return;//1100
        default:flag=true;return; 
    }
}
void print(int x0,int y0,int x1,int y1){//操作输出
    for(auto i:str[x0][y0]){
        if(i=='U')printf("0 %d\n",x0);
        if(i=='D')printf("0 %d\n",x1);
        if(i=='L')printf("1 %d\n",y0);
        if(i=='R')printf("1 %d\n",y1);
    }
}
int main(){
    register int i,j,k;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;++i)
    for(j=1;j<=m;++j)
        fip(k),a[i][j]=k,
        flag|=(k!=j&&k!=m+1-j);
    if(flag){puts("NO");return 0;}
    for(i=n>>1;i>=1;--i)
    for(j=m>>1;j>=1;--j)
        deal(i,j,n+1-i,m+1-j);
    if(flag){puts("NO");return 0;}
    printf("YES\n%d\n",cnt);
    for(i=n>>1;i>=1;--i)
    for(j=m>>1;j>=1;--j)
        print(i,j,n+1-i,m+1-j);
    return 0;
}

不错的月赛题目:)