题解：CF2037C Superultra's Favorite Permutation

一道简单的构造题，建议评橙。

Description

对于每个 n 构造一个 1-n 的排列，使每两个相邻元素何均为合数。

Solution

小学数学学过，除了 2 以外所有偶数都是合数。

于是我们可以优先让和之间为偶数。若 (a+b)\bmod 2=0，则 当且仅当 下面两种情况:

• a\bmod 2=0$ 且 $b\bmod 2=0
• a\bmod 2=1$ 且 $b\bmod 2=1

因此，我们可以先输出所有奇数，再输出所有偶数。但这时就出现了一个问题：奇数与偶数中间的和。于是，我们可以 固定两个数，使他们相加为合数，且一个是奇数，一个是偶数。其中最小的一个即为 (4,5)。而这两个数在分别输出奇数与偶数时跳过即可。

思路很显然，接下来是无解的情况，由于最小的中间衔接部分的两个数中最大的为 5。所以 n<5 的时候输出无解。

Code

请勿抄袭。

#include <bits/stdc++.h>
using namespace std;
int t,n;
void solve()
{
    cin >> n;
    if (n < 5)
    {
        cout << "-1\n";
        return ;
    } //若 n < 5，输出无解
    for (int i = 1;i <= n;i = i + 2)
    {
        if (i != 5) cout << i << ' ';
    } //输出除 5 以外的奇数
    cout << "5 4 "; //输出 (5,4)
    for (int i = 2;i <= n;i = i + 2)
    {
        if (i != 4) cout << i << ' ';
    } //输出除 4 以外的偶数
    cout << '\n';
}
int main()
{
    cin >> t;
    while (t--)
    {
        solve();
    }
  return 0;
}