题解：CF2118B Make It Permutation

· · 题解

简单找规律题

大体思路

首先我们可以发现，对于第 i 行，我们只需要进行一次 i 1 i 和一次 i i+1 n（若 i<n 才执行此操作） 即可，当然这个是我们找规律的结果，所以我们还是需要简单求证的。

证明

可以发现，先进行操作，我们如果只看对角线左下方的三角形，那么会得到如此图形：

我们可以发现第 i-1 列的数字数量永远比 i 上的多，那么也就是说如果我们在这个三角形的第 i-1 列上可以放数 x 使得其不重复，那么第 i 列也可以。

那么通过这个想法我们就可以把右上角剩下的三角形向右"平移一位"，例如 n=4 时平移后就是：

那么此时我们可以考虑答案 n 从答案 n-1 是如何通过转移得到的。首先我们对于 n-1 的答案矩阵进行一次平移，那么将会出现一个形如对角线的空位置，此时我们可以在那里填入 n，可以发现这个操作是我们操作 i i+1 n 可以做到的，那么接下来还有第 n 行没有填入，我们考虑进行平移后第 i 列缺少了哪个数字，可以发现由于我们上三角第 i 列与 i-1 列的数字个数相差 1 且相差的那个数字恰好是 n-i+1 那么我们只需要在第 n 行按顺序填入 n-i+1 就可以了，这个操作与我们的 i 1 i 操作对应，所以我们一定可以使用这种操作完成任务。

代码

#include<bits/stdc++.h>
using namespace std;
int T;
int main(){
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        cout<<2*n-1<<endl;
        for(int i=1;i<=n;++i){
            if(i<n)
                cout<<i<<" "<<i+1<<" "<<n<<endl;
            cout<<i<<" "<<1<<" "<<i<<endl;
        }
    } 
    return 0;
}