也不知道什么时候给我发原创标识,我这个每天一个阅读量的公众号,是不是就不能发原创标识。。。
翻译
特别的组合
一个长度为 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 长春
网友评论