题解：CF2118B 制作排列矩阵

简要题意

给出一个

n\times n

的矩阵，其中

a_{i,j}=j

。可以进行若干次操作，每次操作将某一行内的一段区间翻转，求使得矩阵每一列数字刚好满足

1

至

n

各出现一次的最少操作次数，并输出每一步的操作。

思路

考虑这么一种构造方法：

以

n=5

的情况为例，下面的矩阵显然符合要求：

1~5~4~3~2\\2~1~5~4~3\\3~2~1~5~4\\4~3~2~1~5\\5~4~3~2~1

分析样例可知，我们只需要对每一行的

[1,i]

和

[i+1,n]

这两个区间翻转即可。

在此基础上，我们发现当

i

为

1

，操作

[1, 1]

的区间长度为

1

，这样白白浪费了一次操作次数；同理，当

i

为

n

时，操作

[n+1,n]

是无意义的。因此最终答案为

2n-2

，操作方法为：

若 $i=1$ ，只执行 $1~2~n$ ；
若 $2\le i<n$ ，执行 $i~1~i$ 和 $i~i+1~n$ ；
若 $i=n$ ，只执行 $n~1~n$ 。

CPP

#include <bits/stdc++.h>
using namespace std;
int t, x;
int main()
{
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &x);
        printf("%d\n", 2*x-2);
        printf("%d %d %d\n", 1, 2, x);
        for (int i = 2; i < x; i++)
        {
            printf("%d %d %d\n%d %d %d\n", i, 1, i, i, i+1, x);
        }
        printf("%d %d %d\n", x, 1, x);
    }
}

题解：CF2118B 制作排列矩阵

文章操作

简要题意

思路

相关推荐

评论

题解：CF2118B 制作排列矩阵