第16届蓝桥杯模拟赛3 python组

思路和答案不保证正确

1.填空

如果一个数 p 是个质数，同时又是整数 a 的约数，则 p 称为 a 的一个质因数。

请问， 2024 的最大的质因数是多少？

因为是填空题，所以直接枚举2023~2 ，第一个即是质数也是2024的因数的数就是答案。

1
2
3
4
5
6
7
8
9
10
11
def isprime(x):
    for i in range(2,int(x ** 0.5)+1):
        if(x % i == 0):
            return False
    return True
for i in range(2023,1,-1):
    if(2024 % i == 0 and isprime(i)):
        print(i)
# 23
# 11
# 2

2.填空

对于两个整数 a, b，既是 a 的整数倍又是 b 的整数倍的数称为 a 和 b 的公倍数。公倍数中最小的正整数称为 a 和 b 的最小公倍数。

请问， 2024 和 1024 的最小公倍数是多少？

经典求lcm: $lcm(a,b) = \frac{a b}{ gcd(a b)}$

1
2
3
4
5
6
7
def gcd(x,y):
    if(y == 0): return x
    return gcd(y,x % y)
def lcm(x,y):
    return x * y // gcd(x,y)
print(lcm(2024,1024))
## 259072

(python3.9版本以后的math库中含有lcm函数可以直接调用)

1
2
3
import math
print(math.lcm(2024,1024))
## 259072

3.填空

如果一个数 p 是个质数，同时又是整数 a 的约数，则 p 称为 a 的一个质因数。

请问， 2024 的所有质因数的和是多少？

第一个填空使用的代码已经计算出了2024的质因数为：23,11,8,4,2 ，加到一起就可以了

1
2
3
4
5
6
7
8
9
10
11
def isprime(x):
    for i in range(2,int(x ** 0.5)+1):
        if(x % i == 0):
            return False
    return True
s = 0
for i in range(2023,1,-1):
    if(2024 % i == 0 and isprime(i)):
        s = s + i
print(s)
## 36

4.填空

请问，在不超过 2024 的数中，最大的质数是多少？

枚举2023~2，找到第一个质数

1
2
3
4
5
6
7
8
9
10
11
def isprime(x):
    for i in range(2,int(x ** 0.5)+1):
        if(x % i == 0):
            return False
    return True
s = 0
for i in range(2023,1,-1):
    if(isprime(i)):
        print(i)
        break
## 2017

5.填空

如果两个整数 a, b 除了 1 以外，没有其它的公约数，则称整数 a 与 b 互质。

请问，与 2024 互质的数中（包括1），第 2024 小的数是多少？

while循环从1开始找满足$gcd(x,2024) == 1$ 的数，找第2024个

1
2
3
4
5
6
7
8
9
10
11
def gcd(x,y):
    if(y == 0): return x
    return gcd(y,x % y)
cnt = 0
p = 0
while(cnt < 2024):
    p += 1
    if(gcd(p,2024) == 1):
        cnt += 1
print(p)
## 4655

6.填空

对于字符串 S=ANQNANBNQNANQNQNBNINQNQNANQNINANQNANBNQNANQNQNBNBNQNQNANQNINANQNANBNQNANQNQNBNINQNQNANQNINBNQNANBNQN ，请找到 S 的一个长度不超过 10 的子串 A，使得（A的长度）乘以（A在S中出现的次数）最大。

请问这个子串是什么？（如果有多个满足条件的，请回答字典序最小的）。

字符串不长，直接枚举所有长度不超过10的子串，然后将他们的出现次数记录在字典中，然后在字典中找答案就好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
s = "ANQNANBNQNANQNQNBNINQNQNANQNINANQNANBNQNANQNQNBNBNQNQNANQNINANQNANBNQNANQNQNBNINQNQNANQNINBNQNANBNQN"
dic = {}
for length in range(1,11):
    for i in range(0,len(s) - length):
        dic[s[i:i+length]] = dic.get(s[i:i+length],0) + 1
ansstr = ""
ansnum = 0
for s,cnt in dic.items():
    num = cnt * len(s)
    if(num > ansnum) or (num == ansnum and s < ansstr):
        ansstr = s
        ansnum = num
print(ansstr)
# NQN

7.填空

如果一个字符串中只包含字符 0 和字符 1，则称为一个 01 串（包含全为 0 的串和全为 1 的串）。

请问有多少个长度为 24 的 01 串，满足任意 5 个连续的位置中不超过 3 个位置的值为 1 。

长度为24的01串总共有$2^{24}$ 个，大约$1.7*10^7$ , 可以花点时间暴力枚举所有的字符串（反正是填空题）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import time
def check(x):
    lst = []
    for i in range(0,24):
        if(x & ( 1 << i)):
            lst.append(i)
    if(len(lst)<=2):
        return True
    for i in range(len(lst)-2):
        if(lst[i+2] - lst[i]<= 4):
            return False
    return True
ans = 0
tik = time.time()
for x in range(1<<24):
    # 这些01串可以用0~(2**24-1)的二进制数表示
    if(check(x)):
        ans += 1
tok = time.time()
print(tok-tik) # 花了25.859452724456787秒运行程序
print(ans) # 最终答案是162165

也可以使用dfs来解决本题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import time
lis = [] # 存储当前数的1的位置
ans = 0
def dfs(step):
    global ans
    if(step == 25):
        ans += 1
        return 
    if(len(lis) < 2 or step - lis[-2] > 4):
        lis.append(step) # 选1
        dfs(step + 1) 
        lis.pop() # 还原现场
    dfs(step + 1) # 选0
tic = time.time()
dfs(1)
tok = time.time()
print(tok - tic)# 花了0.04025077819824219秒运行程序
print(ans) # 最终答案是162165

8. 玉米地

题意

【问题描述】

小蓝种了一块玉米地，玉米地长 n 米，宽 m 米，每平方米产玉米 a 千克。请问小蓝的玉米地一共能产多少千克玉米？

【输入格式】

输入三行。第一行包含一个正整数 n ，第二行包含一个正整数 m ，第三行包含一个正整数 a 。

【输出格式】

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

【样例输入】

1
2
3
20
24
900

【样例输出】

1
432000

【评测用例规模与约定】

对于所有评测用例，1 <= n <= 1000, 1 <= m <= 1000, 1 <= a <= 2000。

思路

直接输出$nma$ 

1
2
3
4
n = int(input())
m = int(input())
a = int(input())
print(n * m * a)

9.再创新高

题意

【问题描述】

小蓝有一个数组 a[1], a[2], …, a[n]， 一个“再创新高”的位置是指一个位置 p ，a[p] 的值比之前每个位置的值都大。

请求出小蓝的数组中有多少个再创新高的位置。

【输入格式】

输入的第一行包含一个整数 n 。

第二行包含 n 个整数，相邻数之间使用一个空格分隔，依次表示 a[1], a[2], …, a[n] 。

【输出格式】

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

【样例输入】

1
2
8
1 2 3 4 5 6 6 6

【样例输出】

1
6

【样例输入】

1
2
9
3 2 1 6 5 4 9 8 7

【样例输出】

1
3

【评测用例规模与约定】

对于 30% 的评测用例，1 <= n <= 100，0 <= a[i] <= 1000。

对于 60% 的评测用例，1 <= n <= 1000，0 <= a[i] <= 1000。

对于所有评测用例，1 <= n <= 10000，0 <= a[i] <= 1000000。

思路

枚举数组，不断记录max值，每当max更新就让答案加一

1
2
3
4
5
6
7
8
9
n = int(input())
lst = list(map(int,input().split()))
mx = -1
ans = 0
for x in lst:
    if(x > mx):
        ans += 1
        mx = x
print(ans)

10.四个字符串拼接

题意

【问题描述】

给定四个字符串 a, b, c, d，请将这四个字符串按照任意顺序依次连接拼成一个字符串。

请问拼成的字符串字典序最小是多少？

【输入格式】

输入四行，每行包含一个字符串。

【输出格式】

输出一行包含一个字符串，表示答案。

【样例输入】

1
2
3
4
LAN
LAN
QIAO
BEI

【样例输出】

1
BEILANLANQIAO

【评测用例规模与约定】

对于所有评测用例，输入的字符串非空串，由大写字母组成，长度不超过 1000 。

思路

四个字符串拼接只有$A_4^4$ 种可能，直接枚举所有可能的情况，找到最小的字符串即可。

将四个字符串装入一个列表中，然后使用itertools库中的permutations函数来生成所有可能的排列

1
2
3
4
5
6
7
8
9
10
import itertools
lst = []
for i in range(4):
    s = input()
    lst.append(s)
per = itertools.permutations(lst) # 生成一个包含所有排列情况的可迭代对象
ans = "".join(lst) # 拼接列表中的字符串
for i in per:
    ans = min(ans,"".join(i))
print(ans)

更好的解法

如果字符串数量增多，全排列的数量会大大增长导致我们无法枚举所有的可能。我们可以考虑直接找到最优的字符串。

我们假设字符串目前拼接顺序如下S1,a,b,S2 ，其中a,b 是单元字符串，而S1,S2则分别表示其他字符串拼接后的串。现在我们考虑交换a和b的位置能否使得整个字符串的字典序更小：

显而易见当a+b<b+a时，a在前时字典序更小，b+a<a+b 时交换a和b的位置能够使得最终的字符串字典序更小。 （此处的+ 表示字符串的拼接，> , < 表示字典序比较）

于是我们按照上述的比较规则对这个字符串数组进行排序，最终的顺序就是答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from functools import cmp_to_key
lst = []
for i in range(4):
    s = input()
    lst.append(s)
def cmp(s1,s2): # 比较函数
    if(s1+s2 < s2+s1):
        return -1 # -1表示不需要交换位置
    elif(s1+s2 > s2+s1):
        return 1 # 1表示需要交换位置
    else :
        return 0
lst.sort(key = cmp_to_key(cmp))
print("".join(lst))

11.领取礼物

题意

【问题描述】

蓝桥村正在给村民们发放礼物。礼物通过一个礼物发放机完成。

村民们在机器前排着队领取礼物。

每个礼物有一个价值 v[i] ，有的高，有的低。每位村民有自己对于礼物的期望值 e[i] 。

礼物发放机每次会显示一个礼物，如果礼物的价值大于等于村民的期望值，村民就会高兴地把礼物拿走，并离开礼物发放机。如果礼物的价值比村民的期望值低，村民会让这个礼物取消，并让礼物发放机显示下一个礼物，并重新检查是否满足期望。村民会重复让礼物发放机显示下⼀个礼物，直到礼物发放机没有更多可以显示的礼物或礼物的价值大于等于自己的期望值。

如果礼物发放机中的所有礼物都显示完了，那么还没领到礼物的村民就无法领取礼物了。

如果所有的村民都领到了礼物，而礼物发放机还有礼物显示，村民们也不会再领取礼物。

现在，小蓝知道了每位村民的期望值，也知道了礼物发放机上礼物的显示顺序，请问总共有多少村民拿到了礼物？

【输入格式】

输入的第一行包含一个整数 n ，表示村民的个数。

第二行包含 n 个整数，相邻数之间使用一个空格分隔，依次表示排队的每位村民的期望值 e[i] 。

第三行包含一个整数 m ，表示礼物发放机会显示的礼物个数。

第四行包含 m 个整数，相邻数之间使用一个空格分隔，依次表示礼物发放机显示的礼物的价值 v[i] 。

【输出格式】

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

【样例输入】

1
2
3
4
6
6 5 5 3 6 0
9
9 9 8 2 4 4 3 5 3

【样例输出】

1
4

【样例说明】

前 4 位村民依次取到了第 1, 2, 3, 5 件礼物。后面的礼物未能满足第 5 位村民。

【评测用例规模与约定】

对于 30% 的评测用例，1 <= n, m <= 20 ， 0 <= e[i], v[i] <= 100 。

对于 60% 的评测用例，1 <= n, m <= 300 ， 0 <= e[i], v[i] <= 10000 。

对于所有评测用例，1 <= n, m <= 10000 ， 0 <= e[i], v[i] <= 1000000 。

思路

模拟礼物分发的过程即可

使用for循环按顺序枚举每个村民，对于每个村民使用while循环来查找符合的礼物。

当所有村民都领到礼物，或者所有的礼物都分发完就结束循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
n = int(input())
villager = list(map(int,input().split()))
m = int(input())
gift = list(map(int,input().split()))
p = 0 # 现在分发到哪个礼物了
ans = 0
for x in villager:
    while(p < len(gift) and gift[p] < x):
        p += 1
    if(p == len(gift)):# 如果所有礼物都发完了
        break
    ans += 1 # 有合适的礼物给他
    p += 1
print(ans)

12. 十字矩阵

题意

【问题描述】

小蓝有一个 n 行 m 列的矩阵 $a[i][j]$，他想着矩阵中找出一个“十”字形状的区域，使得区域内的值的和最大。

一个“十”字形状的区域可以由两个行号$r1$ 、 $r2$ 和两个列号 $c1$ 、 $c2$ 表示。“十”字的区域内包括第 $r1$ 行到 $r2$ 行的所有元素，以及第 $c1$ 列到 $c2$ 列的所有元素，既不在这几行也不在这几列的元素不在区域内。

为了保证是一个“十”字的形状，必须满足 $1 < r1 <= r2 < n，1 < c1 <= c2 < m$。

【输入格式】

输入的第一行包含两个整数 $n, m $，分别表示行数和列数。

接下来 $n$ 行，每行包含 $m$整数，相邻数之间使用一个空格分隔，依次表示矩阵的每行每列的值，本部分的第 $i$ 行第 $j$ 列表示 $a[i][j]$ 。

【输出格式】

输出一行包含一个整数，表示最大的和。

【样例输入】

1
2
3
4
5
6
5 6
1 -1 2 -2 3 -3
-1 2 -2 3 -3 4
2 -2 3 -3 4 -4
-2 3 -3 4 -4 5
3 -3 4 -4 5 -5

【样例输出】

1
14

【样例说明】

有两种方法可以得到最大的和。第一种是取 $r1=2, r2=4, c1=3, c2=5$，第二种是取$ r1=2, r2=4, c1=5, c2=5 $。

【评测用例规模与约定】

对于 30% 的评测用例，$3 <= n, m <= 30 ，-1000 <= a[i][j] <= 1000$ 。

对于 60% 的评测用例，$3 <= n, m <= 100 ，-1000 <= a[i][j] <= 1000$ 。

对于所有评测用例，$3 <= n <= 100, 3 <= m <= 5000 ，-1000 <= a[i][j] <= 1000 $。

思路

部分分

本题难度明显高于其他题目，可以考虑拿部分分：

暴力枚举所有十字的可能情况，然后使用二维前缀和来计算这个十字中所有数的加和。时间复杂度（$O(n^2m^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
n,m = list(map(int,input().split()))
matrix = []
matrix.append([0] * (m+1))
# 让matrix的有效数据从下标1开始,便于进行前缀和计算
for i in range(n):
    lst = [0]
    lst = lst + list(map(int,input().split()))
    matrix.append(lst)
# 求二维前缀和
for i in range(1,n+1):
    for j in range(1,m+1):
        matrix[i][j] = matrix[i][j] + matrix[i-1][j] + matrix[i][j-1] - matrix[i-1][j-1]
ans = -1e9
for r1 in range(2,n): ## 枚举十字
    for r2 in range(r1,n):
        for c1 in range(2,m):
            for c2 in range(c1,m):
                ## 计算十字的数字总和
                sm = 0
                sm += matrix[r2][m] - matrix[r1-1][m] # 十字的横
                sm += matrix[n][c2] - matrix[n][c1-1] # 十字的竖
                sm -= matrix[r2][c2] - matrix[r1-1][c2] - matrix[r2][c1-1] + matrix[r1-1][c1-1]# 减去重叠部分
                ans = max(ans,sm)
print(ans)

满分

观察满分的数据范围，发现n没有变大， 只有m变大了。

我们可以枚举$r1,r2$ 的取值，当$r1,r2$ 确定后， 本题就变为了“在一个一维数组中找和最大的子数组”问题。

这个子问题的复杂度是$O(m)$ 的，于是我们的总的复杂度就降到了$O(n^2m)$

如何用$O(n)$算法求解一维数组的最大子数组和？

例题：最大子数组和(leetcode)

对数组进行前缀和$sum$，那么子数组lst[l~r] 即 sum[r] - sum[l-1] ，显而易见当r确定后， 最小的$sum[l-1]$ 能产生最大的 sum[r] - sum[l-1], 于是我们可以枚举右端点r， 左端点$l$通过记录最小值得出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
n,m = list(map(int,input().split()))
matrix = []
matrix.append([0] * (m+1))
# 让matrix的有效数据从下标1开始,便于进行前缀和计算
for i in range(n):
    lst = [0]
    lst = lst + list(map(int,input().split()))
    matrix.append(lst)
pre = matrix.copy()
# 求二维前缀和
for i in range(1,n+1):
    for j in range(1,m+1):
        pre[i][j] = pre[i][j] + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1]
        
ans = -1e9
for r1 in range(2,n):
    for r2 in range(r1,n):
        x = pre[r2][m] - pre[r1-1][m] # 十字的横
        summ = [0]  # 二维前缀和压缩到一维,并减去"横"
        for col in range(1,m+1):
            summ.append(pre[n][col] - (pre[r2][col] - pre[r1-1][col])
        minn = 0
        res = -1e9 # 子数组最大和
        for i in range(1,len(summ)):
            res = max(res,summ[i]-minn)
            minn = min(minn,summ[i])
        ans = max(ans,res + x)
print(ans)