2025年第十六届蓝桥杯 Python 研究生组省赛题目与题解

发表于 更新于

8道题，题面比较好理解，难度感觉也比去年的简单了。

A. 偏蓝

用三个0至255之间的整数（包含0和255）分别表示颜色的红、绿、蓝三个分量。

在这种颜色的表示方法下，小蓝定义了一种颜色是偏蓝的，是指蓝色分量大于红色分量，且蓝色分量大于绿色分量。例如，红、绿、蓝分别为10、10、11 时是偏蓝的；红、绿、蓝分别为100、200、200时不是偏蓝的。

小蓝想知道，有多少种不同的颜色是偏蓝的。两种颜色如果在红、绿、蓝中至少有一个分量值不同，就认为是不同的。

1
2
3
4
5
6
ans = 0
for r in range(256):
    for g in range(256):
        ans += 255 - max(r, g)

print(ans)

B. IPV6

所有IPv6地址（全0—全1）的最短压缩形式的长度的和为多少？

先枚举每一个16位的块的0和1的情况。然后可以分别考虑在一个01块确定的情况下，0、冒号、非0的数对于答案的贡献。

另外一种思路是先不考虑相邻的值为0的段合并压缩起来的情况，求出长度，然后再考虑会压缩的段数，最后减掉这些压缩的长度。

代码太丑就不放了。答案应该是905307083

C. 变换数组

输入一个数组a，包含有n个元素a1,a2,··· ,an。对这个数组进行m次变换，每次变换会将数组a中的每个元素ai转换为ai ·bitCount(ai)。其中bitCount(x)表示数字x的二进制表示中1出现的次数，例如bitCount(3)=2，因为3的二进制表示为11，其中1出现了两次。输出变换之后的数组内容。

nm都很小，直接模拟。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
n = int(input())
a = list(map(int, input().split()))
m = int(input())

def bitcount(x):
    ret = 0
    while x != 0:
        ret += x % 2
        x //= 2
    return ret

for t in range(m):
    for i in range(n):
        a[i] = a[i] * bitcount(a[i])

for i in range(n):
    print(a[i], end=' ')
print()

D. 最大数字

n个连续的整数1,2,3,··· ,n，找到一个排列，使得这些数字转换成二进制表示，拼接形成的二进制数的值最大。

经典贪心题 leetcode 3309，自定义排序函数。注意长字符串转整数要用sys.set_int_max_str_digits()。

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
import sys
def cmp_to_key(mycmp):
    class K:
        def __init__(self, obj, *args):
            self.obj = obj
        def __lt__(self, other):
            return mycmp(self.obj, other.obj) < 0
        def __gt__(self, other):
            return mycmp(self.obj, other.obj) > 0
        def __eq__(self, other):
            return mycmp(self.obj, other.obj) == 0
        def __le__(self, other):
            return mycmp(self.obj, other.obj) <= 0
        def __ge__(self, other):
            return mycmp(self.obj, other.obj) >= 0
        def __ne__(self, other):
            return mycmp(self.obj, other.obj) != 0
    return K

def d(x, y):
    l = int(format(x, 'b') + format(y, 'b'), 2)
    r = int(format(y, 'b') + format(x, 'b'), 2)
    return r - l
sys.set_int_max_str_digits(1000000)
n = int(input())
a = [i for i in range(1, n + 1)]
a.sort(key=cmp_to_key(d))
str = ''
for i in a:
    str += format(i, 'b')
print(int(str, 2))

E. 小说

小蓝是一位网络小说家。现在他正在撰写一部新的推理小说，这部小说有 n 个不同的人物。

小说的每一章都有以下三种情节的一种：

1、A 发现 B不知道真相。

2、A 发现 B知道真相。

3、A 知道了真相。

为了保证读者的协调和新鲜感，小蓝的小说还要满足以下要求：

1、“ B 发现 A不知道真相”不能在“A知道了真相”后。

2、“ B 发现 A知道真相”不能在“A知道了真相”前。

3、“ B 发现 A不知道真相”不能在“B发现A知道真相”后。

4、相邻的两章情节类型不同，例如如果第一章是A发现B不知道真相那么第二章就不能是C发现D不知道真相。

5、完全相同的情节不能出现两次。

现在小蓝希望知道，他最多能写多少章。

找规律，三个人物的情况可以这样：

1、B 发现A不知道真相。

2、A 知道了真相。

3、B 发现A知道真相。

4、A 发现B不知道真相。

5、C 发现A知道真相。

6、C 发现B不知道真相。

7、B 知道了真相。

8、A 发现B知道真相。

9、A 发现C不知道真相。

10、C 发现B知道真相。

11、B 发现C不知道真相。

12、C 知道了真相。

13、B 发现A知道真相。

其实最优解就是每个人都会发现每个人不知道和知道真相。

但是第一个人不知道和最后一个人知道只能有1次。

所以答案就是 $n (n - 1) 2$ (每个人发现每个人) - $(n - 2) * 2$ (第一个和最后一个) + n (自己知道真相)

1
2
3
4
5
n = int(input())
if n == 1:
    print(1)
else:
    print(n * (n - 1) * 2 - n + 4)

F. 01 串

给定一个由0,1,2,3··· 的二进制表示拼接而成的长度无限的 01 串。其前若干位形如011011100101110111···。请求出这个串的前x位里有多少个1。x <= 10^18

先判断这个x落到的数长度多少，再一位一位判断。

预处理x对应的数的长度之前的1的个数。

递归判断x对应的数哪一位是1，哪一位是0。如果这一位是1，就要加上这一位是0的所有数的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
nums = [0,2] # 长度为i的元素个数
cnt = 2
for i in range(70):
    nums.append(cnt)
    cnt *= 2

bits = [0,2] # 长度为i一共多少位？
for i in range(2, 70):
    bits.append(nums[i] * i)

x = int(input())
ans = 0

def find1(x, base, bit, ones, pre):
    global ans
    if x == 0:
        return
    
    # < 1numbers
    if x <= base:
        i = 0
        while x > 0 and i < len(pre):
            if pre[i] == '1':
                ans += 1
            i += 1
            x -= 1
        return

    l_bitzero = nums[bit + 1] * base // 2 # ...0....的长度
    if l_bitzero <= x:
        x -= l_bitzero
        ans += nums[bit] // 2 * (bit - 1) + 2 ** (bit - 1) * ones
        find1(x, base, bit - 1, ones + 1, pre + '1') # ...1....
    else:
        find1(x, base, bit - 1, ones, pre + '0') # ...0....


def find(x, base):
    global ans
    for i in range(1, 70):
        if x - bits[i] >= 0:
            x -= bits[i]
            if i == 1:
                ans = 1
            else:
                ans += 2 ** (i - 1) * (i - 1) // 2 + nums[i]
        else:
            find1(x, i, i - 1, 1, '1')
            break

if x == 1:
    print(0)
elif x == 2:
    print(1)
else:
    find(x, 0)
    print(ans)

G. 登山

小蓝正在登山，山峰的高度构成n行m列的正整数矩阵，ai,j表示第i行第j列格子(i, j)上的山峰的高度。小蓝以一种特别的方式进行登山，如果他此刻在第p行第q列的格子(p,q)上，那么下一步可以选择：

1)走到格子(i,q)，满足ai,qp；

2)走到格子(i,q)，满足ai,q>ap,q且i<p；

3)走到格子(p, j)，满足ap,jq；

4)走到格子(p, j)，满足ap,j>ap,q且j<q。

小蓝想知道，如果他依次从每一个格子开始出发，按照最优策略，他最高能到达的山峰的高度的平均值是多少？

N*M <= 1e6

直接对所有山峰排序，从高到低遍历。每次搜索一个山峰能到达的所有点并标记。

用并查集合并山峰也可以。

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
import sys

sys.setrecursionlimit(1000000000)
a = []
b = []
n, m = map(int, input().split())
vis = [[0 for i in range(m)] for j in range(n)]
for i in range(n):
    a.append(list(map(int, input().split())))
    vis.append([])
    for j in range(m):
        b.append([i, j, a[i][j]])
b.sort(key=lambda x: x[2], reverse=True)
ans = 0

def find(x, y, w):
    global ans
    ans += w
    vis[x][y] = 1
    for i in range(m):
        if vis[x][i] == 0 and ((a[x][i] < a[x][y] and i > y) or (a[x][i] > a[x][y] and i < y)):
            find(x, i, w)
    for i in range(n):
        if vis[i][y] == 0 and ((a[i][y] < a[x][y] and i > x) or (a[i][y] > a[x][y] and i < x)):
            find(i, y, w)

for i in b:
    if vis[i[0]][i[1]] == 0:
        find(i[0], i[1], i[2])

print('{:f}'.format(ans / n / m))

H. 甘蔗

小蓝种了一排甘蔗，甘蔗共n根，第i根甘蔗的高度为ai。小蓝想砍一些甘蔗下来品尝，但是他有强迫症，不希望甘蔗的高度显得乱糟糟的。具体来说，他给出了一个大小为m的整数集合B={b1,b2,··· ,bm}，他希望在砍完甘蔗后，任意两根相邻的甘蔗之间的高度差|ai−ai+1|都要在这个集合B中。小蓝想知道他最少需要砍多少根甘蔗（对于高度为h的甘蔗，他可以将其砍成x高度的甘蔗，x∈{0,1,2,··· ,h−1}）。

n,m <= 500 ai, bi <= 1000

写了一个 O(NMH) 的dp, f[i][j] 表示第 i 根甘蔗的高度为 j 时，前 i 根甘蔗需要砍掉的最小数量。

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
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
f = [[-1 for i in range(1010)] for j in range(n)]
f[0][a[0]] = 0
for i in range(a[0]):
    f[0][i] = 1
for i in range(1, n):
    for j in range(a[i] + 1):
        best = 1
        if j == a[i]:
            best = 0
        for k in b:
            if f[i][j] == best:
                break
            cur = -1
            if j - k > 0 and f[i - 1][j - k] != -1:
                cur = f[i - 1][j - k]
            if j + k <= a[i - 1] and f[i - 1][j + k] != -1:
                if cur == -1:
                    cur = f[i - 1][j + k]
                else:
                    cur = min(cur, f[i - 1][j + k])
            if cur == -1:
                continue
            if j != a[i]:
                cur += 1
            if f[i][j] == -1:
                f[i][j] = cur
            else:
                f[i][j] = min(f[i][j], cur)
ans = -1
for i in range(a[i] + 1):
    if f[n - 1][i] != -1:
        if ans == -1:
            ans = f[n - 1][i]
        else:
            ans = min(ans, f[n - 1][i])
print(ans)