#luogu整理 CF1352G Special Permutation

(zay)讲的题

luogu CF1352G Special Permutation

题目描述

给定 (t) 组数据，每组数据包含一个整数 (n)。

对于每个整数 (n)，你需要输出一个长度为 (n) 的全排列 (p)，输出要求对于所有满足 (i in [1,n))的 (i)，有 (|p_i - p_{i+1}| in [2,4])，如果不存在，输出 (-1)，对于每一组数据，输出占一行。

如果有多组解，请输出其中任意一个。

样例

(in)

(out)

9 6 10 8 4 7 3 1 5 2 
-1
3 1 4 2 
5 3 6 2 4 1 
5 1 3 6 2 4 7 
13 9 7 11 8 4 1 3 5 2 6 10 12

思路：

先随便分析一下：对于n = 8，我们可以这样构造：

[1 3 5 7 4 8 6 2 ]

对于n = 7,我们可以这样构造：

[1 3 5 7 4 6 2 ]

那如果有数字(x = 8(or 7) + 2k (k in Z^*))，我们能够通过在两边加1、2，然后把整个数组的所有数字都加2构造出来。

对于小于等于6的n，我们可以直接next_permutation

(Code)

int t,n;
int a[2000];
int main(){
    // cout << "I AK IOI" << endl;
    // cout << "IOI AK I" << endl;
    // cout << "CYCYCYC" << endl;
    // cout << "YCYCYCY" << endl;
    cin >> t;
    while(t--){
        cin >> n;
        for(int i = 1;i <= n; i++) a[i] = i;
        if(n == 1){
            cout << -1 << endl;
            continue;
        }
        if(n <= 6){
            bool F = 0;
            do{
                bool flag = 0;
                for(int i = 2;i <= n; i++){
                    if(abs(a[i] - a[i-1]) > 4 || abs(a[i] - a[i-1]) < 2) flag = 1;
                }
                if(flag == 0) break;
                if(!next_permutation(a+1,a+1+n)){F = 1;break;}
            }while(1);
            if(!F){
                for(int i = 1;i <= n; i++) cout << a[i] << ' ';
                cout << endl;
            }else cout << -1 << endl;
            continue;
        }else if(!(n & 1)){
            for(int i = 1;i <= n/2; i++) cout << 2 * i-1 << ' ';
            cout << n-4 << ' ';
            cout << n << ' ';
            cout << n-2 << ' ';
            for(int i = n/2 - 3;i >= 1; i--) cout << i * 2 << ' ';
            cout << endl;
        }else{
            for(int i = 1;i <= n/2+1; i++) cout << 2 * i-1 << ' ';
            cout << n-3 << ' ';
            cout << n-1 << ' ';
            for(int i = n/2 - 2;i >= 1; i--) cout << i * 2 << ' ';
            cout << endl;
        }
    }
    return 0;
}