牛客周赛 Round 133（ABCD）

A.小红的闭合标签

链接：A-小红的闭合标签_牛客周赛 Round 133

题目详情：

给定一个 HTML 开始标签 s（不包含属性，只有标签名），请输出其对应的闭合标签。在 HTML 中，一个开始标签的格式为 <tagname>，其中 tagname 是标签的名称；对应的闭合标签格式为 </tagname>，即在 tagname 前添加 </，末尾添加 >。

输入描述：

• 第一行输入一个整数 n (3≤n≤10)，表示字符串的长度。

• 第二行输入一个长度为 n 的字符串 s，表示一个 HTML 开始标签。保证 s 以字符 < 开头、以字符 > 结尾，且中间包含一个由小写字母组成的字符串。

输出描述：

输出一个字符串，表示对应的闭合标签。

代码：

n=int(input())
s=input()
s1=s[0]+'/'+s[1:]
print(s1)

B.小红的众数

题目详情：

给定一个长度为 n 的整数数组 a 和一个目标数字 x，你可以执行任意次数的插入操作（每次插入一个 x 到数组中任意位置）。

请计算最少需要插入多少个 x，使得 x 成为数组中唯一的众数（即 x 的出现次数严格大于数组中其他所有数字的出现次数）。

输入描述:

输出描述:

输出一个整数，表示最少需要插入的 x 的个数。

代码：

n,x=map(int,input().split())
aList=[int(x) for x in input().split()]
aDict= {}
for num in aList:
aDict[num]=aDict.get(num,0)+1
max1=max(aDict.values())

print(max1-aDict.get(x,0))

C.小红的数字查找

题目详情：

给定一个整数 x 以及两个正整数 l,r，请你判断是否存在一个整数 y 满足：

• l≤y≤r；
• x×y 是一个完全平方数。

如果存在，请给出任意一个满足条件的 y；否则输出 −1。

【名词解释】：

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

输入描述：

输入三个整数 x,l,r (1≤x≤10^9; 1≤l≤r≤10^9)。

输出描述：

如果存在符合条件的 y，输出一个整数 y；否则输出 −1。如果存在多个解决方案，您可以输出任意一个。

代码：

import math# 一开始想用素数把x的质因数都算出来，然后x=num*q^2（即num*一个平方数）,所以y=num*一个平方数，但是用了太多的循环，超时了，且超内存了
import bisect# 现在直接通过i*i<=x，直接把x里面的质因数算出来，算出num，再通过二分查找找到第一个值大于等于ceil(l/num)的平方数（大于等于ceil(l/num)因为要满足y>=l）,（要找第一个是因为要尽量满足y<=r）
# n=10**6
# is_prime=[1]*n
# prime=[]
# def ola():
# pp = 0
# is_prime[1]=0
# for i in range(2,n):
# if is_prime[i]:
# prime.append(i)
# pp+=1
# for j in range (0,pp):# 不能直接从1到pp+1，因为会漏掉第一个数字2，并且会超过当前prime列表的范围
# if i*prime[j]<n:# <n
# is_prime[i*prime[j]]=0
# if i%prime[j]==0:
# break
# print(prime)
def demo():
# ola()
x,l,r=map(int,input().split())
# prime_set=set(prime)
s=[]
i=1
while i*i<(10**9+7):
s.append(i*i)
i+=1
num=1
i=2
while i*i<=x:
q=0
while x%i==0:
q+=1
x//=i
if q%2==1:
num*=i
i+=1
num*=x
s1=num*s[bisect.bisect_left(s,math.ceil(l/num))]# bisect.bisect_left(s,math.ceil(l/num))返回第一个>=math.ceil(l/num)的元素的下标
# 用第一个>=math.ceil(l/num)的元素,是因为要尽量让y在范围内，要<=r
if l%num==0:
return l
elif l<=s1<=r:
return s1
else:
return -1

print(demo())

D.小红的异或分组

题目详情：

小红有一个长度为 n 的数组，她想把数组分成三个连续的非空子数组，使得这三个子数组的异或和相等。请计算有多少种合法的分法。

数组的异或和定义为：将数组中所有元素进行按位异或运算得到的结果。若数组只有一个元素，异或和即为该元素本身。

输入描述:

输出描述:

输出一个整数，表示合法的方案数。

代码：

import bisect
def demo():
n=int(input())
aList=[int(x) for x in input().split()]
pre=[0]*n
pre[0]=aList[0]
pre_0=[]
if pre[0]==0:
pre_0.append(0)
for i in range(1,n):
pre[i]=pre[i-1]^aList[i]
if pre[i]==0 and i<n-1:# i<n-1 ,因为要给最后的一个子数组留下至少一个位置！！！
pre_0.append(i)
num_0=len(pre_0)
x=pre[-1]
ans=0
for i in range(n):
if pre[i]==x:
num=num_0-bisect.bisect_left(pre_0,i+1)# 此处+1是因为要避免如果x刚好也为0时第二个子数组直接为空的情况，且本来第二个子数组的开始的第一个元素的下标就应该大于上一个子数组的最后一个下标i
if num==0:
break
ans+=num
return ans

print(demo())