Codeforces 1348B - Phoenix and B

这是我很喜欢的一张照片，雨后的街道，对面楼房挡住的刺眼的阳光，让万物有了这般颜色。

这道题不是一次性通过的，居然在第一个样例卡住了[捂脸]。第二个超时也是个小错误，反复查了很久，有些疏忽了。应该更加认真的，防止工作中也犯这类错误。

题目: Codeforces 1348B - Phoenix and Beauty

https://codeforces.com/problemset/problem/1348/B

这道题讲起来有些麻烦，我尽量讲清楚。

翻译

凤凰喜欢漂亮的数组，漂亮的数组就是所有 k 长度的子数组的和都是相同的值。

凤凰现在有一个长度为 n 的数组 a，他想在任意多个位置插入一些整数，使数组变成漂亮的数组。要求插入的数值在 1 和 n 之间，并且包含 1 和 n。他并不要求结果数组长度最短。

输入格式

第一行输入 t，表示用用例的数量。接下来输入 t 组用例。

输入一行 n 和 k，用空格分割。

输入一行数字，用空格分隔的 n 个数字。这个数组可能本身就是漂亮的数组。

输出格式

如果不能构建出漂亮的数组，直接输出单行的 -1。

如果可以构建出漂亮的数组，第一行输出数组的长度 m，第二行输出长度为 m 的数组，用空格分隔。

如果有多个答案，可以输出任意一个。可以保证，如果能构建出答案，答案的长度小于 10^4。

分析

写到这，感觉这是个翻译题，翻译这些好累。

这道题是个构建题，要求构建出符合要求的答案。符合要求的答案可以看出（我看了两个小时）是连续的重复字符串，循环节点就是 k，所以要求数字的种类不能超出k，而只要种类不超出k就可以证明，能构建出答案。

所以输入后，第一个判断就是不同数字的个数。如果大于k 直接输出 -1。

然后，如果不同的数字数量小于 k，则需要用 1 到 n的数字补齐。然后循环这个循环，并且判断输入的数组哪个位置的数字被使用了，例如：

4 3
1 2 2 1

不同的数字为：1 2
补充为：1 2 3

1 2 3 占用到 1 2
1 2 3 1 2 3 占用到 1 2 2
1 2 3 1 2 3 1 占用到 1 2 2 1

这就是构建的逻辑，花了两个小时找到的规律。

题目为什么保证 10^4 内可以构建出答案呢，因为最多100个数字，最坏情况需要重复 100 此循环节，就可以算出 100 * 100 = 10^4。算到这就能知道这是出题者的思路了。

代码(Python3)

通过记录

# # https://codeforces.com/problemset/problem/1348/B

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):
    line = input()
    arr = line.split(" ")
    n = int(arr[0])
    k = int(arr[1])
    line = input()
    arr = line.split(" ")
    num = []
    diff = []
    result = []
    for i in arr:
        integer = int(i)
        num.append(integer)
        if integer not in diff:
            diff.append(integer)
        
    if len(diff) > k:
        print(-1)
    else:
        while len(diff) < k:
            for i in range(1, n + 1):
                if i not in diff:
                    diff.append(i)
                    break
        pos = -1
        for i in num:
            while pos < len(diff):
                pos += 1
                if pos == len(diff):
                    pos = 0

                result.append(diff[pos])
                if diff[pos] == i:
                    break
        
        print(len(result))
        print(" ".join(str(i) for i in result))

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

by 费城的二鹏 2020.05.03 白山