第十四届蓝桥杯Python B组省赛复盘

04-13 1370阅读

第十四届蓝桥杯Python B组省赛复盘

文章目录

第十四届蓝桥杯Python B组省赛复盘
- 试题 A: 2023
- - 【问题描述】（5 分）
  - 【思路】
  - 试题 B: 硬币兑换（5 分）
  - - 【问题描述】
    - 【思路】
    - 试题 C: 松散子序列
    - - 【问题描述】
      - 【输入格式】
      - 【输出格式】
      - 【样例输入】
      - 【样例输出】
      - 【评测用例规模与约定】
      - 思路
      - 试题 D: 管道
      - 【问题描述】
        【输入格式】
        【输出格式】
        【样例输入】
        【样例输出】
        【评测用例规模与约定】
        思路
        试题 E: 保险箱
        【问题描述】
        【输入格式】
        【输出格式】
        【样例输入】
        【样例输出】
        【评测用例规模与约定】
        思路
        试题 F: 树上选点
        【问题描述】
        【输入格式】
        【输出格式】
        【样例输入】
        【样例输出】
        【评测用例规模与约定】
        思路
        试题 G: T 字消除
        【问题描述】
        【输入格式】
        【输出格式】
        【样例输入】
        【样例输出】
        【样例说明】
        思路
        试题 H: 独一无二
        【问题描述】
        【输入格式】
        【输出格式】
        【样例输入】
        【样例输出】
        【样例说明】
        【评测用例规模与约定】
        思路
        试题 I: 异或和
        【问题描述】
        【输入格式】
        【输出格式】
        【样例输入】
        【样例输出】
        【评测用例规模与约定】
        思路
        试题 J: 混乱的数组
        【问题描述】
        【输入格式】
        【输出格式】
        【样例输入】
        【样例输出】
        【评测用例规模与约定】
        思路
        总结
        试题 A: 2023
        
        【问题描述】（5 分）
        
        请求出在 12345678 至 98765432 中，有多少个数中完全不包含 2023 。
        
        完全不包含 2023 是指无论将这个数的哪些数位移除都不能得到 2023 。
        
        例如 20322175，33220022 都完全不包含 2023，而 20230415，20193213 则含有 2023 (后者取第 1, 2, 6, 8 个数位) 。
        
        【思路】
        
        正则表达式
        
        ''' 正则表达式 ''' import re def check(s) : if re.match(r'.*2.*0.*2.*3.*', s) : return False else : return True st = 12345678 ed = 98765432 res = 0 while st sum1,sum2,⋅⋅⋅,sumK} 的值达到最大，请你帮他计算这个值最大是多少。=s)打开并位于 l l l的管道，在此时此刻可以覆盖的区间是 [ m a x ( l − ( t − s ) , 1 ) , m i n ( l + ( t − s ) , l e n ) ] [max(l - (t - s), 1), min(l + (t - s), len)] [max(l−(t−s),1),min(l+(t−s),len)].
        下面考虑区间覆盖问题，对于n个区间，可以一个个枚举区间，并对覆盖区间进行标记，然而这样的复杂度是 O ( n l e n ) O(nlen) O(nlen)。怎么优化呢？我们想到对区间进行操作的一个基础算法差分，类似于LeetCode中的区间覆盖原题。
        
        ''' 覆盖问题，二分 ''' from sys import stdin def check(x) : st = [0] * (m + 2) for item in a : if item[1] 1 if check(mid) : r = mid else : l = mid + 1 print(l)
        
        试题 E: 保险箱
        
        时间限制: 10.0s 内存限制: 512.0MB 本题总分：15 分
        
        【问题描述】
        
        小蓝有一个保险箱，保险箱上共有 n 位数字。
        小蓝可以任意调整保险箱上的每个数字，每一次操作可以将其中一位增加
        1 或减少 1 。
        当某位原本为 9 或 0 时可能会向前（左边）进位/退位，当最高位（左边第
        一位）上的数字变化时向前的进位或退位忽略。
        例如：
        00000 的第 5 位减 1 变为 99999 ；
        99999 的第 5 位减 1 变为 99998 ；
        00000 的第 4 位减 1 变为 99990 ；
        97993 的第 4 位加 1 变为 98003 ；
        99909 的第 3 位加 1 变为 00009 。
        保险箱上一开始有一个数字 x，小蓝希望把它变成 y，这样才能打开它，问
        小蓝最少需要操作的次数。
        
        【输入格式】
        
        输入的第一行包含一个整数 n 。
        第二行包含一个 n 位整数 x 。
        第三行包含一个 n 位整数 y 。
        
        【输出格式】
        
        输出一行包含一个整数表示答案。
        
        【样例输入】
        
        5 12349 54321
        
        【样例输出】
        
        11
        
        【评测用例规模与约定】
        
        思路
        
        比赛的时候看到这题秒想用BFS，但本题的数据范围实在太大，即使跑10s超过10长度的数据也跑不出来。这时我们需要挖掘一下题目中的性质：
        
        每一次只能让一位增加、减少1
        每一位只会向左边进位、退位，最高位的进退位忽略
        仔细思考，根据已有性质可以推出：每一位有三种可能：进位、退位、不进不退。而且向高位进位或者退位次数，不大于1，因为进退位的目的只是更接近当前位的目标数字，对于高位的第二次改变的花费比在高位直接进行一次操作花费大。
        由于前面的操作无后效性，可以考虑一下DP。
        状态表示 f [ i , 0 / 1 / 2 ] f[i, 0/1/2] f[i,0/1/2], 假设原字符串和目标字符串为 s , e s, e s,e：
        
        集合：分别表示1~i-1位已经处理到相应位置，第i位进位、退位、不进不退的最终拨转到目标数花费集合
        属性：min
        状态计算：
        
        第i位进位： f [ i , 0 ] = ( e i + 10 − s i ) + m i n ( f [ i + 1 , 0 ] − 1 , f [ i + 1 , 1 ] + 1 , f [ i + 1 , 2 ] ) f[i, 0] = (e_i + 10 - s_i) + min(f[i + 1, 0] - 1, f[i + 1, 1] + 1, f[i + 1, 2]) f[i,0]=(ei+10−si)+min(f[i+1,0]−1,f[i+1,1]+1,f[i+1,2])
        第i位退位： f [ i , 1 ] = ( s i + 10 − e i ) + m i n ( f [ i + 1 , 0 ] + 1 , f [ i + 1 , 1 ] − 1 , f [ i + 1 , 2 ] ) f[i, 1] = (s_i + 10 - e_i)+ min(f[i + 1, 0] + 1, f[i + 1, 1] - 1, f[i + 1, 2]) f[i,1]=(si+10−ei)+min(f[i+1,0]+1,f[i+1,1]−1,f[i+1,2])
        第i位不进不退： f [ i , 2 ] = ∣ s i − e i ∣ + m i n ( f [ i + 1 , 0 ] + 1 , f [ i + 1 , 1 ] + 1 , f [ i + 1 , 2 ] ) f[i, 2] = |s_i - e_i| + min(f[i + 1, 0] + 1, f[i + 1, 1] + 1, f[i + 1, 2]) f[i,2]=∣si−ei∣+min(f[i+1,0]+1,f[i+1,1]+1,f[i+1,2])
        n = int(input()) f = [[0, 0, 0] for _ in range(n + 5)] st = input() ed = input() for i in range(n, 0, -1) : if i == n : f[i][0] = int(ed[i - 1]) + 10 - int(st[i - 1]) f[i][1] = int(st[i - 1]) + 10 - int(ed[i - 1]) f[i][2] = abs(int(st[i - 1]) - int(ed[i - 1])) else : f[i][0] = int(ed[i - 1]) + 10 - int(st[i - 1]) + min(f[i + 1][0] - 1, f[i + 1][1] + 1, f[i + 1][2]) f[i][1] = int(st[i - 1]) + 10 - int(ed[i - 1]) + min(f[i + 1][0] + 1, f[i + 1][1] - 1, f[i + 1][2]) f[i][2] = abs(int(st[i - 1]) - int(ed[i - 1])) + min(f[i + 1][0] + 1, f[i + 1][1] + 1, f[i + 1][2]) print(min(f[1][0], f[1][1], f[1][2]))
        
        思路感觉没毛病，但在dotcpp上只能过一个点，家人们谁懂啊
        
        试题 F: 树上选点
        
        时间限制: 10.0s 内存限制: 512.0MB 本题总分：15 分
        
        【问题描述】
        
        给定一棵树，树根为 1，每个点的点权为 V i V_i Vi 。
        你需要找出若干个点 P i P_i Pi，使得：
        
        每两个点 P x P y P_x P_y PxPy 互不相邻；
        每两个点 P x P y P_x P_y PxPy 与树根的距离互不相同；
        找出的点的点权之和尽可能大。
        请输出找到的这些点的点权和的最大值。
        【输入格式】
        
        输入的第一行包含一个整数 n 。
        第二行包含 n − 1 个整数 F i F_i Fi ，相邻整数之间使用一个空格分隔，分别表示
        第 2 至 n 个结点的父结点编号。
        第三行包含 n 个整数 V i V_i Vi，相邻整数之间使用一个空格分隔，分别表示每个
        结点的点权。
        
        【输出格式】
        
        输出一行包含一个整数表示答案。
        
        【样例输入】
        
        5 1 2 3 2 2 1 9 3 5
        
        【样例输出】
        
        11
        
        【评测用例规模与约定】
        
        思路
        
        题目大意是，选的节点不具有父子关系，且不可以深度相同，最终使选择的点价值最大。
        明显的状态机树形DP。
        对于一个确定的节点 i i i，要么取要么不取。
        分情况讨论：
        
        取：则子节点一定不能取
        不取：则可以取一个子节点，也可以不取
        靠写不出来了，感觉又BFS又DFS好烦，过了过了
        试题 G: T 字消除
        
        时间限制: 10.0s 内存限制: 512.0MB 本题总分：20 分
        
        【问题描述】
        
        小蓝正在玩一款游戏，游戏中有一个 n × n 大小的 01 矩阵 A i , j A_{i, j} Ai,j 。
        小蓝每次需要选择一个 T 字型的区域，且这个区域内至少要有一个 1 。选
        中后，这个区域内所有的元素都会变成 0 。
        给定游戏目前的矩阵，小蓝想知道他最多可以进行多少次上述操作。
        T 字型区域是指形如 ( x − 1 , y ) ( x , y ) ( x + 1 , y ) ( x , y + 1 ) (x − 1, y) (x, y) (x + 1, y) (x, y + 1) (x−1,y)(x,y)(x+1,y)(x,y+1) 的四个点所形成的区
        域。其旋转 90, 180, 270 度的形式同样也视作 T 字形区域。
        
        【输入格式】
        
        输入包含多组数据。
        输入的第一行包含一个整数 D 表示数据组数。
        对于每组数据，第一行包含一个整数 n 。
        接下来 n 行每行包含 n 个 0 或 1，表示矩阵 A i , j A_{i, j} Ai,j 的每个位置的值。
        
        【输出格式】
        
        输出 D 行，每行包含一个整数表示小蓝最多可以对当前询问中的矩阵操作
        的次数。
        
        【样例输入】
        
        1 3 001 011 111
        
        【样例输出】
        
        5
        
        【样例说明】
        
        我们用 X 表示某次操作选中的 T 字形，以下给出一种可行方案：
        
        【评测用例规模与约定】
        
        思路
        
        麻了，题目看懂了想dfs做但无从下手，感觉是个贪心的题，去你的。
        
        试题 H: 独一无二
        
        时间限制: 30.0s 内存限制: 512.0MB 本题总分：20 分
        
        【问题描述】
        
        有一个包含 n 个点，m 条边的无向图，第 i 条边的边权为 c i c_i ci，没有重边和
        自环。设 s i s_i si 表示从结点 1 出发到达结点 i 的最短路的不同路径数 ( i ∈ [1, n] )，
        显然可以通过删除若干条边使得 s i = 1 s_i = 1 si=1，也就是有且仅有一条从 1 到 i 的最短
        路，且保持最短路的路径长度不变，对于每个 i ，求出删除边数的最小值。
        
        【输入格式】
        
        输入的第一行包含两个正整数 n, m。
        接下来 m 行，每行包含三个正整数 u i , v i , c i u_i, v_i, c_i ui,vi,ci 表示第 i 条边连接的两个点的
        编号和边权。
        
        【输出格式】
        
        输出 n 行，第 i 行包含一个正整数表示对于结点 i ，删除边数的最小值，
        如果 1 和 i 不连通，输出 −1 。
        
        【样例输入】
        
        4 4 1 2 1 1 3 2 2 4 2 3 4 1
        
        【样例输出】
        
        0
        0
        0
        1
        
        【样例说明】
        
        在给定的图中，只有 s4 一开始为 2，因为有两条最短路：1 → 2 → 4, 1 →
        3 → 4，任意删掉一条边后，就可以只剩一条最短路。
        
        【评测用例规模与约定】
        
        思路
        
        听说是什么最短路+dp转移，听都没听过，以后有缘再见吧！
        
        试题 I: 异或和
        
        时间限制: 15.0s 内存限制: 512.0MB 本题总分：25 分
        
        【问题描述】
        
        给一棵含有 n 个结点的有根树，根结点为 1 ，编号为 i 的点有点权 a i a_i ai （ i ∈ [ 1 , n ] ）（i ∈ [1, n]）（i∈[1,n]）。现在有两种操作，格式如下：
        • 1 x y 该操作表示将点 x 的点权改为 y 。
        • 2 x 该操作表示查询以结点 x 为根的子树内的所有点的点权异或和。
        现有长度为 m 的操作序列，请对于每个第二类操作给出正确的结果。
        
        【输入格式】
        
        输入的第一行包含两个正整数 n, m ，用一个空格分隔。
        第二行包含 n 个整数 a 1 , a 2 , . . . , a n a_1, a_2, ..., a_n a1,a2,...,an ，相邻整数之间使用一个空格分隔。
        接下来 n − 1 行，每行包含两个正整数 u i , v i u_i, v_i ui,vi ，表示结点 u i u_i ui 和 v i v_i vi 之间有一条
        边。
        接下来 m 行，每行包含一个操作。
        
        【输出格式】
        
        输出若干行，每行对应一个查询操作的答案。
        
        【样例输入】
        
        4 4 1 2 3 4 1 2 1 3 2 4 2 1 1 1 0 2 1 2 2
        
        【样例输出】
        
        4
        5
        6
        
        【评测用例规模与约定】
        
        思路
        
        一个dfs序模板
        
        首先要知道异或和的一些性质 :
        
        0异或任何数都是这个数本身
        任何数异或本身等于0
        所以异或中加减操作都集中在异或运算上
        
        具体来说，先处理出树的dfs序列，然后初始化树状数组。dfs序列易于处理一个以u为根的子树，在序列中表示一个区间。用树状数组处理区间和单点操作。
        
        import sys sys.setrecursionlimit(60000) n, m = map(int, input().split()) id = [0] # 表示dfs序 inn = [0] * (n + 1) #以i节点为根的子树在dfs序开始位置 out = [0] * (n + 1) #以i节点为根的子树在dfs序末尾位置 h = [-1] * (2 * n + 7) e = [0] * (2 * n + 7) ne = [-1] * (2 * n + 7) idx = 0 tr = [0] * (n + 7) # 树状数组，存储(x - lowbit(x), x]区间内的异或和 def lowbit(x) : return x & -x def sum(x, c) : # 修改操作 i = x while i A j A_i > A_j Ai>Aj 。
        如果存在多个这样的数组，请输出字典序最小的那个。
        
        【输入格式】
        
        输入一行包含一个整数表示 x 。
        
        【输出格式】
        
        输出两行。
        第一行包含一个整数 n ，表示所求出的数组长度。
        第二行包含 n 个整数 A i A_i Ai，相邻整数之间使用一个空格分隔，依次表示数组
        中的每个数。
        
        【样例输入】
        
        3
        
        【样例输出】
        
        3
        3 2 1
        
        【评测用例规模与约定】
        
        思路
        
        对于这题，我决定直接打表得分,蚊子肉也是肉啊
        
        x = int(input()) if x == 1: print(2) print(2, 1) if x == 2: print(3) print(2, 1, 1) if x == 3: print(3) print(3, 2, 1) if x == 4: print(4) print(2, 2, 1, 1) if x == 5: print(4) print(3, 2, 1, 1) if x == 6: print(4) print(4, 3, 2, 1) if x == 7: print(5) print(3, 2, 2, 2, 1) if x == 8: print(5) print(3, 3, 2, 1, 1) if x == 9: print(5) print(4, 3, 2, 1, 1) if x == 10: print(5) print(5, 4, 3, 2, 1)
        
        总结
        
        麻了，做这B样也能省一，还挺开心。感觉还差挺多的，很多读题失误，很多题没好好体会导致无谓失分，很可惜。继续加油努力吧，冲刺国赛。