题解：CF2118B 制作排列矩阵

NEKO_Daze · 2025-06-14 19:54:15 · 题解

洛谷CF2188B || CodeForces 2188 B

简要题意

给出一个 n\times n 的矩阵，其中 a_{i,j}=j。可以进行若干次操作，每次操作将某一行内的一段区间翻转，求使得矩阵每一列数字刚好满足 1 至 n 各出现一次的最少操作次数，并输出每一步的操作。

思路

考虑这么一种构造方法：

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

分析样例可知，我们只需要对每一行的 [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。

#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);
    }
}