当前位置:   article > 正文

第十四届蓝桥杯第三期模拟赛(python版)_小蓝有一个01矩阵。他打算将第一行第一列的 0 变为 2 。变化过程有传染性,每

小蓝有一个01矩阵。他打算将第一行第一列的 0 变为 2 。变化过程有传染性,每

总体难度不大,正赛肯定比这难。本人答案代码样例都能过,前五个填空题正确性应该都问题不大(有更好方法欢迎放出来!)。大题但可能有一些细节没有考虑到,时间复杂度这一方面是都考虑了的,大题仅供参考。有更好的方法的,欢迎讨论。


问题1

思维题,写代码也挺简单的,建议不用写。
两位数的最大16进制FF为255,最小的三位16进制AAA为2730,故为2730。


题目描述:

请找到一个大于 2022 的最小数,这个数转换成十六进制之后,所有的数位(不含前导 0)都为字母(A 到F)。请将这个数的十进制形式作为答案提交。

问题2

题目描述:

在 Excel 中,列的名称使用英文字母的组合。前 26 列用一个字母,依次为 A 到 Z,接下来 26*26 列使用两个字母的组合,依次为AA 到 ZZ。请问第 2022 列的名称是什么?

# ZZ = 26 + 26*26 = 702
# AAA = 703
count = 702
dist = {}
for i in range(65, 91):
    for j in range(65, 91):
        for k in range(65, 91):
            count += 1
            s = chr(i)+chr(j)+chr(k)
            dist[s] = count
            if count == 2022:
                print(s)  # 答案:'BYT'
# print(dist)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

问题3

思路:用python语言自带的时间处理函数很简单。


题目描述:

对于一个日期,我们可以计算出年份的各个数位上的数字之和,也可以分别计算月和日的各位数字之和。请问从 1900 年 1 月 1 日至 9999年 12 月 31 日,总共有多少天,年份的数位数字之和等于月的数位数字之和加日的数位数字之和。 例如,2022年11月13日满足要求,因为2+0+2+2=(1+1)+(1+3) 。 请提交满足条件的日期的总数量。

import datetime
date1 = datetime.date(1900, 1, 1)
date2 = datetime.date(9999, 12, 31)
count = 0
while date1 != date2:
   date1 += datetime.timedelta(days=1)
   s = str(date1)
   year, month, day = s[:4], s[5:7], s[8:]
   # print(year, month, day)
   s1, s2, s3 = 0, 0, 0
   for i in year:
       s1 += int(i)
   for i in month:
       s2 += int(i)
   for i in day:
       s3 += int(i)
   # print(s1, s2, s3)
   if s1 == s2 + s3:
       count += 1
print(count)  # 答案:70910


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

问题4

思路:用python自带的组合函数模拟就行,或者是两重循环。


题目描述:

小蓝有 30 个数,分别为:99, 22, 51, 63, 72, 61, 20, 88, 40, 21, 63, 30, 11, 18,
99, 12, 93, 16, 7, 53, 64, 9, 28, 84, 34, 96, 52, 82, 51, 77 。
  小蓝可以在这些数中取出两个序号不同的数,共有 30*29/2=435 种取法。请问这 435
种取法中,有多少种取法取出的两个数的乘积大于等于 2022 。

from itertools import *

a = [99, 22, 51, 63, 72, 61,
     20, 88, 40, 21, 63, 30,
     11, 18, 99, 12, 93, 16,
     7, 53, 64, 9, 28, 84,
     34, 96, 52, 82, 51, 77]
# print(len(a))
count = 0
for item in combinations(a, 2):
    if item[0]*item[1] >= 2022:
        count += 1
print(count)  # 答案:189
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

问题5

DFS,注意每重新枚举一个数字时,visted数组要全置False。


题目描述:

小蓝有一个 30 行 60 列的数字矩阵,矩阵中的每个数都是 0 或 1 。如果从一个标为 1 的位置可以通过上下左右走到另一个标为 1
的位置,则称两个位置连通。与某一个标为 1 的位置连通的所有位置(包括自己)组成一个连通分块。请问矩阵中最大的连通分块有多大?

110010000011111110101001001001101010111011011011101001111110
010000000001010001101100000010010110001111100010101100011110
001011101000100011111111111010000010010101010111001000010100
101100001101011101101011011001000110111111010000000110110000
010101100100010000111000100111100110001110111101010011001011
010011011010011110111101111001001001010111110001101000100011
101001011000110100001101011000000110110110100100110111101011
101111000000101000111001100010110000100110001001000101011001
001110111010001011110000001111100001010101001110011010101110
001010101000110001011111001010111111100110000011011111101010
011111100011001110100101001011110011000101011000100111001011
011010001101011110011011111010111110010100101000110111010110
001110000111100100101110001011101010001100010111110111011011
111100001000001100010110101100111001001111100100110000001101
001110010000000111011110000011000010101000111000000110101101
100100011101011111001101001010011111110010111101000010000111
110010100110101100001101111101010011000110101100000110001010
110101101100001110000100010001001010100010110100100001000011
100100000100001101010101001101000101101000000101111110001010
101101011010101000111110110000110100000010011111111100110010
101111000100000100011000010001011111001010010001010110001010
001010001110101010000100010011101001010101101101010111100101
001111110000101100010111111100000100101010000001011101100001
101011110010000010010110000100001010011111100011011000110010
011110010100011101100101111101000001011100001011010001110011
000101000101000010010010110111000010101111001101100110011100
100011100110011111000110011001111100001110110111001001000111
111011000110001000110111011001011110010010010110101000011111
011110011110110110011011001011010000100100101010110000010011
010011110011100101010101111010001001001111101111101110011101
  • 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
  • 29
  • 30
def dfs(grid, i, j, visited):
    # 从位置(i, j)开始,进行DFS遍历,将访问过的位置标记为visited。
    if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]):
        return
    if grid[i][j] == '0' or visited[i][j]:
        return
    visited[i][j] = True
    dfs(grid, i - 1, j, visited)
    dfs(grid, i + 1, j, visited)
    dfs(grid, i, j - 1, visited)
    dfs(grid, i, j + 1, visited)
def largest_connected(grid):
    # 计算矩阵中最大的连通分块的大小。
    # 初始化visited数组
    visited = [[False] * len(grid[0]) for _ in range(len(grid))]
    # 对于每个标为1的位置,进行DFS遍历,并计算连通分块的大小
    max_size = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1' and not visited[i][j]:
                dfs(grid, i, j, visited)
                size = sum([sum(row) for row in visited])
                max_size = max(max_size, size)
                visited = [[False] * len(grid[0]) for _ in range(len(grid))]
    return max_size
a = ['0']*30
for i in range(30):
    a[i] = input()
print(largest_connected(a))  # 答案:148

  • 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
  • 29
  • 30

问题6

问题描述:

给定一天是一周中的哪天,请问 n 天后是一周中的哪天?

输入格式:

输入第一行包含一个整数 w,表示给定的天是一周中的哪天,w 为 1 到 6 分别表示周一到周六,w 为 7 表示周日。第二行包含一个整数 n。

输出格式:

输出一行包含一个整数,表示 n 天后是一周中的哪天,1 到 6 分别表示周一到周六,7 表示周日。

样例输入:
6
10
样例输出:
2
评测用例规模与约定:
  对于所有评测用例,1 <= n <= 1000000。

w = int(input())
n = int(input())
for i in range(n):
    if w + 1 > 7:
        w = 1
    else:
        w += 1
print(w)

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

问题7

数据很小,可以直接暴力过。


问题描述:

小蓝负责一块区域的信号塔安装,整块区域是一个长方形区域,建立坐标轴后,西南角坐标为 (0, 0), 东南角坐标为 (W, 0), 西北角坐标为 (0, H), 东北角坐标为 (W, H)。其中 W, H 都是整数。他在 n个位置设置了信号塔,每个信号塔可以覆盖以自己为圆心,半径为 R 的圆形(包括边缘)。为了对信号覆盖的情况进行检查,小蓝打算在区域内的所有横纵坐标为整数的点进行测试,检查信号状态。其中横坐标范围为 0 到 W,纵坐标范围为0 到 H,总共测试 (W+1) * (H+1) 个点。给定信号塔的位置,请问这 (W+1)*(H+1) 个点中有多少个点被信号覆盖。

输入格式:

输入第一行包含四个整数 W, H, n, R,相邻整数之间使用一个空格分搁。接下来 n 行,每行包含两个整数 x,y,表示一个信号塔的坐标。信号塔可能重合,表示两个信号发射器装在了同一个位置。

输出格式:

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

样例输入:
10 10 2 5
0 0
7 0
样例输出:
57
评测用例规模与约定:
  对于所有评测用例,1 <= W, H <= 100,1 <= n <= 100, 1 <= R <= 100, 0 <= x <= W, 0 <= y <= H。

w, h, n, r = map(int, input().split())
count = 0
a = []
for _ in range(n):
    x, y = map(int, input().split())  # 圆心
    a.append([x, y])
for x1 in range(w+1):
    for y1 in range(h+1):
        for i in range(n):
            x, y = a[i][0], a[i][1]
            d = ((x1-x)**2+(y1-y)**2)**0.5
            if d <= r:
                count += 1
                break
print(count)

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

问题8

时间复杂度为O(nmt),可以暴力过。也可以用二维矩阵的前缀和优化。


问题描述:

小蓝有一个 n * m 大小的矩形水域,小蓝将这个水域划分为 n 行 m 列,行数从 1 到 n 标号,列数从 1 到 m标号。每行和每列的宽度都是单位 1 。现在,这个水域长满了水草,小蓝要清理水草。每次,小蓝可以清理一块矩形的区域,从第 r1行(含)到第 r2 行(含)的第 c1 列(含)到 c2 列(含)。经过一段时间清理后,请问还有多少地方没有被清理过。

输入格式:

输入第一行包含两个整数 n, m,用一个空格分隔。第二行包含一个整数 t ,表示清理的次数。接下来 t 行,每行四个整数 r1, c1, r2, c2,相邻整数之间用一个空格分隔,表示一次清理。请注意输入的顺序。

输出格式:

输出一行包含一个整数,表示没有被清理过的面积。

样例输入1:
2 3
2
1 1 1 3
1 2 2 2
样例输出1:
2
样例输入2:
30 20
2
5 5 10 15
6 7 15 9
样例输出2:
519
评测用例规模与约定
  对于所有评测用例,1 <= r1 <= r2 <= n <= 100, 1 <= c1 <= c2 <= m <= 100, 0 <= t <= 100。

n, m = map(int, input().split())
t = int(input())
# 初始化矩阵,全部置为1
matrix = [[1] * (m+1) for _ in range(n+1)]
# 遍历每次清理的矩形区域,将矩阵中对应的区域置为0
for i in range(t):
   r1, c1, r2, c2 = map(int, input().split())
   for j in range(r1, r2+1):
       for k in range(c1, c2+1):
           matrix[j][k] = 0
# 统计矩阵中值为1的元素个数,即为未被清理过的面积
count = 0
for i in range(1, n+1):
   for j in range(1, m+1):
       if matrix[i][j] == 1:
           count += 1
print(count)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

问题9

bfs或者dfs都可以。


问题描述:

小蓝准备在一个空旷的场地里面滑行,这个场地的高度不一,小蓝用一个 n 行 m 列的矩阵来表示场地,矩阵中的数值表示场地的高度。
  如果小蓝在某个位置,而他上、下、左、右中有一个位置的高度(严格)低于当前的高度,小蓝就可以滑过去,滑动距离为 1 。
  如果小蓝在某个位置,而他上、下、左、右中所有位置的高度都大于等于当前的高度,小蓝的滑行就结束了。小蓝不能滑出矩阵所表示的场地。
  小蓝可以任意选择一个位置开始滑行,请问小蓝最多能滑行多远距离。

输入格式 :

输入第一行包含两个整数 n, m,用一个空格分隔。
接下来 n 行,每行包含 m 个整数,相邻整数之间用一个空格分隔,依次表示每个位置的高度。

输出格式:

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

样例输入:
4 5
1 4 6 3 1
11 8 7 3 1
9 4 5 2 1
1 3 2 2 1
样例输出:
7
样例说明:

滑行的位置一次为 (2, 1), (2, 2), (2, 3), (3, 3), (3, 2), (4, 2), (4, 3)。

评测用例规模与约定
  对于 30% 评测用例,1 <= n <= 20,1 <= m <= 20,0 <= 高度 <= 100。
  对于所有评测用例,1 <= n <= 100,1 <= m <= 100,0 <= 高度 <= 10000。

import queue
dire = [[-1, 0], [1, 0], [0, 1], [0, -1]]
def bfs(x, y, gird):
    q = queue.Queue()
    q.put([x, y, 0])
    s = 0
    while not q.empty():
        t = q.get()
        x1, y1, step = t[0], t[1], t[2]
        s = max(step, s)
        visited[x1][y1] = True
        for i, j in dire:
            dx, dy = x1 + i, y1 + j
            if dx < 0 or dx >= n or dy < 0 or dy >= m or visited[dx][dy]:
                continue
            if gird[dx][dy] < gird[x][y]:
                q.put([dx, dy, step + 1])
    return s
n, m = map(int, input().split())
a = []
for _ in range(n):
    a.append(list(map(int, input().split())))
visited = [[False] * m for _ in range(n)]
max_size = 0
for i in range(n):
    for j in range(m):
        size = bfs(i, j, a)
        max_size = max(max_size, size)
        visited = [[False] * m for _ in range(n)]
print(max_size)
  • 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
  • 29
  • 30

问题10

思路一:很简单的两重循环,第一重遍历每一个点,第二重遍历合法的区间求最小值,时间复杂度为O(nk),肯定是不能全过的。

思路二:经典的单调队列加滑动窗口问题。时间复杂度为O(n),题目是求最小值,所以我们需要保持队列为单调递增的,同时需要队列长度合法。再写一个check函数来保持不越界。代码有注解,如果看了还不太懂的,可以转这个链接,相信肯定豁然开朗。
https://www.bilibili.com/video/BV1H5411j7o6/?spm_id_from=333.880.my_history.page.click&vd_source=3294871d0fd29ddca368a431c4298aba


问题描述:

小蓝有一个序列a[1],a[2],…,a[n]。给定一个正整数k,请问对于每一个1到n之间的序号i.a[i-k],a[i-k+1]…a[i+K]
这2k+1个数中的最小值是多少?当某个下标超过1到n的范围时,数不存在,求最小值时只取存在的那些值。

输入格式:

输入的第一行包含一整数n。 第二行包含n个整数,分别表示 a[1],a[2],…,a[n]。 第三行包含一个整数k

输出格式:

输出一行,包含n个整数,分别表示对于每个字号求得的最小值

样例输入:
5
5 2 7 4 3
1
样例输出:
2 2 2 3 3
评测用例规模与约定
  对于 30% 的评测用例,1 <= n <= 1000,1 <= a[i] <= 1000。
  对于 50% 的评测用例,1 <= n <= 10000,1 <= a[i] <= 10000。
  对于所有评测用例,1 <= n <= 1000000,1 <= a[i] <= 1000000。

def check(i):
    if i <= 0:
        return 0
    if i >= n:
        return n - 1
    return i
n = int(input())
a = list(map(int, input().split()))
k = int(input())
# 初始化双端队列
dq = []  # (队列中存的是下标!)
# 先处理前k个元素,将队列保持单调递增,且保证队列头部是最小元素
for i in range(k):
    # 将当前元素加入队列,保持队列单调递增(如果新加入的数的大小比队尾所对应的数的大小还要小,那么队尾就一直需要出队,否则就直接加)
    while dq and a[dq[-1]] >= a[check(i)]:
        dq.pop()
    dq.append(i)
# print(dq)
for i in range(n):
    # 移除队列头部元素,如果已经超过了i-k的范围(就是滑动窗口长度已近为2*k+1了,这时候需要队头出队)且队列不为空
    if dq and dq[0] < check(i - k):
        dq.pop(0)
    # 将当前元素加入队列,保持队列单调递增(如果新加入的数的大小比队尾所对应的数的大小还要小,那么队尾就一直需要出队,否则就直接加)
    while dq and a[dq[-1]] >= a[check(i + k)]:
        dq.pop()
    dq.append(check(i + k))
    print(a[dq[0]], end=' ')

  • 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
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/知新_RL/article/detail/64267
推荐阅读
相关标签
  

闽ICP备14008679号