题解：CF2171E Anisphia Wynn Palettia and Good Permutations

chengyifan91 · 2025-12-09 18:22:29 · 题解

首先，我们考虑构造一个 12 的排列 a_1,a_2,a_3\cdots,a_{12}，令 a_{13}=a_1+12,a_{14}=a_2+12，使得对于每个 1\le i\le 12， \gcd(a_i,a_{i+1})\in\{2,3\}、 \gcd(a_{i+1},a_{i+2})\in \{2,3\} 或 \gcd(a_i,a_{i+2})\in \{2,3\}。

通过打表可以构造出：1 2 4 5 6 3 7 9 12 11 10 8。

这样我们将排列 12,12 个分组，第 i 组的第 j 个数设置为 (i-1)k+a_j 即可，这样可以使得序列没有一个坏下标。

那么 n 可能不是 12 的倍数，此时我们就可以直接把后 n\bmod 12 个数按照顺序填写，算上序列的最后一个 8，最多会有 12 个数，则它们一定是按照偶数、奇数、偶数、奇数……这样排列的，可以看出只有奇数位置才会产生坏下标，最多只会有 6 个，至此我们做完了这道题。

#include<bits/stdc++.h>
#define _ 0
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n/12; i++) {
            int k = (i-1)*12;
            cout << k+1 << " " << k+2 << " " << k+4 << " " << k+5 << " " << k+6 << " " << k+3 << " " << k+7 << " " << k+9 << " " << k+12 << " " << k+11 << " " << k+10 << " " << k+8 << " ";
        }
        for (int i = n/12*12+1; i <= n; i++) cout << i << " ";
        cout << "\n";
    }
    return ~~(0^_^0);
}