构造题

这道题其实有点类似于素数环问题，一开始尝试使用 DFS 直接搜索。但其实没必要进行搜索，直接特殊构造即可。要求相邻的两个数相加为合数，在构造时选取最特殊的情况，相邻两个数为偶数即可。

如何构造使得相邻的两个数相加为偶数？最简单的方案是将 n 个数分为奇数和偶数两部分，两个奇数相加一定是偶数，两个偶数相加一定是偶数。唯一的特殊情况就是，奇数区域与偶数区域相邻的交接处，如何构造一个奇数和偶数相加，结果为合数。

最小的同时为奇数和合数的数是 1+8=9，因此当 n 大于 8 时可以直接按照这种方案进行构造，奇数区域与偶数区域相邻的交接处放置 1 和 8。对于 n 小于 8 时，直接构造特例单独判断即可。

Code

#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define Ciallo main
#define int long long
using namespace std;

int T, n;

inline void solve() {
    cin >> n;
    if(n <= 4)
        cout << -1 << endl;
    else if(n == 5)
        cout << "1 3 5 4 2" << endl;
    else if(n == 6)
        cout << "1 3 5 4 2 6" << endl;
    else if(n == 7)
        cout << "1 3 5 4 6 2 7" << endl;
    else if(n == 8)
        cout << "1 3 5 4 2 6 8 7" << endl;
    else {
        for(int i = 3; i <= n; i++)
            if(i % 2 == 1)
                cout << i << ' ';
        cout << 1 << ' ' << 8 << ' ';
        for(int i = 2; i <= n; i++)
            if(i % 2 == 0 and i != 8)
                cout << i << ' ';
        cout << endl;
    }
}

signed Ciallo() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    cin >> T;
    while(T--)
        solve();

    return 0;
}