代码收藏家技术教程 2022-07-24

第十三届蓝桥杯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]的字符串，其余的部分都被舍去了