Python解题 - CSDN周赛第38期
又来拯救公主了。。。本期四道题还是都考过,而且后面两道问哥在以前写的题解里给出了详细的代码(当然是python版),直接复制粘贴就可以过了——尽管这样显得有失公允,考虑到以后还会出现重复的考题,所以现在问哥的题解基本不会给出完整的代码了。但是如果理解了思路,写出来应该不难。
第一题:代写匿名信
小Q想要匿名举报XX领导不务正业!小Q害怕别人认出他的字迹。他选择从报纸上剪裁下来英文字母组成自己的举报信。现在小Q找来了报纸,和自己的举报信的Txt,你能帮他确定一下是否能够完成匿名信吗?
输入描述:第一行输入报纸上的英文。 第二行输入小Q匿名信的内容。 (1<=len(str)<=10000)
输出描述:如果能完成输出”Yes”,否则输出”No”。(区分大小写,不考虑空格)
分析
其实小Q要做的,就是把报纸上的一个个字符“剪”出来,然后拼成一封“匿名信”。于是我们只要检查报纸上每个字符的个数,是否足够拼成要写的匿名信就可以了,比如如果要写的匿名信内容是 ddd,那报纸上至少要有3个d。
所以代码实现就很简单了,有很多种做法,比如先找出匿名信里每个字符的个数,然后去报纸里找,是否有这个字符、数量是否足够,还可以先把报纸里的字符及个数统计出来,然后与匿名信的相应字符比较个数,如果少于匿名信,说明字符不够,反之就可以完成。
不过还要稍微判断一下,空格是不需要从报纸上剪下来的,所以不用分析空格的数量。
参考代码
from collections import Counter
a = Counter(magazine)
b = Counter(message)
for i in b:
if i != " " and a[i] < b[i]:
print("No")
break
else:
print("Yes")
第二题:寻因找祖
寻找因子个数为n的最小整数x
分析
本题算是本期相对来说比较烧脑的一道了,虽然很久以前也考过。主要是数学上要对数字有一定的感觉。
首先我们知道,任意一个整数,都可以分解成若干个质数的乘积,而它的因子就是这些质因数的排列组合的乘积。比如整数 48 ,可以分解成 ,所以它的因子就有:
- (所有整数的因子,也可以写成 或 )
- (也可以写成 )
- (也可以写成 )
- (也可以写成 )
- (也可以写成 )
- (也可以写成 )
- (也可以写成 )
- (也可以写成 )
- (也可以写成 )
- (也可以写成 )
如果我们用公式来表示的话,就是任意一个整数都可以写成 的形式,其中 是质数, 。那么其因子个数 是什么关系呢?
我们先将问题简化来看,如果这个整数只有一个质因数,比如,,其因子中的 2 可以出现 0、1、2、3、4 次,也就是 ,16 的因子个数 ,等于因子 2 的出现次数,也就是 2 的幂 4 加一。
如果这个整数有两个质因数,根据排列组合原理,两个质因数的出现次数相乘,就是所有的排列组合个数,也就是因子个数。比如 ,其因子个数 。
所以回到我们 的表示方法,可以得到 。所以本题的问题就转化为在给定 的时候,找出 的大小,使得 最小。
要使该整数最小,我们首先要使作为底的 这些质因数比较小,所以,较小的质因数在这个最小的整数中至少会出现一次,也就是说 。(这应该比较好理解,在给定 的时候,如果可以求得 ,那么以最小的质因数作为底,得到的结果必然最小。)
所以问哥使用的算法是,从 2(最小的质数)开始试, 必然是满足因子个数为 这个要求的,但却不一定是最小的整数。接着再用比 2 大的下一个质数 3 接着试,组成 的形式,其中 (其实就是将 进行因式分解),然后再换下个质数(2 和 3 必须出现一次)不断递归。因为 的因式分解组合是有限的,最终会递归到 的情况。所以把得到的所有数乘起来,就得到所有因子个数为 的整数,再从中找到最小的就是答案。
参考代码(部分)
def dfs(n, x = 2):
if n == 1: return 1
y = x + 1
while not prime(y): # 查找下个质数
y += 1
res = INF
for i in range(n, 1, -1):
if n % i == 0:
res = min(res, x**(i-1) * dfs(n//i, y))
return res
第三题:小Q新式棋盘
已知棋盘大小为n*n。 每个位置都有自己的权值q。该棋盘中有多少对行权值和小于列权值和。
分析
14期考过,以前的题解也给出了比较详细的代码及优化方案。其实也没什么可详细说的,就是按照字面意思分别比较行、列的和即可。
第四题:拯救公主
在Flower Kingdom里,住着一位美丽的公主Ana,有一天Ana得了一种怪病,神医告知国王,在遥远的幽谷中有一种药能治愈Ana, 但是神医只有一份不完整的地图,地图的描述如下: 该地图的共有3行,第一行有m列,m为奇数,第二行有m+1列,第三行有m+2列;每一行用一个字符串表示,只有【两种字符】;‘.'表示草地,可以从它上面通过,‘*’表示岩石,每一行最多一个‘*’; 入口在左上角,由于在对角线方向上,因此即使对角线两边都有岩石,但是缝隙较大,人可以通过,故人可以向八个方向行走; 真实地图是由该地图的【每一行无限循环】得到的,这种神奇的药草就生长在第x行第y列的草地上,药草可能会在岩石上;国王决定派遣勇敢的骑士David前去寻找拯救公主的解药;现在聪明的你是否知道David能否找到该药?
分析
17期考过,问哥还写了一篇比较详细的题解,其中给出了详细的代码,题目本身也不难,直接复制粘贴就可以过了。