蓝桥杯-2023年第十四届省赛真题Python（A-D）_2023蓝桥杯pythona组

A：2023-填空

【问题描述】

        请求出在 12345678 至 98765432 中，有多少个数中完全不包含 2023 。

        完全不包含 2023 是指无论将这个数的哪些数位移除都不能得到 2023 。

        例如 20322175，33220022 都完全不包含 2023，而 20230415，20193213 则 含有 2023 (后者取第 1, 2, 6, 8 个数位) 。

【解析及代码】

        1、从第一个开始找，找到一个就从这里开始找下一个，直到找完就是含有，不然没有

        2、def+暴力

def is_In(s):
    firstIndex=s.find('2')
    if firstIndex==-1: #没找到
        return False
 
    secondIndex = s.find('0',firstIndex)
    if secondIndex == -1:  # 没找到
        return False
 
    thirdIndex = s.find('2',secondIndex)
    if thirdIndex == -1:  # 没找到
        return False
 
    fourthIndex = s.find('3',thirdIndex)
    if fourthIndex == -1:  # 没找到
        return False
 
    return True
 
cnt=0
for i in range(12345678,98765433):
    s=str(i)
    if is_In(s)==False:
        cnt+=1
 
print(cnt)

B：硬币兑换-填空  

【问题描述】

        小蓝手中有 2023 种不同面值的硬币，这些硬币全部是新版硬币，其中第 i (1 ≤ i ≤ 2023) 种硬币的面值为 i ，数量也为 i 个。硬币兑换机可以进行硬币兑换，兑换规则为：交给硬币兑换机两个新版硬币 coin1 和 coin2 ，硬币兑换机会 兑换成一个面值为 coin1 + coin2 的旧版硬币。

        小蓝可以用自己已有的硬币进行任意次数兑换，假设最终小蓝手中有 K 种不同面值的硬币（只看面值，不看新旧）并且第 i (1 ≤ i ≤ K) 种硬币的个数为。小蓝想要使得max{} 
 的值达到最大，请你帮他计算 这个值最大是多少。

        注意硬币兑换机只接受新版硬币进行兑换，并且兑换出的硬币全部是旧版硬币。

【解析及代码】

        意思就是两张小面值（相同也可以）换一张大面值，然后同面值的就数，要凑出最多相同的面值。

        暴力，把能兑出的面值（2-4046）都按最大能兑换出多少，然后取同面值的数量的最大值

#两个重复的面值也可以换一个新面值
#面值和的范围是2-4046
#用列表记录每个面值的最大数量,1-2023是原本有的，在原本有的基础上加
li=[i for i in range(2024)]+[0 for i in range(2024,4047)]
for i in range(1,2024):
    for j in range(i,2024):#避免重复计算保证j比i大
        if i==j:
            li[i+j]+=i//2 #相同的话数量折半
        else:
            li[i+j]+=i #不同的话按小的就是最多能凑出来的
print(max(li))

C：松散子序列

【问题描述】

         给定一个仅含小写字母的字符串 s ，假设 s 的一个子序列 t 的第 i 个字符 对应了原字符串中的第 pi个字符。我们定义 s 的一个松散子序列为：对于 i > 1 总是有 pi−pi−1≥2。设一个子序列的价值为其包含的每个字符的价值之和 (a ∼ z 分别为 1 ∼ 26) 。

        求 s 的松散子序列中的最大价值。

【输入格式】

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

【输出格式】

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

【样例输入】azaazaz
【样例输出】78

【提示】
对于 20% 的评测用例，|s| ≤ 10 ； 

对于 40% 的评测用例，|s| ≤ 300 ；

对于 70% 的评测用例，|s| ≤ 5000 ； 

对于所有评测用例，1 ≤ |s| ≤ 106，字符串中仅包含小写字母。

【解析及代码】

        意思就是要在原有的s里面跳着找子序列，条件是pi−pi−1≥2，就是起码隔一个，找出来让他价值最大。

        dp问题，a[i]为初始的价值，如若子序列包含至到a[i],则该节点最大a[i]=max(a[i-2],a[i-3])+a[i],最后就求max(a[-1],a[-2])

#松散子字符串，考的是动态规划dp问题
#ord(a)=97
s=input()
#转换价值存dp,前面加【0,0,0】不用另外考虑边界
dp=[0,0,0]+[ord(i)-96 for i in s]
for i in range(3,len(dp)):
    dp[i]+=max(dp[i-2],dp[i-3])
 
print(max(dp[-1],dp[-2]))

D：管道 

【问题描述】

        有一根长度为 len 的横向的管道，该管道按照单位长度分为 len 段，每一段的中央有一个可开关的阀门和一个检测水流的传感器。

        一开始管道是空的，位于 Li的阀门会在 Si时刻打开，并不断让水流入管道。

        对于位于 Li的阀门，它流入的水在 Ti(Ti≥Si)时刻会使得从第 Li−(Ti−Si)段到第 Li+(Ti−Si)
段的传感器检测到水流。

        求管道中每一段中间的传感器都检测到有水流的最早时间。

【输入格式】

        输入的第一行包含两个整数 n, len，用一个空格分隔，分别表示会打开的阀门数和管道长度。

        接下来 n 行每行包含两个整数 Li,Si用一个空格分隔，表示位于第 Li段管道中央的阀门会在 Si
时刻打开。

【输出格式】

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

【样例输入】

3 10
1 1
6 5
10 2

【样例输出】

5

【评测用例规模与约定】

【解析及代码】

        阀门是开水的，水管是横向的，随着时间越长水就蔓延的越多，求最早时间（明显循环出来）（可以用二分法搜索，因为给了限制范围怎么样都不会超过10^9），那就check时间，然后判断有水的区间长度是否已蔓延比n大就行。

n,lens=map(int,input().split())
#接下来有n行数据，代表开阀管道和开阀时刻
#将其存入列表,以元组的形式
li=[]
for i in range(n):
    u,v=map(int,input().split())
    li.append((u,v))
 
#函数，输入时刻，判断是否覆盖全管
def check(time):
    res=[]
    for l,s in li:
        last=time-s #就是开闸持续的时间
        if last>=0: #开了的闸，就加进去res，加的是水蔓延的区间段，后期排序合并判断
            res.append([l-last,l+last])
    res.sort()
    ans=res[0][1] #取的是最小的尾巴，看看和后面能不能接上
    for i in range(1,len(res)):
        if res[i][0]-ans<=1:#相差1以内能接上,更新尾巴是最大的
            ans=max(ans,res[i][1])
        else: #接不上，跳出循环肯定没覆盖完
            break
        #都接上了也要判断长度够不够
    return ans>=lens
 
#二分法查时刻
left=0
right=10**9
while left<right:
    mid=(left+right)//2
    if check(mid): #时间符合要求，那就更新右边界，找最小
        right=mid
    else: #不符合，更新左边界且不包含，找更大的
        left=mid+1
print(left)