题解 | #构造数列#

问题的核心在于奇偶性对求和的影响。

设 ，即前半部分和后半部分各包含 个元素。

• 前半部分（偶数部分）的和： 任意 个偶数的和一定是偶数。因为偶数可表示为 ，其和为 ，必然能被 2 整除。
• 后半部分（奇数部分）的和： 任意 个奇数的和的奇偶性，取决于 的奇偶性。
  • 若 是偶数，则（奇数 偶数个）的和为 偶数。
  • 若 是奇数，则（奇数 奇数个）的和为 奇数。

存在性判别

题目要求“前半部分和”等于“后半部分和”。 由于“前半部分和”恒为偶数，那么“后半部分和”也必须是偶数。 根据上述分析，后半部分由 个奇数组成，其和为偶数的充要条件是 必须为偶数。

推导：

结论：

• 若 （即 不能被 4 整除），则不可能构造出满足条件的数组，直接输出 NO。
• 若 ，则一定存在解，输出 YES 并进行构造。

若满足 ，我们采用 贪心构造法 配合 补差法 来构造数组。

构造思路

为了保证元素互不相同且尽可能小（避免越界），我们从最小的正偶数和正奇数开始构造。

1. 构建前半部分（偶数）： 直接取最小的 个正偶数：。 这部分的和为 。

2. 构建后半部分（奇数）： 我们也尝试取最小的 个正奇数：。 这部分的和为 。

3. 计算差值与修正： 比较上述两组序列的和： 这意味着，如果我们直接取最小的 个奇数，其总和比偶数部分少了 。

   补差策略： 为了使总和相等，我们需要将奇数部分的总和增加 。为了保持前 个奇数尽可能小且互不相同，我们保持前 个奇数不变，将所有的差值 全部加到最后一个奇数上。

   • 前 个奇数：。
   • 第 个奇数（调整后）：原定值 加上差值 ，即 。

正确性验证

• 奇偶性： 是奇数吗？ 由于 ，故 是偶数。 ，偶数 必然是 奇数。符合条件。
• 元素唯一性：调整后的最后一个奇数是否会与前面的奇数重复？ 调整后的值为 。 前面的最大奇数为 。 显然，当 时，。因此所有奇数互不相同，且奇数与偶数天然不相同。符合条件。

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        int n;
        cin >> n;
        if (n % 4 != 0) {
            cout << "NO\n";
            continue;
        }

        cout << "YES\n";

        for (int i = 1; i <= n / 2; i++) {
            cout << (i * 2) << " ";
        }
        for (int i = 1; i <= n / 2; i++) {
            if (i < n / 2) {
                cout << (i * 2 - 1) << " ";
            } else {
                cout << (i * 2 - 1 + n / 2);
            }
        }
        cout << "\n";
    }
}