网站服务器哪里的好,1688网站怎样做推广,wordpress自带hosts文件,字体中国设计网第16届蓝桥杯模拟赛3 python组
思路和答案不保证正确
1.填空
如果一个数 p 是个质数#xff0c;同时又是整数 a 的约数#xff0c;则 p 称为 a 的一个质因数。
请问#xff0c; 2024 的最大的质因数是多少#xff1f;
因为是填空题#xff0c;所以直接枚举2023~2 同时又是整数 a 的约数则 p 称为 a 的一个质因数。
请问 2024 的最大的质因数是多少
因为是填空题所以直接枚举2023~2 第一个即是质数也是2024的因数的数就是答案。
def isprime(x):for i in range(2,int(x ** 0.5)1):if(x % i 0):return Falsereturn True
for i in range(2023,1,-1):if(2024 % i 0 and isprime(i)):print(i)
# 23
# 11
# 22.填空
对于两个整数 a, b既是 a 的整数倍又是 b 的整数倍的数称为 a 和 b 的公倍数。公倍数中最小的正整数称为 a 和 b 的最小公倍数。
请问 2024 和 1024 的最小公倍数是多少
经典求lcm: l c m ( a , b ) a ∗ b g c d ( a ∗ b ) lcm(a,b) \frac{a * b}{ gcd(a* b)} lcm(a,b)gcd(a∗b)a∗b
def gcd(x,y):if(y 0): return xreturn gcd(y,x % y)
def lcm(x,y):return x * y // gcd(x,y)
print(lcm(2024,1024))
## 259072(python3.9版本以后的math库中含有lcm函数可以直接调用)
import math
print(math.lcm(2024,1024))
## 2590723.填空
如果一个数 p 是个质数同时又是整数 a 的约数则 p 称为 a 的一个质因数。
请问 2024 的所有质因数的和是多少
第一个填空使用的代码已经计算出了2024的质因数为23,11,8,4,2 加到一起就可以了
def isprime(x):for i in range(2,int(x ** 0.5)1):if(x % i 0):return Falsereturn True
s 0
for i in range(2023,1,-1):if(2024 % i 0 and isprime(i)):s s i
print(s)
## 364.填空
请问在不超过 2024 的数中最大的质数是多少
枚举2023~2找到第一个质数
def isprime(x):for i in range(2,int(x ** 0.5)1):if(x % i 0):return Falsereturn True
s 0
for i in range(2023,1,-1):if(isprime(i)):print(i)break
## 20175.填空
如果两个整数 a, b 除了 1 以外没有其它的公约数则称整数 a 与 b 互质。
请问与 2024 互质的数中包括1第 2024 小的数是多少
while循环从1开始找满足 g c d ( x , 2024 ) 1 gcd(x,2024) 1 gcd(x,2024)1 的数找第2024个
def gcd(x,y):if(y 0): return xreturn gcd(y,x % y)
cnt 0
p 0
while(cnt 2024):p 1if(gcd(p,2024) 1):cnt 1
print(p)
## 46556.填空
对于字符串 SANQNANBNQNANQNQNBNINQNQNANQNINANQNANBNQNANQNQNBNBNQNQNANQNINANQNANBNQNANQNQNBNINQNQNANQNINBNQNANBNQN 请找到 S 的一个长度不超过 10 的子串 A使得A的长度乘以A在S中出现的次数最大。
请问这个子串是什么如果有多个满足条件的请回答字典序最小的。
字符串不长直接枚举所有长度不超过10的子串然后将他们的出现次数记录在字典中然后在字典中找答案就好
s ANQNANBNQNANQNQNBNINQNQNANQNINANQNANBNQNANQNQNBNBNQNQNANQNINANQNANBNQNANQNQNBNINQNQNANQNINBNQNANBNQN
dic {}
for length in range(1,11):for i in range(0,len(s) - length):dic[s[i:ilength]] dic.get(s[i:ilength],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 sansnum num
print(ansstr)
# NQN7.填空
如果一个字符串中只包含字符 0 和字符 1则称为一个 01 串包含全为 0 的串和全为 1 的串。
请问有多少个长度为 24 的 01 串满足任意 5 个连续的位置中不超过 3 个位置的值为 1 。
长度为24的01串总共有 2 24 2^{24} 224 个大约 1.7 ∗ 1 0 7 1.7*10^7 1.7∗107 , 可以花点时间暴力枚举所有的字符串反正是填空题
import time
def check(x):lst []for i in range(0,24):if(x ( 1 i)):lst.append(i)if(len(lst)2):return Truefor i in range(len(lst)-2):if(lst[i2] - lst[i] 4):return Falsereturn True
ans 0
tik time.time()
for x in range(124):# 这些01串可以用0~(2**24-1)的二进制数表示if(check(x)):ans 1
tok time.time()
print(tok-tik) # 花了25.859452724456787秒运行程序
print(ans) # 最终答案是162165也可以使用dfs来解决本题
import time
lis [] # 存储当前数的1的位置
ans 0
def dfs(step):global ansif(step 25):ans 1return if(len(lis) 2 or step - lis[-2] 4):lis.append(step) # 选1dfs(step 1) lis.pop() # 还原现场dfs(step 1) # 选0
tic time.time()
dfs(1)
tok time.time()
print(tok - tic)# 花了0.04025077819824219秒运行程序
print(ans) # 最终答案是1621658. 玉米地
题意
【问题描述】
小蓝种了一块玉米地玉米地长 n 米宽 m 米每平方米产玉米 a 千克。请问小蓝的玉米地一共能产多少千克玉米
【输入格式】
输入三行。第一行包含一个正整数 n 第二行包含一个正整数 m 第三行包含一个正整数 a 。
【输出格式】
输出一行包含一个整数表示答案。
【样例输入】
20
24
900【样例输出】
432000【评测用例规模与约定】
对于所有评测用例1 n 1000, 1 m 1000, 1 a 2000。
思路
直接输出 n ∗ m ∗ a n*m*a n∗m∗a
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] 。
【输出格式】
输出一行包含一个整数表示答案。
【样例输入】
8
1 2 3 4 5 6 6 6【样例输出】
6【样例输入】
9
3 2 1 6 5 4 9 8 7【样例输出】
3【评测用例规模与约定】
对于 30% 的评测用例1 n 1000 a[i] 1000。
对于 60% 的评测用例1 n 10000 a[i] 1000。
对于所有评测用例1 n 100000 a[i] 1000000。
思路
枚举数组不断记录max值每当max更新就让答案加一
n int(input())
lst list(map(int,input().split()))
mx -1
ans 0
for x in lst:if(x mx):ans 1mx x
print(ans)10.四个字符串拼接
题意
【问题描述】
给定四个字符串 a, b, c, d请将这四个字符串按照任意顺序依次连接拼成一个字符串。
请问拼成的字符串字典序最小是多少
【输入格式】
输入四行每行包含一个字符串。
【输出格式】
输出一行包含一个字符串表示答案。
【样例输入】
LAN
LAN
QIAO
BEI【样例输出】
BEILANLANQIAO【评测用例规模与约定】
对于所有评测用例输入的字符串非空串由大写字母组成长度不超过 1000 。
思路
四个字符串拼接只有 A 4 4 A_4^4 A44 种可能直接枚举所有可能的情况找到最小的字符串即可。
将四个字符串装入一个列表中然后使用itertools库中的permutations函数来生成所有可能的排列
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的位置能否使得整个字符串的字典序更小
显而易见当abba时a在前时字典序更小baab 时交换a和b的位置能够使得最终的字符串字典序更小。 此处的 表示字符串的拼接 , 表示字典序比较
于是我们按照上述的比较规则对这个字符串数组进行排序最终的顺序就是答案
from functools import cmp_to_key
lst []
for i in range(4):s input()lst.append(s)
def cmp(s1,s2): # 比较函数if(s1s2 s2s1):return -1 # -1表示不需要交换位置elif(s1s2 s2s1):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] 。
【输出格式】
输出一行包含一个整数表示答案。
【样例输入】
6
6 5 5 3 6 0
9
9 9 8 2 4 4 3 5 3【样例输出】
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循环来查找符合的礼物。
当所有村民都领到礼物或者所有的礼物都分发完就结束循环
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 1if(p len(gift)):# 如果所有礼物都发完了breakans 1 # 有合适的礼物给他p 1
print(ans)12. 十字矩阵
题意
【问题描述】
小蓝有一个 n 行 m 列的矩阵 a [ i ] [ j ] a[i][j] a[i][j]他想着矩阵中找出一个“十”字形状的区域使得区域内的值的和最大。
一个“十”字形状的区域可以由两个行号 r 1 r1 r1 、 r 2 r2 r2 和两个列号 c 1 c1 c1 、 c 2 c2 c2 表示。“十”字的区域内包括第 r 1 r1 r1 行到 r 2 r2 r2 行的所有元素以及第 c 1 c1 c1 列到 c 2 c2 c2 列的所有元素既不在这几行也不在这几列的元素不在区域内。
为了保证是一个“十”字的形状必须满足 1 r 1 r 2 n 1 c 1 c 2 m 1 r1 r2 n1 c1 c2 m 1r1r2n1c1c2m。
【输入格式】
输入的第一行包含两个整数 $n, m $分别表示行数和列数。
接下来 n n n 行每行包含 m m m整数相邻数之间使用一个空格分隔依次表示矩阵的每行每列的值本部分的第 i i i 行第 j j j 列表示 a [ i ] [ j ] a[i][j] a[i][j] 。
【输出格式】
输出一行包含一个整数表示最大的和。
【样例输入】
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【样例输出】
14【样例说明】
有两种方法可以得到最大的和。第一种是取 r 1 2 , r 2 4 , c 1 3 , c 2 5 r12, r24, c13, c25 r12,r24,c13,c25第二种是取$ r12, r24, c15, c25 $。
【评测用例规模与约定】
对于 30% 的评测用例 3 n , m 30 − 1000 a [ i ] [ j ] 1000 3 n, m 30 -1000 a[i][j] 1000 3n,m30−1000a[i][j]1000 。
对于 60% 的评测用例 3 n , m 100 − 1000 a [ i ] [ j ] 1000 3 n, m 100 -1000 a[i][j] 1000 3n,m100−1000a[i][j]1000 。
对于所有评测用例$3 n 100, 3 m 5000 -1000 a[i][j] 1000 $。
思路
部分分
本题难度明显高于其他题目可以考虑拿部分分
暴力枚举所有十字的可能情况然后使用二维前缀和来计算这个十字中所有数的加和。时间复杂度 O ( n 2 m 2 ) O(n^2m^2) O(n2m2)
n,m list(map(int,input().split()))
matrix []
matrix.append([0] * (m1))
# 让matrix的有效数据从下标1开始,便于进行前缀和计算
for i in range(n):lst [0]lst lst list(map(int,input().split()))matrix.append(lst)
# 求二维前缀和
for i in range(1,n1):for j in range(1,m1):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 0sm 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变大了。
我们可以枚举 r 1 , r 2 r1,r2 r1,r2 的取值当 r 1 , r 2 r1,r2 r1,r2 确定后 本题就变为了“在一个一维数组中找和最大的子数组”问题。
这个子问题的复杂度是 O ( m ) O(m) O(m) 的于是我们的总的复杂度就降到了 O ( n 2 m ) O(n^2m) O(n2m) 如何用 O ( n ) O(n) O(n)算法求解一维数组的最大子数组和
例题最大子数组和(leetcode)
对数组进行前缀和 s u m sum sum那么子数组lst[l~r] 即 sum[r] - sum[l-1] 显而易见当r确定后 最小的 s u m [ l − 1 ] sum[l-1] sum[l−1] 能产生最大的 sum[r] - sum[l-1], 于是我们可以枚举右端点r 左端点 l l l通过记录最小值得出。
n,m list(map(int,input().split()))
matrix []
matrix.append([0] * (m1))
# 让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,n1):for j in range(1,m1):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,m1):summ.append(pre[n][col] - (pre[r2][col] - pre[r1-1][col])minn 0res -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)
