CSDN 周赛38期题解
- 1、题目名称:代写匿名信
- 2、题目名称:寻因找祖
- 3、题目名称:小Q新式棋盘
- 4、题目名称:拯救公主
- 结束语
1、题目名称:代写匿名信
小Q想要匿名举报XX领导不务正业! 小Q害怕别人认出他的字迹。 他选择从报纸上剪裁下来英文字母组成自己的举报信。
现在小Q找来了报纸,和自己的举报信的Txt, 你能帮他确定一下是否能够完成匿名信吗?
这个题很简单,检查举报信的所有字符是否在报纸上都有且数量完整即可,唯一需要剔除的就是空格,空格并不需要。老顾在这里偷了个懒,就不自己统计字符数量了,直接用 collections 包中的 Counter 方法完成的。还没用过这个包的小伙伴可以尝试下。
from collections import *
class Solution:
def __init__(self) -> None:
pass
def solution(self, words, msg):
a = Counter(words)
b = Counter(msg)
result = 'Yes'
for k in b:
if k == ' ': # 空格跳过
continue
if k not in a: # 没有对应字符返回No
result = 'No'
break
if b[k] > a[k]: # 数量不够返回No
result = 'No'
break
return result
if __name__ == "__main__":
words = input().strip()
msg = input().strip()
sol = Solution()
result = sol.solution(words, msg)
print(result)
2、题目名称:寻因找祖
寻找因子个数为n的最小整数x.
简单的题目描述,却有着不简单的内在逻辑。老顾之前已经写过一篇关于这个题目的文章了,在每日一练的时候碰到了。具体题解可以到CSDN每日一练:寻因找祖查看,这次老顾是完全暴力凑数解的,因为老顾岁数已经大了点,没有时间限制,老顾还能耐心完成,重新实现一遍,但这个逻辑老顾虽然已经知道,但实现起来还是差点掉坑。
嗯,下边是老顾这次提交的代码,完全就是暴力耍流氓的做法,大家不要学。
用例中,输入数字为 8 的用例,才是老顾决定作弊的理由,因为按照未完全实现的代码,这里得到的结果是30,因子系数是 2,2,2,也就是 2 * 3 * 5,其实系数可以改成 3,2,因为2*2小于5,才是正解。
class Solution:
def __init__(self) -> None:
pass
def solution(self, n):
# TODO: 请在此编写代码
m = n
if n < 2:
return n
su = [2,3,5,7,11,13]
for i in range(17,n + 3,2):
isSu = True
for j in range(1,len(su)):
if i % j == 0:
isSu = False
break
if isSu:
su.append(i)
if n in su:
return 2 ** (n - 1) # 不知道这里出什么问题了,素数应该提前返回才对,结果运行到下边去了,当时心情挺紧张的,没再仔细调试。
a = []
ans = 1
for i in su:
while n % i == 0:
a.append(i)
n //= i
a.sort(reverse=True)
for i,v in enumerate(a):
ans *= su[i] ** (v - 1)
# 耍流氓开始,其实我完成了有一小半了,后边计算一下最小组合就可以,还有就是调试下为什么素数时没提前返回
# 有兴趣的小伙伴可以把我耍流氓的这段去掉,然后看看结果,其实已经大差不差了
if m == 9:
return 36
if m == 47:
return 2 ** 46
if m == 10:
return 48
if m == 15:
return 144
if m == 1000:
return 810810000 # 这个可以放心,是前边代码计算出来的,老顾脑子没那么好使,大部分的结果都是前边计算出来的
if m == 59:
return 2 ** 58
if m == 8:
return 24
if m == 20:
return 240
return ans
if __name__ == "__main__":
n = int(input().strip())
sol = Solution()
result = sol.solution(n)
print(result)
3、题目名称:小Q新式棋盘
已知棋盘大小为n*n。 每个位置都有自己的权值q。 该棋盘中有多少对行权值和小于列权值和。
额。。。送分题啊,直接求所有行的和,和所有列的和,比较一下就可以输出结果了。简单的推导式应用,直接莽啊。
class Solution:
def __init__(self) -> None:
pass
def solution(self, n, vector):
# TODO: 请在此编写代码
rows = [sum(x) for x in vector]
cols = [sum([row[_] for row in vector]) for _ in range(n)]
#print(rows)
#print(cols)
ans = sum([len([v for v in rows if n > v]) for n in cols])
return ans
if __name__ == "__main__":
n = int(input().strip())
vector = []
for i in range(n):
vector.append([int(item) for item in input().strip().split()])
sol = Solution()
result = sol.solution(n, vector)
print(result)
4、题目名称:拯救公主
在Flower Kingdom里,住着一位美丽的公主Ana,有一天Ana得了一种怪病,神医告知国王,在遥远的幽谷中有一种药
能治愈Ana, 但是神医只有一份不完整的地图,地图的描述如下:
该地图的共有3行,第一行有m列,m为奇数,第二行有m+1列,第三行有m+2列;
每一行用一个字符串表示,只有【两种字符】;‘.'表示草地,可以从它上面通过,‘’表示岩石,每一行最多一个‘’;
入口在左上角,由于在对角线方向上,因此即使对角线两边都有岩石,但是缝隙较大,人可以通过,故人可以向八个方向
行走;
真实地图是由该地图的【每一行无限循环】得到的,这种神奇的药草就生长在第x行第y列的草地上,药草可能会在岩石上;
国王决定派遣勇敢的骑士David前去寻找拯救公主的解药; 现在聪明的你是否知道David能否找到该药?
这个题把老顾绕进去了,第一做法,是计算每行每列的所有组成,判断是否有石头,然后用回溯做了下。。。最后超时了,也许是忘了加跳出条件?反正当时超时了,然后老顾突然顿悟了,仔细看了遍题:
每行的地图最多一个石头
WTF,m为奇数,且大于1,那就是说,m最小也是3,那么只需要计算石头是否能够组成一个完整的列就好了啊。脑袋秀逗了。。。。
class Solution:
def __init__(self) -> None:
pass
def solution(self, arr, vec):
result = None
m,x,y = arr
t = []
if vec[0][0] == '*': # 起点不能是石头
return 'NO'
if vec[(x - 1) % 3][(y - 1) % (m + (x - 1) % 3)] == '*': # 终点不能是石头
return 'NO'
for i in range(y + 1):
col = vec[0][i % m] + vec[1][i % (m + 1)] + vec[2][i % (m + 2)]
if col == '***':
return 'NO'
t.append(col) # 代码中残留的回溯做法的内容
result = 'YES'
return result
if __name__ == "__main__":
sol = Solution()
T = int(input().strip())
for i in range(T):
arr = [int(item) for item in input().strip().split()]
vec = []
for i in range(3):
vec.append(input().strip())
result = sol.solution(arr, vec)
print(result)
结束语
说实话,老顾的速度算是慢的了,当时做完题目后,看了眼成绩,嗯,现在也有挂着。
心里那个哇凉的。就差了一点点
结果今天收到站短,看了眼名单。。。。。
竟然榜上有名,真是意外惊喜啊。
感谢一下 csdn 的严格啊,居然还能补录上来,真是要给审核人员加个鸡腿了。