120 周赛
如果第一题没有提示,我还真不确定我是不是能做出来
第一题 最大GCD
提示是通过给定样例观察一下 n 和答案之间的关系。结果会发现答案就是 n 向下取整除以 2
第二题 统计范围内一共有多少个正整数满足其十进制表示只含 4 或 7
这道题目立马就想到了借助二进制来求解,但将思路转换为算法的过程颇为曲折,所以简单记录一下最后优化后的代码。
py
n = int(input())
digits = len(str(n))
ans = 0
for i in range(1, digits):
ans += 2 ** i
bits = 2 ** digits
for i in range(bits):
bit = ((bin(i))[2:]).rjust(digits, '0')
bit = bit.replace('0', '4').replace('1', '7')
num = int(bit)
if num <= n:
ans += 1
else:
break
print(ans)
第三题 完美匹配和普通匹配的字符数量
好气,思路方向是对的,但提交的时候一直有错误答案,但一直想不出是什么情况。
简单扫了一遍别人的代码后,发现大家都有两个循环,也就是说,不可以在同一个循环中判断一个位置是完美匹配还是普通匹配。我对此的理解是:当一个字符没有完美匹配,但可以普通匹配时,由于匹配后会删掉对应的字符,这这个字符可能是后面的某个字符的完美匹配!所以只能先匹配完所有的完美匹配,然后再匹配普通的。
py
s = list(map(ord, input().strip()))
t = input().strip()
t_map = [0] * 123
for i in t:
t_map[ord(i)] += 1
def toggle(o):
if o < 97:
return o+32
return o-32
perfect = common = 0
had_perfect = [False] * len(s)
for i, a1 in enumerate(s):
if t_map[a1] > 0:
perfect += 1
t_map[a1] -= 1
had_perfect[i] = True
for i, a1 in enumerate(s):
a2 = toggle(a1)
if not had_perfect[i] and t_map[a2] > 0:
common += 1
t_map[a2] -= 1
print(perfect,common)