当前位置：首页 > news >正文

Python解题 - CSDN周赛第38期

news 2025/8/29 7:17:09

又来拯救公主了。。。本期四道题还是都考过，而且后面两道问哥在以前写的题解里给出了详细的代码（当然是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 ，可以分解成 $48=2*2*2*2*3$ ，所以它的因子就有：

$1$ （所有整数的因子，也可以写成 $2^{0}$ 或 $3^{0}$ ）
$2$ （也可以写成 $2^{1}$ ）
$3$ （也可以写成 $3^{1}$ ）
$4:2*2$ （也可以写成 $2^{2}$ ）
$6:2*3$ （也可以写成 $2^{1}*3^{1}$ ）
$8:2*2*2$ （也可以写成 $2^{3}$ ）
$12:2*2*3$ （也可以写成 $2^{2}*3^{1}$ ）
$16:2*2*2*2$ （也可以写成 $2^{4}$ ）
$24:2*2*2*3$ （也可以写成 $2^{3}*3^{1}$ ）
$48:2*2*2*2*3$ （也可以写成 $2^{4}*3^{1}$ ）

如果我们用公式来表示的话，就是任意一个整数都可以写成 $a^{x}*b^{y}*c^{z}*...$ 的形式，其中 $a,b,c$ 是质数， $x,y,z\geq 0$ 。那么其因子个数 $n$ 是什么关系呢？

我们先将问题简化来看，如果这个整数只有一个质因数，比如， $16=2^{4}$ ，其因子中的 2 可以出现 0、1、2、3、4 次，也就是 $2^{0},2^{1},2^{2},2^{3},2^{4}$ ，16 的因子个数 $n = 5$ ，等于因子 2 的出现次数，也就是 2 的幂 4 加一。

如果这个整数有两个质因数，根据排列组合原理，两个质因数的出现次数相乘，就是所有的排列组合个数，也就是因子个数。比如 $48=2^{4}*3^{1}$ ，其因子个数 $n = (4+1)*(1+1)=10$ 。

所以回到我们 $a^{x}*b^{y}*c^{z}*...$ 的表示方法，可以得到 $n=(x+1)*(y+1)*(z+1)*...$ 。所以本题的问题就转化为在给定 $n$ 的时候，找出 $x,y,z,...$ 的大小，使得 $a^{x}*b^{y}*c^{z}*...$ 最小。

要使该整数最小，我们首先要使作为底的 $a,b,c,...$ 这些质因数比较小，所以，较小的质因数在这个最小的整数中至少会出现一次，也就是说 $x,y,z\geq 1$ 。（这应该比较好理解，在给定 $n$ 的时候，如果可以求得 $x,y,z$ ，那么以最小的质因数作为底，得到的结果必然最小。）

所以问哥使用的算法是，从 2（最小的质数）开始试， $2^{n-1}$ 必然是满足因子个数为 $n$ 这个要求的，但却不一定是最小的整数。接着再用比 2 大的下一个质数 3 接着试，组成 $2^{x}*3^{y}$ 的形式，其中 $(x+1)*(y+1)=n$ （其实就是将 $n$ 进行因式分解），然后再换下个质数（2 和 3 必须出现一次）不断递归。因为 $n$ 的因式分解组合是有限的，最终会递归到 $n=1$ 的情况。所以把得到的所有数乘起来，就得到所有因子个数为 $n$ 的整数，再从中找到最小的就是答案。

参考代码（部分）

def dfs(n, x = 2):if n == 1: return 1y = x + 1while not prime(y): # 查找下个质数y += 1                res = INFfor 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期考过，问哥还写了一篇比较详细的题解，其中给出了详细的代码，题目本身也不难，直接复制粘贴就可以过了。

$n$