目录
C.小红的小小红
题目
输入
输出
题解
代码
D.小红的中位数
题目
输入
输出
题解
代码
E.小红构造数组
题目
输入
输出
题解
代码
C.小红的小小红
题目
小红拿到了一个字符串，其中一定包含连续子串”xiao”，和连续子串”hong”。
请你将字符串重排，使得该字符串包含”xiaohong”的连续子串。
输入
honghongxiao
输出
xiaohonghong题解
在py里面可以采用字符串计数 + 替换的方法直接快速构造
分别统计‘xiao’和‘hong’，然后构造出‘xiaohong’之后，其他的按照原来的写
代码
s = input()numx = s.count('xiao')numh = s.count('hong')res = s.replace('xiao' , '-')res = res.replace('hong' , '-')# print(res)res += 'xiaohong' + (numx - 1) * 'xiao' + (numh - 1) * 'hong'print(res.replace('-' , ''))D.小红的中位数
题目
小红拿到了一个数组：a1,a2,…,ana_1,a_2,…,a_na1,a2,…,an。她定义 f(i) 为，删除第iii个元素后，数组的中位数。现在小红想让你求出f(1),f(2)…f(n)f(1),f(2)…f(n)f(1),f(2)…f(n)的值，你能帮帮她吗？
输入
4
2 5 8 1
输出
5.0
2.0
2.0
5.0
题解
中位数： 排序之后，中间的数，如果是偶数就是中间两边的数相加除以2
先进行排序，然后分类讨论并保存值到一个哈希表，根据以下情况来判定，最后按照初始列表来输出
值得注意的是，可能会有相同的情况，但是在python里面方便的一点就是可以在哈希表里面很便捷的存储一个列表，最后按照列表顺序输出即可
代码
from math import *from collections import defaultdictn = int(input())a = [0] +list(map(int,input().split()))# 先存排序之前所有的下标：值b = sorted(a)dic = defaultdict(list)if n % 2 == 0:mid = n // 2for i in range(1 , n + 1):if i <= mid:dic[b[i]].append(b[mid + 1])else:dic[b[i]].append(b[mid])else:mid = ceil(n / 2)for i in range(1 , n + 1):if i < mid:dic[b[i]].append((b[mid + 1] + b[mid]) / 2)elif i == mid:dic[b[i]].append((b[mid - 1] + b[mid + 1]) / 2)else:dic[b[i]].append((b[mid] + b[mid - 1]) / 2)for i in range(1 , n + 1):print("%.1f"%dic[a[i]][0])dic[a[i]].pop(0)E.小红构造数组
题目
小红希望你构造一个数组，满足以下三个条件：
1. 数组的元素都是素数。
2. 数组所有元素相乘恰好等于xxx。
3. 数组任意相邻两个元素不等。
输入
30
输出
3
2 5 3
题解
先来看一个概念，做这道题的前提（如果不会的话，可以先学习一下数论基础）
唯一分解定理：任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积N=P1a1P2a2P3a3……Pnan，这里P1<P2<P3……<Pn均为质数，其中指数ai是正整数。
我们先将一个数分解成若干个质数，在这些质数之上来构造相邻两个数不相等（肯定要错开来填）
比如分出来的数是这样的：
我们可以发现，最大的重复数是2 ， 那么2就可以把5隔开填，因为3个5的空隙是4，依次类推，5可以把3交错填
对于除了最大的重复数，其他数就可以计算一个缝隙数，如果最大的重复数量比剩下可以插空的数量大的话，那么就无法构造（比如4个2 和 3个5 ，自己可以动手尝试一下）
如果可以的话，那么就交替插入： 对于一个重复数，先从偶数开始插，然后再从奇数开始插，这样一定可以隔开插入（对于每个重复的数来说）
有几点需要注意的：
1. 在最后进行插入的时候，一定要从最大数量的重复数开始插入，也就是先要排个序，从大到小。并且要先插入偶数，才能插入奇数（这是因为，其他数的间隔数是从0开始算的，否则就会出现以下情况）
代码
import mathfrom collections import Counterdef f(n):res = []for i in range(2, int(math.sqrt(n)) + 1):while n % i == 0:n //= ires.append(i)if n > 1:res.append(n)return resn = int(input())res = f(n)dic = dict(Counter(res))# 排序lst = list(dic.items())lst.sort(key = lambda p: p[1] ,reverse=True)mx = 0for k,v in dic.items():mx = max(mx , v)m = len(res)if mx == 0 or mx > m - mx + 1:print(-1)else:print(m)odd , even = 1 , 0new = [0] * (m + 1)for k,v in lst:# 先构造偶数while v and even < m:new[even] = kv-=1even += 2# 再构造奇数while v and odd < m:new[odd] = kv-=1odd += 2print(*new[:-1])