牛客周赛 Round 133

小红的闭合标签

考点：模拟。

思路：

按题意模拟即可。

复杂度：O(n)

import sys
input=sys.stdin.readline
n=int(input())
a=list(input().strip())
s='</'
for i in range(1,n):
s+=a[i]
print("".join(s))

小红的众数

考点：模拟。

思路：

找到在数组a中出现最多的数字，然后跟x在a中出现的次数相减即可。

复杂度：O(n)

import sys
from collections import defaultdict
input=sys.stdin.readline

n,x=map(int,input().split())
a=list(map(int,input().split()))
b=defaultdict(int)
for v in a:
b[v]+=1
zd=max(b.values())
z=0
for val,cnt in b.items():
if val==x:
z=cnt
break
print(zd-z)

小红的数字查找

考点：模拟。

思路：

把问题转换成把x变成平方因子去掉后的那部分，然后让y去补全剩余的平方。

import sys
import math
sqrt=math.sqrt
input=sys.stdin.readline
x,l,r=map(int,input().split())
q=2
#先把x^2去除掉，剩下找y即可。
while q*q<=x:
res=q*q
while x%res==0:
x//=res
q+=1
#找y
i=1
while i*i*x<l:
i+=1
if i*i*x<=r:
print(i*i*x)
else:
print(-1)

小红的异或分组

考点：前缀和

思路：

设前缀异或p：

• 
• 
• 总异或为

由于三段异或和相等，设每段异或和为x，那么就有：

• 。
• 第一段。
• 第三段。

所以我们只要找到p[a]=T且pre[b]=0的(a,b)对的数量即可。

复杂度：O(n)

import sys
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
if n<3:
print(0)
exit()
p=[0]*(n+1)
x=0
for i,v in enumerate(a):
x^=v
p[i+1]=x
zh=p[n]
pre=[0]*(n+1)
for i in range(1,n-1):
pre[i]=pre[i-1]+(1 if p[i]==zh else 0)
cnt=0
for c2 in range(2,n):
if p[c2]==0:
cnt+=pre[c2-1]
print(cnt)