蓝桥杯python第二期模拟赛 python 题解

蓝桥杯python第二期模拟赛 python 题解

文章目录

• 蓝桥杯python第二期模拟赛 python 题解
• • 题目1
  • 题目2
  • 题目3
  • 题目4
  • 题目5
  • 题目6
  • 题目7
  • 题目8
  • 题目9
  • 题目10

题目1

小蓝的IP地址为 192.168.*.21，其中 * 是一个数字，请问这个数字最大可能是多少 ?

思路：就是简单的IP地址的位数吧，计算机的常识，也就是255

答案：255

题目2

如果一个整数 g 能同时整除整数 A 和 B，则称 g 是 A 和 B 的公约数。

例如：43 是 86 和 2021 的公约数。

请问在 1（含） 到 2021（含） 中，有多少个数与 2021 存在大于 1 的公约数。

请注意 2021 和 2021 有大于 1 的公约数，因此在计算的时候要算一个。

思路：首先这道题和之前不一样的点是，我们求的是公约数，没有说最大公约数，所以说gcd是没有用的。

然后仔细看看题目，我们说的是与2021的最大公约数，首先满足的条件就是，一定能被2021整除，所以先取出所有能被2021整除的数

然后再1-2021中判断，能不能被其中一个数小于他的数整除，如果可以，说明就是公约数。

答案：89

from math import gcd

cnt = 0
h = []
for i in range(2,2022):
    if 2021%i == 0:
        h.append(i)

for i in range(1,2022):
    for x in h:
        if x > i:
            break
        if i % x == 0 and 2021 % x == 0:
            cnt += 1
##            print(i,x)
            break
    
print(cnt) # 答案:89

题目3

2021 是一个非常特殊的数，它可以表示成两个非负整数的平方差，2021 = 45 * 45 - 2 * 2。

2025 也是同样特殊的数，它可以表示成 2025 = 45 * 45 - 0 * 0。

请问，在 1 到 2021 中有多少个这样的数？
请注意，有的数有多种表示方法，例如 9 = 3 * 3 - 0 * 0 = 5 * 5 - 4 * 4，在算答案时只算一次。

思路：其实对于我们来说，又是穷举了，但是这里涉及一个上界，我们多少穷举到多少好呢，我觉得有一个笨方法，我试了一下，比如首先上界设为100，得到一个答案，然后我们可以提高上界1000，如果发现答案又大了，说明上界没有到，那就继续加，发现我们的答案没变的时候，说明就到我们的上界了

但实际上是有方法的，首先知道平方差公式

• 平方差公式：a^2 - b^2 = （a+b)（a-b）
• 确定内层循环范围：b
• 确定外层循环范围：b=a-1时取得最小正数，此时（a+b)（a-b）=（2a-1)，令2a-1=2021,得到a的上限1011

所以上界为1011是最准确的

s = set()
for i in range(1012):
    for j in range(i+1,1012):
        x = j*j - i*i
        if x not in s and 1<=x<=2021:
            s.add(x)
print(len(s)) # 答案：1516
##print(s)

题目4

小蓝要用01串来表达一段文字，这段文字包含 a, b, c, d, e, f 共 6 个字母，每个字母出现的次数依次为：a 出现 10 次，b 出现 20 次，c 出现 3 次，d 出现 4 次，e 出现 18 次，f 出现 50 次。

　小蓝准备分别对每个字母使用确定的01串来表示，不同字母的01串长度可以不相同。

　在表示文字时，将每个字母对应的01串直接连接起来组成最终的01串。

为了能够正常还原出文字，小蓝的编码必须是前缀码，即任何一个字符对应的01串都不能是另一个字符对应的01串的前缀。

　例如，以下是一个有效的编码：
　a: 000
　b: 111
　c: 01
　d: 001
　e: 110
　f: 100
　其中 c 的长度为 2，其它字母的编码长度为 3，这种方式表示这段文字需要的总长度为：103+203+32+43+183+503=312。

　上面的编码显然不是最优的，将上面的 f 的编码改为 10，仍然满足条件，但是总长度为 262，要短 50。

　要想编码后的总长度尽量小，应当让出现次数多的字符对应的编码短，出现次数少的字符对应的编码长。

　请问，在最优情况下，编码后的总长度最少是多少？

思路：这个的话，实际上就是哈夫曼树了，对我们的数进行一个编码 *** 作，这个确实知识点还没复习到，大二数据结构学的了，也可以看看。

首先我们可以画一个哈夫曼的图

根据这个图我们就可以对我们的数据进行编码了，这些都是基本的知识，就是去较多的剔除，这样我们编码的时候，长度较短，出现比较少，就可以有效减小编码长度。

按左树为0，右树为1编码：
c: 3 11000
d: 4 11001
a: 10 1101
e: 18 111
b: 20 10
f: 50 0
    
5*3+5*4+4*10+3*18+2*20+1*50=219

题目5

下面的矩阵中包含 ABCDEF 六种字符，请问出现最多的字符出现了几次？
　FFEEFEAAECFFBDBFBCDA
　DACDEEDCCFFAFADEFBBA
　FDCDDCDBFEFCEDDBFDBE
　EFCAAEECEECDCDECADDC
　DFAEACECFEADCBFECADF
　DFBAAADCFAFFCEADFDDA
　EAFAFFDEFECEDEEEDFBD
　BFDDFFBCFACECEDCAFAF
　EFAFCDBDCCBCCEADADAE
　BAFBACACBFCBABFDAFBE
　FCFDCFBCEDCEAFBCDBDD
　BDEFCAAAACCFFCBBAAEE
　CFEFCFDEEDCACDACECFF
　BAAAFACDBFFAEFFCCCDB
　FADDDBEBCBEEDDECFAFF
　CDEAFBCBBCBAEDFDBEBB
　BBABBFDECBCEFAABCBCF
　FBDBACCFFABEAEBEACBB
　DCBCCFADDCACFDEDECCC
　BFAFCBFECAACAFBCFBAF

思路：简单来说，就是一个哈希表，最后统计最多的字符，直接暴力搜素嘻嘻

m = ['FFEEFEAAECFFBDBFBCDA',
'DACDEEDCCFFAFADEFBBA',
'FDCDDCDBFEFCEDDBFDBE',
'EFCAAEECEECDCDECADDC',
'DFAEACECFEADCBFECADF',
'DFBAAADCFAFFCEADFDDA',
'EAFAFFDEFECEDEEEDFBD',
'BFDDFFBCFACECEDCAFAF',
'EFAFCDBDCCBCCEADADAE',
'BAFBACACBFCBABFDAFBE',
'FCFDCFBCEDCEAFBCDBDD',
'BDEFCAAAACCFFCBBAAEE',
'CFEFCFDEEDCACDACECFF',
'BAAAFACDBFFAEFFCCCDB',
'FADDDBEBCBEEDDECFAFF',
'CDEAFBCBBCBAEDFDBEBB',
'BBABBFDECBCEFAABCBCF',
'FBDBACCFFABEAEBEACBB',
'DCBCCFADDCACFDEDECCC',
'BFAFCBFECAACAFBCFBAF']

from collections import Counter
c = Counter()
h = {}
for i,x in enumerate(m):
    for j,y in enumerate(x):
        h[y] = h.get(y,0) + 1
        # c[y] += 1
print(max(h)) # 答案:F 出现了78次

题目6

小蓝要到店里买铅笔。

铅笔必须一整盒一整盒买，一整盒 12 支，价格 p 元。

小蓝至少要买 t 支铅笔，请问他最少花多少钱？
输入格式
输入一行包含两个整数 p、t，用一个空格分隔。

输出格式
输出一行包含一个整数，表示答案。

样例输入
5 30
样例输出
15
样例说明
小蓝至少要买3盒才能保证买到30支铅笔，总共花费 15 元。

评测用例规模与约定
对于所有评测用例，1 <= p <= 100，1 <= t <= 10000。

思路：这个就是模拟题了，如果刚刚好是倍数，就买相应盒数，如果不是，那可能要多买一盒才能达到要求

p,t = map(int,input().split())

if t % 12==0:
    print(p*(t//12))
else:
    print(p*(t//12+1))

题目7

给定一个三角形的三条边的长度 a, b, c，请问这个三角形是不是一个直角三角形。

输入格式
输入一行包含三个整数 a, b, c，表示三角形三边的长度，相邻整数之间用一个空格分隔。

输出格式
如果是直角三角形，输出“YES”（全大写），否则输出“NO”（全大写）。

样例输入
3 4 5
样例输出
YES
样例输入
4 5 4
样例输出
NO
评测用例规模与约定
对于所有评测用例，1 <= a, b, c <= 1000。

思路：勾股定理，binggo

a,b,c = map(int,input().split())


a,b,c = sorted([a,b,c])
if a*a + b*b == c*c:
    print('YES')
else:
    print('NO')

题目8

n 个小朋友正在做一个游戏，每个人要分享一个自己的小秘密。

每个小朋友都有一个 1 到 n 的编号，编号不重复。

为了让这个游戏更有趣，老师给每个小朋友发了一张卡片，上面有一个 1 到 n 的数字，每个数字正好出现一次。

每个小朋友都将自己的秘密写在纸上，然后根据老师发的卡片上的数字将秘密传递给对应编号的小朋友。

如果老师发给自己的数字正好是自己的编号，这个秘密就留在自己手里。

小朋友们拿到其他人的秘密后会记下这个秘密，老师会再指挥所有小朋友将手中的秘密继续传递，仍然根据老师发的卡片上的数字将秘密传递给对应编号的小朋友。

这样不断重复 n 次。

现在，每个小朋友都记下了很多个秘密。

老师现在想找一些小朋友，能说出所有秘密，请问老师最少要找几个小朋友？
输入格式
输入的第一行包含一个整数 n。

第二行包含 n 个整数 a[1], a[2], …, a[n]，相邻的整数间用空格分隔，分别表示编号 1 到 n 的小朋友收到的数字。

输出格式
输出一行包含一个整数，表示答案。

样例输入
6
2 1 3 5 6 4
样例输出
3
样例说明
最终小朋友 1, 2 互相知道了对方的秘密，小朋友 3 只知道自己的秘密，小朋友 4, 5, 6 互相知道了对方的秘密。

至少要找 3 个小朋友才能说出所有秘密。

评测用例规模与约定
对于 30% 的评测用例，2 <= n <= 30。

对于 60% 的评测用例，2 <= n <= 1000。

对于所有评测用例，2 <= n <= 100000。

思路：这道题其实就是考一个图的连通分量，所以我们可以利用并查集

但是这道题我是有些不懂的，我们选小朋友，12中选一个，3选一个，456起码选择两个才知道所有秘密吧，不明白（可能知道秘密的可以互相交换吧）

后面好像明白了，就是4一直把秘密传给5,5传给6,6传给4，这样慢慢的，就互相知道秘密了

def find(x):
    if x!=f[x]:
        f[x] = find(f[x])
    return f[x]
def union(x,y):
    fx,fy = find(x),find(y)
    if fx!=fy:
        f[fx] = fy

n = int(input())
f = [i for i in range(n+1)]
a = map(int,input().split())
for i,v in enumerate(a):
    union(i+1,v)

s = set()
for i in range(1,n+1):
    x = find(i)
    if x not in s:
        s.add(x)
print(len(s))

题目9

一个 1 到 n 的排列被称为半递增序列，是指排列中的奇数位置上的值单调递增，偶数位置上的值也单调递增。

例如：(1, 2, 4, 3, 5, 7, 6, 8, 9) 是一个半递增序列，因为它的奇数位置上的值是 1, 4, 5, 6, 9，单调递增，偶数位置上的值是 2, 3, 7, 8，也是单调递增。

请问，1 到 n 的排列中有多少个半递增序列？
输入格式
输入一行包含一个正整数 n。

输出格式
输出一行包含一个整数，表示答案，答案可能很大，请输出答案除以 1000000007 的余数。

样例输入
5
样例输出
10
样例说明
有以下半递增序列：
　(1, 2, 3, 4, 5)
　(1, 2, 3, 5, 4)
　(1, 2, 4, 3, 5)
　(1, 3, 2, 4, 5)
　(1, 3, 2, 5, 4)
　(1, 4, 2, 5, 3)
　(2, 1, 3, 4, 5)
　(2, 1, 3, 5, 4)
　(2, 1, 4, 3, 5)
　(3, 1, 4, 2, 5)
评测用例规模与约定
对于 50% 的评测用例，2 <= n <= 20。

对于所有评测用例，2 <= n <= 1000。

思路：这道题把我搞蒙了，这道题实际上是一个杨辉三角形，DP真牛

我们可以这样想，如果我们有n个数，其中就是n//2个奇数，我们要放在n个位置上，所以就是组合问题了，最后的偶数的放法就只有一种了，是不是很简单，所以就是求 C n n / / 2 C_n^{n//2} Cnn//2​，但是假设我们有1000个数，这样太大了，我们也要取模，所以就可以借鉴我们的杨辉三角形，因为杨辉三角形就是可以求组合数的。

其实我觉得，我们可以调库的，很简单，只要明白意思

n = int(input())
MOD = 1000000007

import math
print(math.comb(n,n//2)%MOD)


dp = [0]*1001
for i in range(1,n+1):
    dp[0] = 1
    dp[i] = 1
    for j in range(i-1,0,-1):
        dp[j] = (dp[j]+dp[j-1])%MOD
print(dp[n//2])

题目10

小蓝住在 LQ 城，今天他要去小乔家玩。

LQ 城可以看成是一个 n 行 m 列的一个方格图。

小蓝家住在第 1 行第 1 列，小乔家住在第 n 行第 m 列。

小蓝可以在方格图内走，他不愿意走到方格图外。

城市中有的地方是风景优美的公园，有的地方是熙熙攘攘的街道。

小蓝很喜欢公园，不喜欢街道。

他把方格图中的每一格都标注了一个属性，或者是喜欢的公园，标为1，或者是不喜欢的街道标为2。

小蓝和小乔住的地方都标为了1。

小蓝每次只能从一个方格走到同一行或同一列的相邻方格。

他想找到一条路径，使得不连续走两次标为 2 的街道，请问在此前提下他最少要经过几次街道？

输入格式
输入的第一行包含两个整数 n, m，用一个空格分隔。

接下来 n 行，每行一个长度为 m 第数字串，表示城市的标注。

输出格式
输出一行包含一个整数，表示答案。

如果没有满足条件的方案，输出 -1。

样例输入
3 4
1121
1211
2211
样例输出
1
样例输入
3 4
1122
1221
2211
样例输出
-1
样例输入
5 6
112121
122221
221212
211122
111121
样例输出
5
评测用例规模与约定
对于 50% 的评测用例，2 <= n, m <= 20。

对于所有评测用例，2 <= n, m <= 300。

思路：这道题就是熟为人知的DFS了，其实我感觉用BFS也可以的，不过这里有几部分需要剪枝，剪枝才能得到更好的成绩的。

比如我们需要判断到当前路径的最优值，如果比最优值大了，说明这条路径不对，我们就可以直接剪枝剪掉，我们还可以判断如果当前就和最优的结果一样的话，那还没到终点就得到了这个值，后面肯定是大于等于的，所以我们也进行剪枝。

n,m = map(int,input().split())

g = []
for _ in range(n):
    g.append([int(x) for x in input()])

f = [(1,0),(-1,0),(0,1),(0,-1)] # 上下左右

visit = [[0]*m for _ in range(n)]
temp = [[float('inf')]*m for _ in range(n)]
res = float('inf')
# dfs x,y是起点，t是已经经过了2，s是已有最少的经过2的次数
def dfs(x,y,t,s):
    if x == n-1 and y == m-1:
        global res
        res = min(res,s)
        return 

    if s < temp[x][y]:
        temp[x][y] = s
    else:
        return
    for tx,ty in f:
        dx,dy = tx+x,ty+y
        if 0<= dx < n and 0<= dy < m and visit[dx][dy]==0:
            if g[dx][dy] == 2:
                if t == 1: continue # 经过两次
                if s == res: continue # 当前和最优相等，之后肯定是大于等于
                visit[dx][dy] = 1
                dfs(dx,dy,1,s + 1)
                visit[dx][dy] = 0
            else:
                visit[dx][dy] = 1
                dfs(dx,dy,0,s)
                visit[dx][dy] = 0

visit[0][0] = 1
dfs(0,0,0,0)
if res == float('inf'):
    print(-1)
else:
    print(res)