当前位置: 首页 > article >正文

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 ,可以分解成 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 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期考过,问哥还写了一篇比较详细的题解,其中给出了详细的代码,题目本身也不难,直接复制粘贴就可以过了。


http://www.kler.cn/a/3340.html

相关文章:

  • STM32_SD卡的SDIO通信_基础读写
  • JQuery基本介绍和使用方法
  • 基于 WEB 开发的手机销售管理系统设计与实现内容
  • Java实现简易银行账户管理系统
  • 基于springboot社区医院管理系统
  • 数据库事务详解
  • 【机器学习基础 3】 sklearn库
  • 智能触摸面板开关一Homekit智能家居
  • ES6新增功能强大的运算符详解!!!写项目事半功倍!!!力荐!!!
  • 深入探索Android卡顿优化(上)
  • AD/DA转换(XPT2046)
  • [oeasy]python0116_文字的起源_苏美尔文明_楔形文字_两河流域
  • 【数据结构】二叉树及相关习题详解
  • SANGFOR 旧防火墙配置怎么导入新防火墙
  • 【Python】虚拟环境及在VS Code当中的使用
  • 线程池的讲解和实现
  • 图形视图界面 图形效果
  • 【数据结构】树的介绍
  • 用队列实现栈(图示超详解哦)
  • GPT-4发布,这类人才告急,大厂月薪10W+疯抢
  • LeetCode算法 打家劫舍 和 打家劫舍II C++
  • ChatGPT新进展GPT-4 模型介绍
  • 【数据结构与算法】 - 线性表详解 - (带头结点)单链表详细实现思路及代码
  • 基于51单片机的自动打铃打鸣作息报时系统AT89C51数码管三极管时钟电路
  • Week 14
  • C/C++每日一练(20230325)