当前位置:首页 » 《我的小黑屋》 » 正文

2024第十六届蓝桥杯模拟赛(第二期)-Python

8 人参与  2024年12月03日 16:01  分类 : 《我的小黑屋》  评论

点击全文阅读


提示:前五题是填空,不需要提交代码。


知识点:

1、质因数、质数、约数。

2、动态规划(dp)。

3、思维。 


 

一、【问题描述】

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

请问, 2024 的最大的质因数是多少?

【答案提交】

这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

1、思路:质数的判定https://www.acwing.com/file_system/file/content/whole/index/content/4443622/

2、代码:

def is_prime(x):    if x == 1:        return False    for i in range(2, int(x ** 0.5) + 1):        if x % i == 0:            return False    return Truefor i in range(2023,1,-1):    if(2024%i==0):        if(is_prime(i)):            print(i)            break        else:            continue

3、结果:23

 


 

二、【问题描述】

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

请问, 2024 和 1024 的最小公倍数是多少?

【答案提交】

这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

1、思路:暴力

2、代码:

res=2024while(1):    if(res%2024==0 and res%1024==0):        print(res)        break    else:        res+=1

3、结果:259072

 


三、【问题描述】

两个数按位异或是指将这两个数转换成二进制后,最低位与最低位异或作为结果的最低位,次低位与次低位异或作为结果的次低位,以此类推。

例如,3 与 5 按位异或值为 6 。

请问,有多少个不超过 2024 的正整数,与 2024 异或后结果小于 2024 。

【答案提交】

这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

1、思路:暴力

2、代码:

count = 0for x in range(1, 2025):    if (x ^ 2024) < 2024:        count += 1print(count)

3、结果:2001

 


四、【问题描述】

小蓝有一个整数,初始值为 1 ,他可以花费一些代价对这个整数进行变换。

小蓝可以花费 1 的代价将整数增加 1 。

小蓝可以花费 3 的代价将整数增加一个值,这个值是整数的数位中最大的那个(1 到 9)。

小蓝可以花费 10 的代价将整数变为原来的 2 倍。

例如,如果整数为 16,花费 3 将整数变为 22 。

又如,如果整数为 22,花费 1 将整数变为 23 。

又如,如果整数为 23,花费 10 将整数变为 46 。

请问,如果要将整数从初始值 1 变为 2024,请问最少需要多少代价?

【答案提交】

这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

1、思路:动态规划


(1)初始化: 创建一个长度为y+1的dp数组,dp[i]表示将1变成i的最小代价,初始化为无穷大,dp[1] = 0。
(2)遍历每个数: 遍历从1到y,对于每个数i,尝试三种操作。
(3)加1操作: 若i + 1 <= y,更新dp[i + 1]为min(dp[i + 1], dp[i] + 1)。
(4)加最大数位操作: 计算当前数i的最大数位max_digit,若i + max_digit <= y,更新dp[i + max_digit]。
(5)乘2操作: 若i * 2 <= y,更新dp[i * 2]为min(dp[i * 2], dp[i] + 10)。
(6)返回结果: 最终返回dp[y],即将1变为y的最小代价。

 

2、代码:

def min_cost(y):    dp=[float('inf')]*(y+1)    # dp[x]表示将整数1变为x的最小代价    dp[1]=0    for i in range(1, y + 1):        #加1        if i+1<=y:            dp[i+1]=min(dp[i+1], dp[i]+1)        #加最大数位        max_digit=int(max(str(i)))  # 找到当前数的最大数位        if i+max_digit<=y:            dp[i+max_digit]=min(dp[i+max_digit],dp[i]+3)        #乘以 2        if i*2<=y:            dp[i*2]=min(dp[i*2],dp[i]+10)    return dp[y]result=min_cost(2024)print(result)

3、结果:79

 


 

五、【问题描述】

小蓝有以下 100 个整数:

534, 386, 319, 692, 169, 338, 521, 713, 640, 692, 969, 362, 311, 349, 308, 357, 515, 140, 591, 216,

57, 252, 575, 630, 95, 274, 328, 614, 18, 605, 17, 980, 166, 112, 997, 37, 584, 64, 442, 495,

821, 459, 453, 597, 187, 734, 827, 950, 679, 78, 769, 661, 452, 983, 356, 217, 394, 342, 697, 878,

475, 250, 468, 33, 966, 742, 436, 343, 255, 944, 588, 734, 540, 508, 779, 881, 153, 928, 764, 703,

459, 840, 949, 500, 648, 163, 547, 780, 749, 132, 546, 199, 701, 448, 265, 263, 87, 45, 828, 634.

小蓝想从中选出一部分数求和,使得和是 24 的倍数,请问这个和最大是多少?

【答案提交】

这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

1、思路:

(1)初始化DP数组:定义dp[i]表示当前可以得到的和,对24取余后等于i的最大和。初始化时,dp[0] = 0,表示和为0时,余数为0;其他dp[i]初始化为负无穷,表示不可达状态。
(2)遍历数组:对每个数num,更新dp数组。遍历当前所有的余数i,如果dp[i]是有效值(不为负无穷),则计算当前和加上num后的余数new_i,并更新dp[new_i]为当前和的最大值。
(3)返回结果:最终,返回dp[0],即和对24取余为0时的最大和。如果dp[0]是负无穷,说明无法组成和为0的情况,返回0。

2、代码:

def Max_sum(nums):    # dp[i] 表示和对24取余等于 i 的最大和。    dp = [-float('inf')] * 24    dp[0] = 0  # 初始条件,和为0时,余数为0    for num in nums:        # 创建一个临时数组来保存更新后的结果        temp = dp[:]        for i in range(24):            if dp[i] != -float('inf'):                # 计算当前数添加到现有和后的余数                new_sum = dp[i] + num                new_i = new_sum % 24                temp[new_i] = max(temp[new_i], new_sum)        dp = temp    return dp[0] if dp[0] >= 0 else 0nums = [    534, 386, 319, 692, 169, 338, 521, 713, 640, 692, 969, 362, 311, 349, 308, 357, 515, 140, 591, 216,    57, 252, 575, 630, 95, 274, 328, 614, 18, 605, 17, 980, 166, 112, 997, 37, 584, 64, 442, 495,    821, 459, 453, 597, 187, 734, 827, 950, 679, 78, 769, 661, 452, 983, 356, 217, 394, 342, 697, 878,    475, 250, 468, 33, 966, 742, 436, 343, 255, 944, 588, 734, 540, 508, 779, 881, 153, 928, 764, 703,    459, 840, 949, 500, 648, 163, 547, 780, 749, 132, 546, 199, 701, 448, 265, 263, 87, 45, 828, 634]result = Max_sum(nums)print(result)

3、结果:49176

 


六、【问题描述】

小蓝准备请自己的朋友吃饭。小蓝朋友很多,最终吃饭的人总数达 2024 人(包括他自己)。

请问如果每桌最多坐 n 人,最少要多少桌才能保证每个人都能吃饭。

【输入格式】

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

【输出格式】

输出一行包含一个整数,表示最少的桌数。

【样例输入】

10

【样例输出】

203

【样例输入】

8

【样例输出】

253

【评测用例规模与约定】

对于所有评测用例,1 <= n <= 2024。

1、思路:无

2、代码:

n=int(input())res=2024//nif 2024%n != 0:    res+=1print(res)

 


七、【问题描述】

小蓝有一个数组 a[1], a[2], ..., a[n] ,请求出数组中值最小的偶数,输出这个值。

【输入格式】

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

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

【输出格式】

输出一行,包含一个整数,表示答案。数据保证数组中至少有一个偶数。

【样例输入】

99 9 8 2 4 4 3 5 3

【样例输出】

2

【样例输入】

54321 2143 1324 1243 4312

【样例输出】

1324

【评测用例规模与约定】

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

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

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

1、思路:可以暴力

2、代码:

n=int(input())a=list(map(int,input().split(' ')))res=1e6+10for x in a:    if x%2==0:        res=min(res,x)print(res)

 


 

八、【问题描述】

一个字符串包含LANQIAO是指在字符串中能取出几个字符,将他们按照在原串中的位置顺序摆成一排后字符串为 LANQIAO 。即字符串包含 LANQIAO 是指 LANQIAO 是这个串的子序列。

例如:LLLLLANHAHAHAQLANIIIIALANO 中包含 LANQIAO 。

又如:OAIQNAL 中不包含 LANQIAO 。

给点一个字符串,判断字符串中是否包含 LANQIAO 。

【输入格式】

输入一行包含一个字符串。

【输出格式】

如果包含 LANQIAO ,输出一个英文单词 YES ,否则输出一个英文单词 NO 。

【样例输入】

LLLLLANHAHAHAQLANIIIIALANO

【样例输出】

YES

【样例输入】

OAIQNAL

【样例输出】

NO

【评测用例规模与约定】

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

1、思路:

(1)初始化指针:设置i = 0,用于跟踪T中的字符位置。
(2)遍历S:逐个检查S中的字符,判断是否与T[i]相等。如果相等,则指针i向后移动,检查下一个字符。
(3)判断是否匹配完T:如果i达到了7,说明T中的所有字符都在S中按顺序找到了,输出"YES"。
(4)如果遍历完S后没有找到完整的T,则输出"NO"。

2、代码:

S=input()T="LANQIAO"i=0for s in S:    if s==T[i]:        i+=1        if i==7:            breakif i==7:    print("YES")else:    print("NO")

 


九、【问题描述】

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

具体讲,一个“口”字形状的区域可以由两个坐标 (x1, y1) 和 (x2, y2) 确定,满足:

1 <= x1 < x2 <= n ;1 <= y1 < y2 <= m ;x2 - x1 = y2 - y1 。

对应的区域由满足以下条件之一的点 (x, y) 构成:

x1 <= x <= x2,且 y = y1 ,对应“口”的左边一竖;y1 <= y <= y2,且 x = x1 ,对应“口”的上面一横;x1 <= x <= x2,且 y = y2 ,对应“口”的右边一竖;y1 <= y <= y2,且 x = x2 ,对应“口”的下面一横。

请注意有些点满足以上条件的多个,例如左上角的点 (x1, y1) ,在计算时算为一个点。

区域上的值是指对应区域的所有点的值,即“口”字的框上的值,不含框内和框外的值。

【输入格式】

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

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

【输出格式】

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

【样例输入】

5 61 -1 2 -2 3 -3-1 2 -2 3 -3 42 -2 3 -3 4 -4-2 3 -3 4 -4 53 -3 4 -4 5 -5

【样例输出】

4

【样例说明】

取 (x1, y1) = (1, 1) , (x2, y2) = (5, 5) 可得到最大值。

【评测用例规模与约定】

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

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

对于所有评测用例,1 <= n, m <= 300 ,-1000 <= a[i][j] <= 1000 。

1、思路:

(1)遍历所有左上角位置 (x1, y1):从矩阵的每个可能的左上角点开始,计算可能的“口”字形区域。
(2)遍历所有可能的边长 l:对于每个左上角点 (x1, y1),遍历不同的边长 l,计算对应的右下角 (x2, y2)。
(3)计算“口”字形区域的和:
      通过四条边(左竖边、上横边、右竖边、下横边)计算区域和。
      减去重复计算的四个角点。
(4)更新最大和:每次计算出新的区域和时,更新当前最大值。
(5)返回结果:返回所有可能的“口”字形区域的最大和。

2、代码:

def f(n,m,G):    res=float('-inf')    # 遍历所有可能的左上角点 (x1,y1)    for x1 in range(n-1):        for y1 in range(m-1):            # 遍历所有可能的边长 l            L=min(n-x1,m-y1)            for l in range(1,L):                x2 = x1 + l                y2 = y1 + l                # 计算这个“口”字形区域的和                s = 0                # 左竖边 (x1, y1) 到 (x2, y1)                for x in range(x1, x2 + 1):                    s+=G[x][y1]                # 上横边 (x1, y1) 到 (x1, y2)                for y in range(y1, y2 + 1):                    s+=G[x1][y]                # 右竖边 (x2, y1) 到 (x2, y2)                for x in range(x1, x2 + 1):                    s+=G[x][y2]                # 下横边 (x1, y2) 到 (x2, y2)                for y in range(y1, y2 + 1):                    s+=G[x2][y]                # 减去重复的四个角点 (x1, y1), (x1, y2), (x2, y1), (x2, y2)                s-=G[x1][y1]                s-=G[x1][y2]                s-=G[x2][y1]                s-=G[x2][y2]                # 更新最大值                res= max(res,s)    return resn,m=map(int,input().split())G=[list(map(int,input().split())) for _ in range(n)]print(f(n,m,G))

 


十、【问题描述】

小蓝正在玩一个寻宝游戏。寻宝游戏在一个方格图上进行。方格图中的每一个格子都有一个坐标 (r, c),其中越往北 r 越小,越往南 r 越大,越往东 c 越大,越往西 c 越小。南北相邻方格的 c 坐标相同,r 坐标差一。东西相邻方格的 r 坐标相同, c 坐标差一。

游戏开始时,小蓝站在 (0, 0) 处,面向北边。游戏区域无限大,且没有障碍。每一步,小蓝控制自己的角色走一步,他可以有如下三种选择:

向前走:朝现在的方向前进到相邻的方格中,并保持当前的方向。向左走:向左转90度,并前进到相邻的方格中(即进入到原来左边的方格),面向的方向变为了原来的左边。向右走:向右转90度,并前进到相邻的方格中(即进入到原来右边的方格),面向的方向变为了原来的右边。

小蓝玩了一会儿,一共走了 n 步,他记录了自己的每一个动作。但是他没有找到宝藏。他怀疑前面的某一步出现了失误。他想知道,如果他改变之前的某一步,能到的位置有哪些。由于这个太复杂,他想知道最终到的位置(第 n 步后到的位置)有多少种。

【输入格式】

输入的第一行包含一个整数 n ,表示小蓝走了 n 步。

第二行包含一个长度为 n 的由大写字母组成的字符串,依次表示小蓝走的每一步。字母 F 、 L 、 R 分别表示对应的步是向前走、向左走、向右走。

【输出格式】

输出一行,包含一个整数,表示如果改变某一步,可以到的位置的种类数。

【样例输入】

3FLR

【样例输出】

6

【样例说明】

如果不改变,三步依次走到:(-1, 0), (-1, -1), (-2, -1) ,最终位置为 (-2, -1) 。

如果第一步改成 L,三步依次走到:(0, -1), (1, -1), (1, -2) ,最终位置为 (1, -2) 。

如果第一步改成 R,三步依次走到:(0, 1), (-1, 1), (-1, 2) ,最终位置为 (-1, 2) 。

如果第二步改成 F,三步依次走到:(-1, 0), (-2, 0), (-2, 1) ,最终位置为 (-2, 1) 。

如果第二步改成 R,三步依次走到:(-1, 0), (-1, 1), (0, 1) ,最终位置为 (0, 1) 。

如果第三步改成 F,三步依次走到:(-1, 0), (-1, -1), (-1, -2) ,最终位置为 (-1, -2) 。

如果第三步改成 L,三步依次走到:(-1, 0), (-1, -1), (0, -1) ,最终位置为 (0, -1) 。

共有 6 种不同的最终位置。

【样例输入】

4RRRR

【样例输出】

6

【样例说明】

有 8 种改变方法:

改为 FRRR ,最终位置为 (0, 0);

改为 LRRR ,最终位置为 (0, 0);

改为 RFRR ,最终位置为 (1, 1);

改为 RLRR ,最终位置为 (0, 2);

改为 RRFR ,最终位置为 (2, 0);

改为 RRLR ,最终位置为 (2, 2);

改为 RRRF ,最终位置为 (1, -1);

改为 RRRL ,最终位置为 (2, 0)。

不同的最终位置共有 6 种。

【评测用例规模与约定】

对于 30% 的评测用例,1 <= n <= 20。

对于 60% 的评测用例,1 <= n <= 1000。

对于所有评测用例,1 <= n <= 100000。

1、思路:应该会超时,不能满分,后续优化

1.输入与初始化:
     读取输入的路径长度 n 和移动指令串 moves。
     定义方向数组 directions 来表示四个方向(北、东、南、西),以及一个 direction 变量来表示当前方向(0:北,1:东,2:南,3:西)。
    初始位置为 (0, 0),并记录该位置和方向。
2.模拟路径:
对于每个移动指令,按顺序执行:
   'F':向当前方向前进一格。
   'L':左转,改变方向。
   'R':右转,改变方向。
每一步记录当前位置 (x, y) 和当前方向 direction。
3.尝试替换每一步指令:
   对每个指令位置,尝试用 'F', 'L', 'R' 替换原指令,并重新模拟一遍路径,计算不同的最终位置。
   如果替换后的路径到达的位置不在之前的路径中,则把它加入结果集合 result。
4.输出结果:
   最后,输出集合 result 的大小,即不同的最终位置数量。

2、代码:

def solve():    n = int(input())    moves = input().strip()    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]    # 起始位置    x, y = 0, 0    # 用方向表示北 (0), 东 (1), 南 (2), 西 (3)    direction = 0  # 初始方向是北    # 先记录每一步的 (x, y) 和方向    positions = [(x, y, direction)]    for move in moves:        if move == 'F':            x += directions[direction][0]            y += directions[direction][1]        elif move == 'L':            direction = (direction - 1) % 4            x += directions[direction][0]            y += directions[direction][1]        elif move == 'R':            direction = (direction + 1) % 4            x += directions[direction][0]            y += directions[direction][1]        positions.append((x, y, direction))    # 使用集合来记录所有可能的最终位置    result = set()    # 对于每一步,我们尝试更改当前的指令并计算结果    for i in range(n):        original_move = moves[i]        original_x, original_y, original_direction = positions[i]        # 尝试改变为 F, L, R        for new_move in 'FLR':            if new_move == original_move:                continue            # 重新模拟替换后的路径            x, y, direction = 0, 0, 0  # 从原点开始            for j in range(n):                if j == i:                    if new_move == 'F':                        x += directions[direction][0]                        y += directions[direction][1]                    elif new_move == 'L':                        direction = (direction - 1) % 4                        x += directions[direction][0]                        y += directions[direction][1]                    elif new_move == 'R':                        direction = (direction + 1) % 4                        x += directions[direction][0]                        y += directions[direction][1]                else:                    move = moves[j]                    if move == 'F':                        x += directions[direction][0]                        y += directions[direction][1]                    elif move == 'L':                        direction = (direction - 1) % 4                        x += directions[direction][0]                        y += directions[direction][1]                    elif move == 'R':                        direction = (direction + 1) % 4                        x += directions[direction][0]                        y += directions[direction][1]            result.add((x, y))    # 输出不同的最终位置数目    print(len(result))solve()

 代码仅供参考,如有错误,感谢指正!

 

 

 


点击全文阅读


本文链接:http://m.zhangshiyu.com/post/196030.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1