第十五届蓝桥杯 Python B 组省赛

南宫谨 2024-09-30 13:35:02 阅读 68

这届比赛的题目数量总共有八道,比之前少了两道,而且 Python 组题目的难度比去年下降了不少,同时也是所有组里面难度最低的。不知道是不是为了照顾参赛的选手水平。去年 Python 组的题太难了,我到现在还有好几道不会的题🫢😥。

A:穿越时空之门

考察:字符串、枚举

3a4ce28a8bccb87bdb2572fe7a91ec8a.png

解题思路

从 1 枚举到 2024,遇到符合条件的数就计数器加一,最后输出计数器即可。

代码

<code>ans = 0

def check(x): # 判断是否符合条件

s1, s2 = sum(int(i) for i in bin(x)[2:]), 0

while x:

s2 += x % 4

x //= 4

return s1 == s2

for i in range(1, 2025):

ans += check(i)

print(ans) # 63

最后答案为: 63

B:数字串个数

考察:容斥原理、快速幂取余

c109b8a546997001c736694d484ef474.png

解题思路

根据条件一:该数字串只能由数字 1 ~ 9 组成。

根据条件二:要减去不包含数字 3 或 7 的。用容斥原理做,集合总大小为:9^10000,减去两个8^10000,由于多减了一个两个都不含的,再加上一个 7^10000。

快速幂取模可以用 Python 的内置函数 pow 实现。

代码

<code>mod = 10**9 + 7

# 157509472

print((pow(9, 10000, mod) - 2 * pow(8, 10000, mod) + pow(7, 10000, mod)) % mod)

最后答案为:157509472

C:连连看

考察:枚举

b2578c9850267df156b80ba2faa58322.png

8573290dd921b4bdb774f14d8a8c932a.png

解题思路

由于要寻找横纵坐标差的绝对值相同的格子对的数量,所以有左上、右上、左下、右下四个方向。

但是在顺序枚举的过程只需要找两个方向就够了,要不然枚举到后面格子的时候会产生重复判断。

代码

<code>n, m = map(int, input().split())

a = [list(map(int, input().split())) for _ in range(n)]

ans = 0

for i in range(1, n): # 枚举左上方向

for j in range(1, m):

for k in range(1, min(i, j) + 1):

if a[i][j] == a[i - k][j - k]:

ans += 2

for i in range(n - 1): # 枚举左下方向

for j in range(1, m):

for k in range(1, min(n - i, j + 1)):

if a[i][j] == a[i + k][j - k]:

ans += 2

print(ans)

测试样例

样例一

输入:

3 2

1 2

2 3

3 2

输出:

6

样例二

输入:

3 3

3 2 3

2 3 2

3 2 3

输出:

20

D:神奇闹钟

考察:时间处理

9bae0172ece20dbb3d95c0983286d1da.png

06f724529cbea0719d3387eb18809937.png

解题思路

可以使用 Python 标准库中的 datetime 模块来解决此题。

本题中的输入是标准的 iso 格式日期时间,所以可以直接解析为 datetime 对象。

计算上一次响的时间:用总的分钟数减去对时间间隔求余的余数得到上次响的分钟数,再加上起始时间,转化为 datetime 对象,最后输出即可。

代码

<code>from datetime import *

bg = datetime.fromisoformat('1970-01-01 00:00:00')

for _ in range(int(input()):

date, time, dif = input().split()

dt = datetime.fromisoformat(date + ' ' + time)

nows = int((dt - bg).total_seconds()) // 60 # 分钟数

nows -= nows % int(dif)

print(bg + timedelta(minutes=nows))

测试样例

样例一

输入:

2

2016-09-07 18:24:33 10

2037-01-05 01:40:43 30

输出:

2016-09-07 18:20:00

2037-01-05 01:30:00

E:蓝桥村的真相

考察:分类讨论、找规律

ceb435121246feefdd537c83f887387c.png

b469d75bfe97be861ec4b41820042ea4.png

解题思路

分别讨论一个村民的断言为假话、真话和后面的村民的断言为假话、真话的情况。再往后的村民的断言真假都可以通过前面的断言真假推断出来。

51654d647a3eed9a1b2307f4f5787c97.png

 再往后就是之前的重复了。

注意上面前三个分支需要村民个数为 3 的倍数才行,这时“假”的个数为 2n;如果不为 3 的倍数,则只有最后一个情况符合条件,这时“假”的个数为 n。

代码

<code>for _ in range(int(input())):

n = int(input())

print(n * (1 + (n % 3 == 0)))

F:魔法巡游

考察:哈希表、DP

fd0c82f59bdc78bcbf5203f3f3c279b0.png

9c2be0846251fb8fd77332cd98e3d82d.png

解题思路

用一个哈希表统计上一个包含 '0'、'2'、'4' 的符石作为序列末尾的最长序列长度。

最后输出序列最大值即可。

代码

<code>cin = lambda: list(map(int, input().split()))

n, s, t = int(input()), cin(), cin()

dig1, dig2 = defaultdict(int), defaultdict(int)

digs = ('0', '2', '4')

for i in range(n):

num1, num2 = str(s[i]), str(t[i])

d1, d2 = dict(dig1.items()), dict(dig2.items())

for d in digs:

if d in num2 and d in d1:

dig2[d] = max(dig2[d], d1[d] + 1)

for d in digs:

if d in num1:

if d in d2:

dig1[d] = max(dig1[d], d2[d] + 1)

else:

dig1[d] = 1

print(max(max(dig1[d], dig2[d]) for d in digs))

测试样例

样例一

输入:

5

126 393 581 42 44

204 990 240 46 52

输出:

4

样例二

输入:

5

222 222 222 222 222

222 222 222 222 222

输出:

5

G:缴纳过路费

考察:缩点、并查集、DFS

a8605a52156f7de9937a8cd9aba6aba8.png

afba188b1075f410ab557553f8d831ed.png

解题思路

分析:由于要满足路径中最贵的一次收费在 [L, R] 区间内,所以收费大于 R 的路径是一定不可以经过的,而对于收费小于 L 的路径可以经过,但是不能让整条路径的收费全部小于 L,要不然路径的最大值也小于 L 了。

对此,我们要:将所有小于 L 的边连接的点缩成一个点(缩点),并记录缩后的点数(就是记录有多少个点缩成了这一个点),大于 R 的边则直接舍弃(不加到图中)。

然后再搜索满足条件的点对的数量,比如:有 3 个点缩成的点 A 和 2 个点缩成的点 B 之间有一条 [L, R] 之间的边,那么就有 2 x 3 = 6 个点对。示意图如下:

45a6be6a300fa1c6d2c53edf23870473.png

 对应的点对分别为:(1, 4)、(1, 5)、(2, 4)、(2, 5)、(3, 4)、(3, 5)。

怎么实现缩点呢?并查集!将所有小于 L 的边连接的点用并查集来合并,让集合的根作为合并后的新点。注意记录集合的大小(也就是新点是由多少旧点合并来的)。

最后使用 DFS 累加点对数量。比如点 A 是由 3 个旧点合并而来,与其连通的有 2 个新点,对应 5 个旧点,那么以 A 为第一个坐标的点对就有 3 x (8 - 3) 对。

注意累加的点对有重复((1, 2)、(2, 1) 是同一对),最后要除以二。

代码

<code>cin = lambda: list(map(int, input().split()))

n, m, l, r = cin()

e = [set() for _ in range(n + 1)]

# s[i] == i 表示 i 为新点,sz[i] 表示新点 i 的大小

s, sz = list(range(n + 1)), [1] * (n + 1)

def find(x):

if s[x] == x:

return x

s[x] = find(s[x])

return s[x]

edges = [cin() for _ in range(m)]

for u, v, w in edges:

if w > r: continue

su, sv = find(u), find(v)

if w < l:

# 合并

s[su] = sv

sz[sv] += sz[su]

# 以新点建图

for u, v, w in edges:

if l <= w <= r:

su, sv = find(u), find(v)

e[su].add(sv)

e[sv].add(su)

vis = [False] * (n + 1)

def dfs(u, block): # block 保存新点,返回值表示总大小

block.append(u)

res, vis[u] = sz[u], True

for v in e[u]:

if vis[v]:

continue

res += dfs(v, block)

return res

ans = 0

for i in range(1, n + 1):

if s[i] == i and not vis[i]:

block = []

t = dfs(i, block)

for u in block:

ans += sz[u] * (t - sz[u])

print(ans // 2)

测试样例

样例一

输入:

5 5 1 2

1 2 2

1 3 5

1 4 1

2 4 5

2 5 4

输出:

3

样例二

输入:

10 12 5 8

1 5 3

1 2 8

2 5 5

2 6 7

5 7 2

7 10 9

8 10 2

8 9 4

2 8 7

3 7 6

3 8 5

3 4 10

输出:

30

H:纯职业小组

考察:贪心

9f7ba5fdfdcb525c08e00cdcdfedf446.png

02649c8032955c88d181904f3ffa15a4.png

解题思路

把这道题反过来想,找出组成 k 个“纯职业小组”的最大人数。

同职业中选 3x+2 个是最优的,其中(3x+2 <= n <= 3x + 3)

代码

<code>cin = lambda: list(map(int, input().split()))

for _ in range(int(input())):

n, k = cin()

cnt = Counter()

for i in range(n):

a, b = cin()

cnt[a] += b

if sum(c // 3 for c in cnt.values()) < k:

print(-1)

continue

ans = 0

for c in cnt.values():

if c % 3 == 0:

ans += c - 1

k -= c // 3 - 1

elif c % 3 == 1:

if c == 1:

ans += 1

else:

ans += c - 2

k -= c // 3 - 1

else:

ans += c

k -= c // 3

if k <= 0:

print(ans - k * 3)

break

else:

print(ans + k)

测试样例

样例一

输入:

2

3 2

1 3

2 3

3 3

3 5

1 3

2 3

3 3

输出:

8

-1

样例二

输入:

1

6 60

1 100

2 43

3 51

1 32

2 55

3 98

输出:

274

最后

今年蓝桥杯省赛的成绩出来了,居然是河北省B组第一名哈哈哈~

5e68f3ee79c3cb0cc2f5a9e48febf201.png

可惜的是不知道具体多少分😥

最后祝大家都能蓝桥杯榜上有名,心想事成🤪❤️!!!!

有什么问题欢迎在评论区留言。



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。