题解：P12051 [THUPC 2025 决赛] 排列与质数

· · 题解

我太菜了，一道绿题想不出来。还是 @zhikang 大神教我的。虽然他也看了官方题解。

首先锐评一下，这个构造题完全不同于正常的和出题人对脑电波的题，完全是个数学题，知道定理就一定会做，反之一定不会做。并且这个质数个数误导性也很强，差评。

思路

引理：伯特兰-切比雪夫定理：对于任意 n\ge 2 且 n 为正整数，在 (n,n\times 2) 中必至少存在一个质数。

那么先把 n\le 5 判掉，这个随便输出就行。令 k=\lfloor\dfrac{n}{3}\rfloor，根据定理，在 (k,k\times 2) 中必存在一个质数，令该质数 =x。按照如下方式构造：

p=x,x-1,x+1,x-2,x+2,\dots,x-m,x+m

直到 x-m\le 0 或 x+m>n 为止。显然这些项全部 =x，为质数。剩下的项乱填。

因此此题结论可以加强成 c_i 中至少存在 2\times\lfloor\dfrac{n}{3}\rfloor 个质数。

代码

代码实现非常简单。AC 记录。

// NOTE: "[EDIT]" means you should edit this part by yourself
#include <bits/stdc++.h>
#define MULTITEST
using namespace std;
typedef long long ll;
#define rep1(i,x,y) for (int i = (x);i <= (y);i++)
#define rep2(i,x,y) for (int i = (x);i >= (y);i--)
#define rep3(i,x,y,z) for (int i = (x);i <= (y);i += (z))
#define rep4(i,x,y,z) for (int i = (x);i >= (y);i -= (z))
#define cl(a) memset(a,0,sizeof(a))
const int N = 1e5 + 10;
int n,cnt,k,pos;
bool visited[N];
int ans[N];
bool prime(int x)
{
    for (int i = 2;i * i <= x;i++)
        if (x % i == 0)
            return false;
    return true;
}
void solve()
{
    cin >> n;
    if (n <= 5)
    {
        rep1(i,1,n)
            cout << i << ' ';
        cout << '\n';
        return;
    }
    k = n / 3;
    cl(visited);
    rep1(i,k,k * 2)
    {
        if (prime(i))
        {
            pos = i;
            break;
        }
    }
    cnt = 0;
    ans[++cnt] = pos;
    visited[pos] = true;
    rep1(i,1,min(pos - 1,n - pos))
    {
        ans[++cnt] = pos - i;
        ans[++cnt] = pos + i;
        visited[pos - i] = true;
        visited[pos + i] = true;
    }
    rep1(i,1,n)
        if (!visited[i])
            ans[++cnt] = i;
    rep1(i,1,n)
        cout << ans[i] << ' ';
    cout << '\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
#ifdef MULTITEST
    cin >> t;
#else
    t = 1;
#endif
    while (t--)
        solve();
}