第十四届蓝桥杯大赛软件赛省赛pythonB(含代码)_大学生能参加的python类比赛

A.2023

暴力即可

import bisect
import sys
import copy
from collections import deque, defaultdict
import heapq
from itertools import accumulate, permutations, combinations
import math

input = 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 = 12345678
b = 98765432
cnt_all = 0
ans = 0

for 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
            break
print(cnt_all - ans)
# 85959030
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

B.硬币兑换

注意，只有新币可以兑换，最后结果不论硬币新旧。
故应当将1 + 2022， 2 + 2021， … ，1011 + 1012。

a = [i for i in range(2024)]
a = a + [0] * 2024
left = 1
right = 2022
while left < right:
    a[left + right] += a[left]
    a[right] -= a[left]
    a[left] = 0
    left += 1
    right -= 1

print(max(a))
# 513589
1
2
3
4
5
6
7
8
9
10
11
12
13

C.松散子序列

import sys

input = 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] * n
if 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))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

D.管道

直接遍历每一个阀门，定义数组 $vi{s}_i$ 为第 $i$ 个阀门最早感应到水流的时间。

import bisect
import sys
import copy
from collections import deque, defaultdict
import heapq
from itertools import accumulate, permutations, combinations
import math

input = 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 < vis[left]:
        vis[left] = t
        t += 1
        left -= 1

    t = s + 1
    while right <= len and t < vis[right]:
        vis[right] = t
        t += 1
        right += 1


print(max(vis[1::]))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

E.保险箱

写的贪心，感觉不对。

import bisect
import sys
import copy
from collections import deque, defaultdict
import heapq
from itertools import accumulate, permutations, combinations
import math

input = 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())


n = I()
x = input()
y = input()
prev = 0
ans = 0
for i in range(n-1, -1, -1):
    tmp_x = int(x[i]) + prev

    tmp_y = int(y[i])
    if tmp_x > tmp_y:
        if (tmp_x - tmp_y) - (tmp_y + 10 - tmp_x) > 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 = 0

print(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

F.树上选点

暴力枚举第一个点，再找第二个点。

import bisect
import sys
import copy
from collections import deque, defaultdict
import heapq
from itertools import accumulate, permutations, combinations
import math

input = 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] + value
deep = [0] * (n + 1)
dfs_deep(1, 0)
ans = 0

for 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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

G.T字消除

没做。

H.独一无二

开个cnt数组，每次dis[u]+w == dis[v]的时候+1

import bisect
import sys
import copy
from collections import deque, defaultdict
import heapq
from itertools import accumulate, permutations, combinations
import math

input = 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 = -1


def add(a, b, c):
    global idx
    e[idx].v = b
    e[idx].w = c
    e[idx].ne = h[a]
    h[a] = idx
    idx += 1


def 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 < dis[v]:
                dis[v] = dis[u] + w
                if not vis[v]:
                    heapq.heappush(q, [dis[v], v])
            if dis[u] + w == dis[v]:
                cnt[v] += 1

    cnt[s] = 1
    for i in range(1, n + 1):
        print(cnt[i] - 1)


n, m = read()
h = [-1] * (n + 1)
idx = 0
e = [Edge() for _ in range(m)]
for _ in range(m):
    u, v, c = read()
    add(u, v, c)
dijkstra(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

I.异或和

a维护以x为根的子树异或和, prev维护每个结点的点权。
每次change只需要向上更改贡献即可。
正解应该是 dfs序+树状数组/线段树 维护

import bisect
import sys
import copy
from collections import deque, defaultdict
import heapq
from itertools import accumulate, permutations, combinations
import math

input = 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 0


n, m = read()
a = list(read())
a = [0] + a
prev = 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])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

J.混乱的数组

手算 $x\le 10$

import bisect
import sys
import copy
from collections import deque, defaultdict
import heapq
from itertools import accumulate, permutations, combinations
import math

input = 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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

注意

非官方题解，只是我自己的做法，如果有错误，或者有更好的做法都欢迎指正。