BGN77 构造数列

思路

这题让你构造一个长度为 的数组，前一半是互不相同的偶数，后一半是互不相同的奇数，且两半的和相等。

先想一个关键问题：前半部分的和与后半部分的和，奇偶性能对上吗？

取最小的 个偶数和奇数来分析：

  • 个偶数的和一定是偶数（偶数之和必为偶数）
  • 个奇数的和呢？ 个奇数相加，当 为偶数时和为偶数， 为奇数时和为奇数

不管你怎么换数字，只要保持偶数/奇数的身份不变，奇偶性就不会变。所以：

  • 当 是奇数时（即 ），偶数和是偶数、奇数和是奇数，两者永远不可能相等，输出 NO
  • 当 是偶数时（即 ），两边的和奇偶性相同，有可能构造出来

那 呢？，是奇数情况，直接 NO。

怎么构造？

设 （ 为偶数）。

取最小的 个偶数：，和为 。

取最小的 个奇数：，和为 。

最后一个奇数设为 ，需要满足：

$$

来验证一下 的合法性：

  1. 是奇数吗？ 是偶数， 是偶数， 是奇数。没问题。
  2. 和前面的奇数重复吗？ 前面最大的奇数是 ，而 （当 时），不会重复。
  3. 和偶数重复吗？ 是奇数，偶数们是偶数，不可能重复。

完美！直接输出就行。

以 为例：，偶数 ，和 ；奇数 ，和 ；最后一个奇数 。输出 2 4 6 8 1 3 5 11，和样例一致。

代码

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

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        int half = n / 2;
        if (half % 2 != 0) {
            printf("NO\n");
        } else {
            printf("YES\n");
            long long evenSum = 0;
            for (int i = 1; i <= half; i++) {
                printf("%d", 2 * i);
                if (i < half) printf(" ");
                evenSum += 2 * i;
            }
            long long oddPartial = 0;
            for (int i = 0; i < half - 1; i++) {
                int val = 2 * i + 1;
                printf(" %d", val);
                oddPartial += val;
            }
            printf(" %lld\n", evenSum - oddPartial);
        }
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            int n = sc.nextInt();
            int half = n / 2;
            if (half % 2 != 0) {
                sb.append("NO\n");
            } else {
                sb.append("YES\n");
                long evenSum = 0;
                for (int i = 1; i <= half; i++) {
                    if (i > 1) sb.append(' ');
                    sb.append(2 * i);
                    evenSum += 2 * i;
                }
                long oddPartial = 0;
                for (int i = 0; i < half - 1; i++) {
                    int val = 2 * i + 1;
                    sb.append(' ').append(val);
                    oddPartial += val;
                }
                sb.append(' ').append(evenSum - oddPartial).append('\n');
            }
        }
        System.out.print(sb);
    }
}

import sys
input = sys.stdin.readline

T = int(input())
out = []
for _ in range(T):
    n = int(input())
    half = n // 2
    if half % 2 != 0:
        out.append("NO")
    else:
        out.append("YES")
        evens = [2 * i for i in range(1, half + 1)]
        even_sum = sum(evens)
        odds = [2 * i + 1 for i in range(half - 1)]
        odd_partial = sum(odds)
        last = even_sum - odd_partial
        out.append(' '.join(map(str, evens + odds + [last])))
print('\n'.join(out))

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', (line) => lines.push(line.trim()));
rl.on('close', () => {
    const T = parseInt(lines[0]);
    const out = [];
    for (let t = 1; t <= T; t++) {
        const n = parseInt(lines[t]);
        const half = Math.floor(n / 2);
        if (half % 2 !== 0) {
            out.push("NO");
        } else {
            out.push("YES");
            const evens = [];
            let evenSum = 0;
            for (let i = 1; i <= half; i++) {
                evens.push(2 * i);
                evenSum += 2 * i;
            }
            const odds = [];
            let oddPartial = 0;
            for (let i = 0; i < half - 1; i++) {
                const val = 2 * i + 1;
                odds.push(val);
                oddPartial += val;
            }
            odds.push(evenSum - oddPartial);
            out.push([...evens, ...odds].join(' '));
        }
    }
    console.log(out.join('\n'));
});

复杂度分析

  • 时间复杂度：，每组测试用例线性构造。
  • 空间复杂度：（C++ 版本），（Java 版本用了 StringBuilder）。