第十四届蓝桥杯大赛软件赛省赛pythonB(含代码)

A.2023

���力即可

import bisectimport sysimport copyfrom collections import deque, defaultdictimport heapqfrom itertools import accumulate, permutations, combinationsimport mathinput = lambda: sys.stdin.readline().rstrip("\r\n")printf = lambda d: sys.stdout.write(str(d) + "\n")# INF = 0x3f3f3f3f3f3f# sys.setrecursionlimit(100000)def read():    line = sys.stdin.readline().strip()    while not line:        line = sys.stdin.readline().strip()    return map(int, line.split())def I():    return int(input())a = 12345678b = 98765432cnt_all = 0ans = 0for num in range(a, b + 1):    cnt_all += 1    tmp = [int(i) for i in str(num)]    flag_2_0 = False    flag_0 = False    flag_2_1 = False    flag_3 = False    for i in range(len(tmp)):        if flag_2_0 == False and tmp[i] == 2:            flag_2_0 = True        if flag_2_0 == True and flag_0 == False and tmp[i] == 0:            flag_0 = True        if flag_2_0 == True and flag_0 == True and flag_2_1 == False and tmp[i] == 2:            flag_2_1 = True        if flag_2_0 == True and flag_0 == True and flag_2_1 == True and flag_3 == False and tmp[i] == 3:            flag_3 = True            ans += 1            breakprint(cnt_all - ans)# 85959030

B.硬币兑换

注意，只有新币可以兑换，最后结果不论硬币新旧。

故应当将1 + 2022， 2 + 2021， … ，1011 + 1012。

a = [i for i in range(2024)]a = a + [0] * 2024left = 1right = 2022while left  
C.松散子序列
  
import sysinput = lambda: sys.stdin.readline().rstrip("\r\n")printf = lambda d: sys.stdout.write(str(d) + "\n")def read():    line = sys.stdin.readline().strip()    while not line:        line = sys.stdin.readline().strip()    return map(int, line.split())def I():    return int(input())s = input()n = len(s)f = [0] * nif s == '':    print(0)elif n == 1:    print(ord(s[0]) - ord('a') + 1)else:    f[0] = ord(s[0]) - ord('a') + 1    f[1] = max(f[0], ord(s[1]) - ord('a') + 1)    for i in range(2, n):        f[i] = max(f[i - 1], f[i - 2] + ord(s[i]) - ord('a') + 1)    print(max(f))
 
D.管道
 
直接遍历每一个阀门，定义数组                                    v                         i                                   s                            i                                       vis_i                  visi​ 为第                                    i                              i                  i 个阀门最早感应到水流的时间。
 
import bisectimport sysimport copyfrom collections import deque, defaultdictimport heapqfrom itertools import accumulate, permutations, combinationsimport mathinput = lambda: sys.stdin.readline().rstrip("\r\n")printf = lambda d: sys.stdout.write(str(d) + "\n")INF = int(1e12)# sys.setrecursionlimit(100000)def read():    line = sys.stdin.readline().strip()    while not line:        line = sys.stdin.readline().strip()    return map(int, line.split())def I():    return int(input())n, len = read()a = []for _ in range(n):    l, s = read()    a.append([l, s])vis = [INF] * (len + 1)for i in range(n):    l, s = a[i]    vis[l] = min(vis[l], s)for i in range(n):    l, s = a[i]    t = s + 1    left = l - 1    right = l + 1    while left >= 1 and t  1:            ans += (tmp_y + 10 - tmp_x)            prev = 1        else:            ans += tmp_x - tmp_y            prev = 0    elif tmp_x == tmp_y:        prev = 0    else:        if (tmp_y - tmp_x) - (tmp_x + 10 - tmp_y) > 1:            ans += (tmp_x + 10 - tmp_y)            prev = -1        else:            ans += tmp_y - tmp_x            prev = 0print(ans)
 
F.树上选点
 
暴力枚举第一个点，再找第二个点。
 
import bisectimport sysimport copyfrom collections import deque, defaultdictimport heapqfrom itertools import accumulate, permutations, combinationsimport mathinput = lambda: sys.stdin.readline().rstrip("\r\n")printf = lambda d: sys.stdout.write(str(d) + "\n")# INF = 0x3f3f3f3f3f3f# sys.setrecursionlimit(100000)def read():    line = sys.stdin.readline().strip()    while not line:        line = sys.stdin.readline().strip()    return map(int, line.split())def I():    return int(input())def dfs_deep(u, depth):    deep[u] = depth    for v in g[u]:        dfs_deep(v, depth + 1)def dfs(u, fa, x):    if fa == x:        vis[u] = True    for v in g[u]:        if v == x:            vis[u] = True        dfs(v, u, x)n = I()g = [[] for _ in range(n + 1)]f = list(read())for i in range(n - 1):    g[f[i]].append(i + 2)value = list(read())value = [0] + valuedeep = [0] * (n + 1)dfs_deep(1, 0)ans = 0for x in range(1, n + 1):    vis = [False] * (n + 1)    vis[0] = True    for i in range(1, n + 1):        if deep[i] == deep[x]:            vis[i] = True    dfs(1, 0, x)    tmp = []    maxm1 = 0    for i in range(1, n + 1):        if not vis[i] and i != x:            if value[i] > maxm1:                maxm1 = value[i]    ans = max(ans, value[x] + maxm1)print(ans)
 
G.T字消除
 
没做。
 
H.独一无二
 
开个cnt数组，每次dis[u]+w == dis[v]的时候+1
 
import bisectimport sysimport copyfrom collections import deque, defaultdictimport heapqfrom itertools import accumulate, permutations, combinationsimport mathinput = lambda: sys.stdin.readline().rstrip("\r\n")printf = lambda d: sys.stdout.write(str(d) + "\n")INF = 0x3f3f3f3f3f3f# sys.setrecursionlimit(100000)def read():    line = sys.stdin.readline().strip()    while not line:        line = sys.stdin.readline().strip()    return map(int, line.split())def I():    return int(input())class Edge:    v = 0    w = 0    ne = -1def add(a, b, c):    global idx    e[idx].v = b    e[idx].w = c    e[idx].ne = h[a]    h[a] = idx    idx += 1def dijkstra(s):    vis = [False] * (n + 1)    dis = [INF] * (n + 1)    cnt = [0] * (n + 1)    dis[0] = dis[s] = 0    vis[0] = True    q = []    heapq.heappush(q, [0, s])    while q:        _, u = heapq.heappop(q)        if vis[u]:            continue        vis[u] = True        i = h[u]        while i != -1:            v = e[i].v            w = e[i].w            i = e[i].ne            if dis[u] + w  
I.异或和
 
a维护以x为根的子树异或和, prev维护每个结点的点权。
每次change只需要向上更改贡献即可。
正解应该是 dfs序+树状数组/线段树 维护
 
import bisectimport sysimport copyfrom collections import deque, defaultdictimport heapqfrom itertools import accumulate, permutations, combinationsimport mathinput = lambda: sys.stdin.readline().rstrip("\r\n")printf = lambda d: sys.stdout.write(str(d) + "\n")# INF = 0x3f3f3f3f3f3f# sys.setrecursionlimit(100000)def read():    line = sys.stdin.readline().strip()    while not line:        line = sys.stdin.readline().strip()    return map(int, line.split())def I():    return int(input())def dfs(u):    for v in g[u]:        a[u] ^= dfs(v)    return a[u]def change(u, x, y):    if u == x:        a[x] = a[x] ^ prev[x] ^ y        # 注意要把点权也修改了，比赛的时候忘记了。。。。        prev[x] = y        return prev[x] ^ y    for v in g[u]:        a[u] ^= change(v, x, y)    return 0n, m = read()a = list(read())a = [0] + aprev = copy.deepcopy(a)g = [[] for _ in range(n + 1)]for i in range(n - 1):    u, v = read()    g[u].append(v)dfs(1)for _ in range(m):    op = list(read())    if op[0] == 1:        x, y = op[1], op[2]        change(1, x, y)    if op[0] == 2:        x = op[1]        print(a[x])
 
J.混乱的数组
 
手算                                    x                         ≤                         10                              x\le10                  x≤10
 
import bisectimport sysimport copyfrom collections import deque, defaultdictimport heapqfrom itertools import accumulate, permutations, combinationsimport mathinput = lambda: sys.stdin.readline().rstrip("\r\n")printf = lambda d: sys.stdout.write(str(d) + "\n")# INF = 0x3f3f3f3f3f3f# sys.setrecursionlimit(100000)def read():    line = sys.stdin.readline().strip()    while not line:        line = sys.stdin.readline().strip()    return map(int, line.split())def I():    return int(input())x = I()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)
 
注意
 
非官方题解，只是我自己的做法，如果有错误，或者有更好的做法都欢迎指正。