牛客周赛 Round 126(ABCDE)

A.小红的顺子构造

题目详情：

小红定义 k 张牌为「顺子」：当这些牌从小到大排序后，对于 1～k-1 的每个 i，都满足 ai​+1=ai+1​（即连续的 k 个整数）。例如，{4,3,6,7,5} 是顺子（排序后为 3,4,5,6,7）。

请构造一个由 5 张牌组成的、包含数字 x 的顺子，输出这 5 张牌（任意顺序）。

输入描述：

第一行输入一个整数 x (1≤x≤10)。

输出描述：

在一行上以任意顺序输出五个整数，代表包含 x 的 5 张牌的顺子。

代码：

x=int(input())
for i in range(x,x+5):
print(i,end=" ")

B.小红的字符串构造（easy）

题目详情：

本题为简单版本，保证给定数组中的「01 串」两两有前缀关系。

• 「01 串」定义：仅包含字符 0 和 1 的字符串。
• 给定长度为 n 的 01 串数组 s（特殊性质：任意 i,j，总有 si​ 是 sj​ 的前缀或 sj​ 是 si​ 的前缀）。

• 需构造字符串 s′，使得 s 中恰好有 k 个 01 串（可以相同）是 s′ 的前缀。

【名词解释】

前缀：从字符串开头到任意位置的子串（例如 “1234” 的前缀有 “1”“12”“123”“1234” 和空串）。

输入描述：

输出描述：

• 若不存在合法字符串，输出 -1；

• 否则输出构造的字符串 s′ (1≤∣s′∣≤10^6)，需满足 s 中恰好有 k 个 01 串是 s′ 的前缀。

代码：

import sys
def demo():
data = sys.stdin.read().split()
n, k = map(int,data[:2])
aList = data[2:]
aDict = {}
for i in aList:
aDict[i] = aDict.get(i, 0) + 1
bList = sorted(aDict.keys())
num = 0
for x in bList:
num += aDict[x]
if num == k:
return x
elif num > k:
return -1
print(demo())

C.小红的好数组构造

题目详情：

小红定义一个数组是好数组，当且仅当数组中每个数都出现了偶数次，且所有元素均为正整数。特殊的，{}（空数组）也是一个好数组。

现在小红想要找到一个长为 n 的数组，使得：

• 对于任意整数 d (0≤d<k)，删除数组中任意 d 个下标后，得到的数组都不是好数组；

• 存在一种删除 k 个下标的方式，使得得到的数组是好数组。

请你帮帮她。

输入描述：

第一行输入两个整数 n,k (1≤n≤2×10^5,0≤k≤n)。

输出描述：

如果不存在这样的数组，请输出 −1；否则请输出 n 个整数 a1​,a2​,…,an​ (1≤ai​≤10^9)，代表所求的数组。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

代码：

n,k=map(int,input().split())
if (n-k)%2==1:
print(-1)
else:
aList=[int(x) for x in range(1,k+1)]
for i in range(k+1,k+1+(n-k)//2):
aList+=[i,i]
print(' '.join(map(str,aList)))

D.小红的左看右看构造

题目详情：

在此题中，我们认为数组以从左到右的顺序排列。对于一个数组 a，小红定义「左看」与「右看」为：

• 「左看」：从左到右依次记录数组中满足 “大于其左侧所有数” 的数组成的新数组（按取出顺序）。
• 「右看」：从右到左依次记录数组中满足 “大于其右侧所有数” 的数组成的新数组（按取出顺序）。

如，设一个数组 b={2,3,4,3,5,1}，则「左看」为 {2,3,4,5}，「右看」为 {1,5}。

小红给出了一个长为 x 的数组 c 与一个长为 y 的数组 d，他希望小苯能构造一个长为 n 的数组，使得 c 是其「左看」，d 是其「右看」。请你帮帮小苯。特殊的，保证数组 c，d 严格单调递增。

输入描述：

第一行输入三个整数 x,y,n (1≤x,y,n≤2×10^5)。第二行输入 x 个整数 ci​ (1≤ci​≤2×10^5)。第三行输入 y 个整数 di​ (1≤di​≤2×10^5)。

输出描述：

如果不存在合法的构造，请输出 −1，否则输出 n 个正整数，代表所构造的数组。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

代码：

x,y,n=map(int,input().split())
aList=[int(x) for x in input().split()]
bList=[int(x) for x in input().split()]
if aList[-1]!=bList[-1] or x+y-1>n:
print(-1)
else:
cList=aList[:-1]+[aList[-1]]*(n-x-y+2)+bList[:-1][::-1]
print(' '.join(map(str,cList)))

E.小红的完全平方数构造

题目详情：

小红拿到了一个整数 n，她想要在这个整数的十进制表示末尾拼接一个非空的数字串（如将 123 修改为 1230987654），使得修改过后的新数 n′ 是一个完全平方数，请你帮帮她。

【名词解释】

完全平方数：一个数如果可以表示为某个整数的平方，那么这个数就是完全平方数。前十个完全平方数是 0, 1, 4, 9, 16, 25, 36, 49, 64, 81。

输入描述：

每个测试文件均包含多组测试数据。第一行输入一个整数 T (1≤T≤10^5) 代表数据组数，每组测试数据描述如下：

第一行输入一个整数 n (1≤n≤10^8)。

输出描述：

对于每组测试数据，新起一行输出一个整数 n′ (1≤n′≤10^18)，代表修改后的整数。可以证明，在所给的数据范围内一定存在合法的答案。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

代码：

def demo():
n=int(input())
ans=0
a=10
for i in range(18):
l, r = 0, 10 ** 9 + 7
while l<=r:
mid=(r-l)//2+l
if mid*mid>=n*a:
r=mid-1
ans=mid
else:
l=mid+1
if ans*ans<(n+1)*a:
break
a*=10
print(ans*ans)

t=int(input())
while t:
t-=1
demo()