Codeforces 1352G - Special Permu

也不知道什么时候给我发原创标识，我这个每天一个阅读量的公众号，是不是就不能发原创标识。。。

翻译

特别的组合

一个长度为 n 的数组组合，内容是 1 到 n，并且每个元素都不相同。

给一个数字 n (n >= 2)，组合一个特别的数组，每个元素和邻居元素的差值为2到4，包含边界。

输出任何一种组合，后者输出不能构造。

输入格式

输入一个整数 t，接下来输入 t 组测试用例。

每个测试用例输入一个数字 n。

输出格式

每个测试用例输出一行组合，用空格分隔。

分析

当 n = 2 时，只能组合成 1 2，不符合要求，输出 -1
当 n = 3 时，组合成 1 2 3, 1 3 2, 2 1 3 ，均不符合要求， 输出 -1
当 n = 4 时，组合成 3 1 4 2 符合要求
当 n = 5 时，可以在 4 的基础上添加 5，3 1 4 2 5
当 n = 6 时，6 3 1 4 2 5
。。。

依次类推，反复往两边添加数组，为了提升数组插入的性能，可以现在尾部添加奇数，然后翻转数组，再次插入偶数。

一道很简单的构造题目。

代码(PyPy3)

image.png

# https://codeforces.com/problemset/problem/1352/G

import sys

# sys.stdin = open(r"./file/input.txt", 'r')
# sys.stdout = open(r"./file/output.txt", 'w')

t = int(input())

for _ in range(t):
    n = int(input())
    result = [3, 1, 4, 2]
    for i in range(5, n + 1):
        if i % 2 == 1:
            result.append(i)

    result.reverse()
    for i in range(5, n + 1):
        if i % 2 == 0:
            result.append(i)

    if n >= 4:
        print(" ".join(str(i) for i in result))
    else:
        print(-1)

更多代码尽在 https://github.com/Tconan99/Codeforces

by 费城的二鹏 2020.05.14 长春