第十三届蓝桥杯Python B组国赛题解

第十三届蓝桥杯Python B组国赛题解

  • 试题A:斐波那契与7
  • 试题 B: 小蓝做实验
  • 试题 C: 取模
  • 试题 D: 内存空间
  • 试题 E: 近似 GCD
  • 试题 F: 交通信号
  • 试题 G: 点亮
  • 试题 H: 打折
  • 试题 I: owo
  • 试题 J: 替换字符
  • 比赛心得
  • 写在开头:题解全部为个人思路,仅供参考

    试题地址https://www.aliyundrive.com/s/QBKYnUpeh3v
    提取码: d59a

    题解还没有全部写完,持续更新

    试题A:斐波那契与7


    题意分析

  • 题目中问有多少项个位是7,而能让个位发生变化的也只有个位相加减,所以只考虑个位就行,不用在考虑其他位,即结果只保留个位就行

    对于这种题,肯定有规律,我们只需要找到找个规律,题目差不多就解决了

  • 
    f1 = 0
    f2 = 1
    f3 = 1
    c = 0   # 统计出现的次数
    for i in range(60):
        print(f3, end=' ')  # 斐波那契数列中的数字
        f3 = (f1+f2)%10
        if f3 ==7:
            c+=1
        f1 = f2
        f2 = f3
    # 1 1 2 3 5 8 3 1 4 5 9 4 3 7 0 7 7 4 1 5 6 1 7 8 5 3 8 1 9 0 9 9 8 7 5 2 7 9 6 5 1 6 7 3 0 3 3 6 9 5 4 9 3 2 5 7 2 9 1 0
    # 经过验证,60个一循环 每个循环里面有8个个位为7的数字
    print()
    print(c)
    print(202202011200//60)  # 一共3370033520次循环
    print((202202011200//60)*8) # 26960268160
    

    答案:26960268160

    试题 B: 小蓝做实验

    利用埃氏筛法解题,埃氏筛法的效率非常高 关于埃氏筛法看这个

    答案:342693

    # 运用埃氏筛法进行解题
    # 因为只有少部分的数据大于10**8,将数据分为两部份,小于10**8的,大于10**8
    f = open(r'primes.txt','r',encoding='utf-8')  
    txt = f.read().split()         # 讲文件内的东西转化为列表 
    arr1 = [int(i) for i in txt if len(i)<=8]  # 根据长度分,然后在转换为整型
    arr2 = [int(i) for i in txt if len(i)>8]   # 长度为170,所以单独判断花费的时间并不长
    
    # 先默认所有的都为质数(这部分可以看我质数筛的文章)
    # 埃氏筛选法效率非常高2分42秒能够找出10*8以内的质数
    nums = [True for i in range(10**8+1)] 
    for i in tqdm(range(3,10**8+1)):
        if nums[i]:
            for j in range(i+i,10**8,i):
                nums[j] = False
    c=0 # 记录次数
    for i in arr1:  # 根据列表里面的值判断是否为质数
        if nums[i]:
            c+=1
    for i in arr2:   # 对大于10**8的数进行判断
        for j in range(2,int(i**0.5)+1):  
                if i%j == 0:
                    break
        else:
            c+=1
    print(c)
    

    试题 C: 取模

    # 暴力
    t = int(input())
    nums = []
    for i in range(t):
        n,m = input().split()
        n = int(n)
        m = int(m)
        f = False
        for j in range(1,m+1):
            if f:
                break
            for k in range(j+1,m+1):
                if n%j==n%k:
                    f = True
                    nums.append('Yes')
                    break
            
        else:
            nums.append('No')
    for i in nums:
        print(i)
    

    试题 D: 内存空间




    思路

  • 观察题意我们可以根据每句的前几个字符进行分类,详细可以分为5类,我们对不同的类,进行不同的处理,具体的处理方法见代码
  • 占用空间的大小先用B为单位,最后再根据转换的规则转换成题目要求的形式
  • t = int(input())
    zong = 0 # 总大小,单位B
    for i in range(t):
        s_lst = input().split()
        if s_lst[0] == 'int':     # 根据不同的输入情况进行分类
            st1 = s_lst[1].split(',')
            zong+=len(st1)*4  
        elif s_lst[0] == 'long':
            st1 = s_lst[1].split(',')
            zong+=len(st1)*8 
        elif  s_lst[0] == 'String':
            st1 = s_lst[1].split(',')
            num = 0
            for item in st1:
                num+=len(item.split('=')[1])-2
            zong+=num-1
        elif s_lst[0] == 'int[]':
            num = 0
            for it in range(1,len(s_lst)):
                if 'long' in s_lst[it] and ';' not in s_lst[it]:
                    num += int(s_lst[it][4:-1])
                elif 'long' in s_lst[it] and ';' in s_lst[it]:
                    num += int(s_lst[it][4:-2])
            zong+=num*4
        elif  s_lst[0] == 'long[]':
            num = 0
            for it in range(1,len(s_lst)):
                if 'long' in s_lst[it] and ';' not in s_lst[it]:
                    num += int(s_lst[it].split(',')[0][5:-1])
                elif 'long' in s_lst[it] and ';' in s_lst[it]:
                    num += int(s_lst[it][5:-2])
                    
            zong+=num*8
    
    z = [0,0,0,0]   # B,KB,MB,GB 前的数值
    for i in range(4):
        z[i]=zong%1024
        zong = zong//1024
        if zong <=0:
            break
    
    result = ''
    result_st = ['GB','MB','KB','B']
    for i in range(1,len(z)+1):
        if z[4-i] != 0:
            result+=f'{z[4-i]}{result_st[i-1]}'
    print(result)
    
    

    试题 E: 近似 GCD



    解题思路

  • 题目的意思就是求,数组A中的长度大于1的子数组,有多少个满足近似GCD的值为g
  • 本题主要采用的方法,双指针法
  • 算法主要分为两部分
  • 判断子数组是否满足条件,
  • 指针的移动几种情况
  • n,g = map(int,input().split())
    nums = [int(i) for i in input().split()]
    import math
    l = 0
    r = 2
    c = 0
    while r<=len(nums):
        arr = nums[l:r]
        flag = False
        for i in range(len(arr)):
            s = g
            for j in range(len(arr)):
                if i == j:  # 跳过本身,也就是相当于将本身修改为 g
                    continue
                else:
                    s = math.gcd(s,arr[j])   # 利用math库中的gcd方法求解质数
            if s == g:
                c += 1
                flag = True
                break
        
        if flag: 
            r+=1
        else:
            if r-l>3:  # 长度大于3  
                r-=1
                l+=1
            elif r-l==3:  # 长度等于3 
                l+=1
            else:         # 长度等于2
                r+=1
                l+=1
    

    试题 F: 交通信号


    试题 G: 点亮


    试题 H: 打折



    解题思路

  • 这道题使用暴力解题还是比较容易想出来的,可能会超时,但是能的一部分分是一部分
    大概就是,计算每一天需要花费的金额,选出花钱最少的
  • 不过暴力也是可以进行简单的优化,减少循环的次数,降低内存的占用。这样都可以加快程序运行的效率
  • n,m = map(int,input().split())
    arr = []
    max_day = 0
    for i in range(m):
        s, t, p, c = map(int,input().split()) # 分别表示商店优惠的起始和结束时间、折扣率以及商店内的商品总数
        if t>max_day:
            max_day=t
        lst = []
        for j in range(c):
            a,b = map(int,input().split()) # 第 j 个商品的类型和价格
            lst.append((a,b))
        arr.append([s, t, p, c,lst])
    result = []
    for i in range(1,max_day+1):  # 循环的天数
        dic = {}
        for item in arr:
            if item[0] <= i and i <= item[1]:
                for index,value in item[4]:
                    s = int(value * item[2] / 100)
                    if index in dic:
                        if dic[index] > s:
                            dic[index] = s
                    else:
                        dic[index] = s
            else:
                for index, value in item[4]:
                    if index in dic:
                        if dic[index] > value:
                            dic[index] = value
                    else:
                        dic[index] = value
        result.append(sum(dic.values()))
    print(min(result))
    

    试题 I: owo


    我看有直接用全排列做题的,是一种解题的方式,在比赛中能写上就写上,但是我个人感觉时间复杂度太高了,等有合适的方法在写题解吧

    试题 J: 替换字符


    我也不知道为什么这道题放最后,我个人感觉比上面的题简单
    主要采用了切片和replace()函数
    思路
    将字符串分割成三部分,左中右,中间的字符串为待替换掉的部分,修改以后再将字符串拼接起来,

    s = input()
    m = int(input())
    for i in range(m):
        nums = input().split()
        l = int(nums[0])
        r = int(nums[1])
        x = nums[2]
        y = nums[3]
    
        s1 = s[0:l-1]
        s2 = s[l-1:r]
        s3 = s[r:]
        s2 = s2.replace(x,y)
        s = s1+s2+s3
    print(s)
    

    注意 不能直接 s = s[l-1:r].replace(x, y) 这样修改,因为你这样修改后的s就是s[l-1:r]的字符串,其余的部分都被舍去了

    比赛心得

  • 能用内置函数解决绝不自己再重复造轮子,因为内置函数效率一般都很高
  • 蓝桥杯是OI赛制,也就是提交答案之后赛后评判,根据通过的样例数量给分。所以对于一些难度比较高的题目,想不到合适的解决方法就用暴力,能跑对几个案例就多捞一点分
  • 好像今年这一届对python的时间限制放宽了改为了10秒钟,所以用暴力解题也是一个好的选择
  • 在比赛中,可能会因为太紧张,而出现读不懂题的情况,这时候小声读题能够让你的注意力更加的集中
  • 合理安排时间不要陷人做题的牢笼,不要因为一道题而放弃所有,如果在一道题上花费了1个小时还没有解决,先暂时放弃,去做其他的题目,后面的题目可能对于你来说更加简单
  • 关于试题的类型一般每年都差不多,备考阶段,根据自己的情况,由简入难,多思考,多刷题
  • 来源:小鱼干儿♛

    物联沃分享整理
    物联沃-IOTWORD物联网 » 第十三届蓝桥杯Python B组国赛题解

    发表评论