美文网首页
Codeforces 1352G - Special Permu

Codeforces 1352G - Special Permu

作者: 费城的二鹏 | 来源:发表于2020-05-19 11:58 被阅读0次

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

    翻译

    特别的组合

    一个长度为 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 长春

    相关文章

      网友评论

          本文标题:Codeforces 1352G - Special Permu

          本文链接:https://www.haomeiwen.com/subject/vdstohtx.html