Codeforces 1348B - Phoenix and 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 白山
