2025蓝桥杯PythonA组省赛题解

一定注意，由于在编写本题解时还没有在线题目。所以：

本题解仅供参考，在题意、思路、code上都可能发生错误！

A. RGB三色

题意

我们可以用三个0~255之间的数(r,g,b)来表示一个颜色，如(0,0,255) 表示蓝色。

那么请问所有的颜色中，有多少种颜色是“偏蓝色”

我们定义当且仅当$b > r $ 并且$b > g$ ，$(r,g,b)$ 是偏蓝色的。

思路 & 代码

直接暴力枚举！复杂度$256^3 = 16777216$ 。

ans = 0
for r in range(256):
    for g in range(256):
        for b in range(256):
            if(b > g and b > r):
                ans += 1
print(ans) # 5559680

方法二：

使用公式计算：

如果我们给定b，那么r和g可以取$[0,b-1]$ 中的任何一个值，有$b^2$ 种可能。于是我们就有如下公式：

$ans = \underset{b = 1}{\overset{255}{\sum}} b^2$

ans = 0
for b in range(1,256):
    ans += b * b
print(ans) # 5559680

B. IPv6的缩写长度

题意

给出IPv6的缩写规则：

IPv6由8段组成，每段4个16进制数。

省略规则如下：

对于一段的四个十六进制数，前导零可以省略。
如果一段中只包含零，必须保留一个零。
可以将一段连续的0省略，用:: 替代，但是整个IPv6只能缩写一段。

下面给出一些例子

缩写前	缩写后
2001:0db8:0000:0000:0000:ff00:0042:8329	2001:db8::ff00:42:8329
0000:0000:0000:0000:0000:0000:0000:0001	::1
0000:0000:0000:0000:0000:0000:0000:0000	::
ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff	ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff
2001:0db8:85a3:0000:0000:8a2e:0370:7334	2001:db8:85a3::8a2e:370:7334

那么请问：

所有的IPv6地址，把他们的长度加起来是多少？

由于答案太大，我们对$10^9+7$ 取模。

思路

直接枚举肯定是不可以的。

我们考虑按段分类枚举：

对于八个段中的每一个段，我们分为以下五种情况：

这一段是0 ,共1个数符合情况
这一段是一位数，即三位前导零，共(000f - 0 = 15)个数符合情况
这一段是两位数，即两位前导零，共`(00ff - 000f = 15*16)个数符合情况
这一段是三位数，即一位前导零，共(0fff - 00ff = 15*16*16) 个数符合情况
这一段是四位数，没有前导零，共(ffff - 0fff = 15*16*16*16) 个数符合情况

当我们固定了八段所有的情况后，他的长度就可以求出来了，于是我们对每段枚举这五种情况。循环的时间复杂度是$5^8$ 。

之后我们假设这个IPv6地址如下：a0:a1:a2:a3:a4:a5:a6:a7

那么我们就可以计算得到在缩写前的总长度是$length_{pre} = (l_0+l_1+l_2+…+l_7) + 7$ (七个冒号) (这里$a_i = 0$时$l_i=1$ ,其他时候$l_i = a_i$ )

在缩写时我们对每段连续0区间进行计算，得到他的缩小程度。我们取其中的最大值$length_{omit}$即可。

如何计算？假设我们得到了一个区间$[l,r]$

如果$l = 0 \text{ and }r = 7$ , $length_{omit} = 13$
若不满足第一项：如果$l = 0 \text{ or } r = 7$ , $length_{omit} = 2 * (r - l + 1) - 2$
如果不满足第一、二项；$length_{omit} = 2 * (r - l + 1) - 1$

这样我们就计算出来这个地址的长度，那么这个地址的总数则是每段所包含的数的数量，把他们乘到一起。$cnt{all} = \Pi{i = 0}^7 cnt(a_i)$

那么整个这个类型的IPv6的地址总长度，当然就是$cnt{all} * (length{pre} - length_{omit})$ 了。

注：我们枚举八个段，可以使用八重循环（太丑陋！）

也可以直接枚举一个“五进制数”，从0 到$5^8$ , 然后对他进行进制拆分

代码

我们在调试时可以把N设置的比较小，然后输出所有的情况来查看计算是否有问题。

N = 8
ans = 2 # 这里直接把全零的情况提取出来，后面的range从1开始
cnt = [1,15,15*16,15*16*16,15*16*16*16]
MOD = int(1e9+7)
for x in range(1,5**N):
    a = [] # a[i]表示第i位是几
    for right in range(N):
        a.append(x%5)
        x //= 5

    # 接下来找连续的0串
    left = -1
    length_omit = 0 
    for right in range(N):
        # 这里枚举的区间是(left,right],区间长度是right-left
        if(a[right] == 0):
            if(left == -1 or right == N-1):
                length_omit = max(length_omit,2 *(right-left)-2)
            else:
                length_omit = max(length_omit,2 *(right-left)-1)
        else :
            left = right
    length_pre = 0
    for i in range(N):
        if(a[i] == 0):
            length_pre += 1
        else:
            length_pre += a[i]
    length_pre += (N-1)
    cnt_all = 1
    for i in range(N):
        cnt_all = cnt_all * cnt[a[i]] % MOD
    # print(a)
    # print(length_pre,length_omit)
    ans += cnt_all * (length_pre - length_omit) % MOD
    ans %= MOD
print(ans) # 905307083

C. 2025

题意

给出$n,w$, 求出n行m列的2025矩阵：

第1行是2025的不断重复
从第2行开始，每行都是上一行左移一位

当n = 4,m = 10时如下：

思路

我们发现，左下-右上对角线上的元素是相同的。他们满足$j + i = c$ ，即列和行的和是定值。

代码

import sys
Input = sys.stdin.readline
n,m = map(int,Input().split())

ch = [2,0,2,5]
for i in range(n):
    for j in range(m):
        print(ch[(i+j)%4],end="")
    print("")

D 1到n的二进制拼接

题意

把1到n这些数，转换为二进制，然后进行拼接操作。

问怎样拼接能使得数值尽可能大？把这个01串再转换回十进制。

例如：n = 3时，$1,2,3$ 的二进制分别为$1,10,11$ ，进行拼接后最大为11110 ,转换为十进制为30

$n \le 10000$

思路

把代码分为三部分，然后每部分分别处理即可。

第一步，二进制转换，我们使用字符串来保存。

对每个数进行按位分离(每位为2)，然后拼接成字符串即可。

第二步，找最大的拼接。

这是一个经典例题最大数(leetcode) , 简单地说就是对字符串进行排序，排序规则是“对于相邻的两个串，如果$s_a + s_b > s_b + s_a$，那么$s_a$ 在$s_b$ 的前面” ,详细证明可以看leetcode例题的题解。

第三步，对拼接后的字符串进行二进制转十进制。

从最高位枚举然后乘起来即可，我们python不需要考虑溢出问题。

代码

n = int(input())

s_lst = []
for i in range(1,n+1):
    a = []
    x = i
    while(x):
        a.append(str(x%2))
        x //= 2
    s_lst.append("".join(a[::-1])) # 注意这里要倒过来

# 自定义排序推荐重写类的___lt__ 方法
class Node():
    def __init__(self,s):
        self.s = s
    def __lt__(self,other):
        return self.s+other.s > other.s+self.s

node_lst = []
for i in s_lst:
    node_lst.append(Node(i))
# 排序
node_lst.sort()
# 拼接
ans_str = "" 
for i in node_lst:
    ans_str += i.s

# 进制转换
ans = 0
for i in ans_str:
    ans = ans * 2 + int(i)
print(ans)

E. 彩色瓶子

题意

给你n个瓶子，以及整数k。

每隔k个他们的瓶子颜色就是一样的。即对于所有的i，满足$colori = color{i + k}$ , 每个瓶子中都有一定量的水。记作$a_1,a_2,…,a_n$ 。

你可以任意次地将第$i$个瓶子中的整数量的水倒入相同颜色的瓶子$j$中 ,唯一的要求是$i < j$。

那么请问，在任意次操作后，所有瓶子中含水量的最小值，最大的可能是多少。

思路

最大的最小值，我们要首先尝试二分答案，在本题，二分求瓶子的最小值x。

我们的check函数应该是这样的：

我们对每个水瓶进行如下处理：

如果当前水瓶的水超过x，那么把多余的水存下来，供后面使用。
如果当前水瓶的水不够x，则用之前相同颜色水瓶存的水补满，补不满则宣告这个x是不可能的。

如果check(x) == True，我们则可以考虑令x更大一些

如果check(x) == False ，我们则考虑令x更小一些。

于是这样就能找到满足check(x) == True的最大的x了。

代码

import sys
input = sys.stdin.readline
n,k = list(map(int,input().split()))
a = list(map(int,input().split()))


def check(x):
    global n,a,k
    have = [0] * k 
    for i in range(n):
        if(a[i] >= x):
            have[i % k] += a[i] - x
        else:
            if(have[i%k]+a[i] >= x):
                have[i%k] -= x - a[i]
            else:
                return False
    return True

l = 1
r = int(1e9)
while(l < r):
    mid = (l + r + 1) // 2
    if(check(mid)):
        l = mid
    else:
        r = mid - 1
print(l)

F.拼好数

题意

给出n个正整数。 $a_1,a_2,…,a_n$

你可以将他们拼接为若干个组。要求如下：

每组最多由三个数拼接而成
拼接完成后“6”的数位数量不少于6个。

那么请问最多可以分为多少组？

$n \le 1000$

思路

我们不关心$a$数组之间的顺序关系，并且只关心$a_i$ 中包含6的数量。所以我们可以统计一下出现$(0,1,2,3,4,5,6+)$个6的数分别有多少个。

注意

当一个数中出现了不少于6个6时，那么只需要一个这个数就可以使得答案成立。我们可以把这一类数归为同一类。这一类不需要参与计算，他们单独一组就是最优的。
当一个数中出现了0个6时，这个数是没有用的，我们可以直接扔掉。

于是我们就得到了cnt数组。其中$cnt[i]$ 表示出现了i个6有多少个数。

于是我们就可以考虑使用搜索来求了，那么如何进行状态转移？action为选择了一个合适的组。我的做法是预处理出所有可选的operator。得到如下数组(直接三重循环即可)：

1
2

ope = [[0, 1, 5], [0, 2, 4], [0, 2, 5], [0, 3, 3], [0, 3, 4], [0, 3, 5], [0, 4, 4], [0, 4, 5], [0, 5, 5], [1, 1, 4], [1, 1, 5], [1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 3], [1, 3, 4], [1, 3, 5], [1, 4, 4], [1, 4, 5], [1, 5, 5], [2, 2, 2], [2, 2, 3], [2, 2, 4], [2, 2, 5], [2, 3, 3], [2, 3, 4], [2, 3, 5], [2, 4, 4], [2, 4, 5], [2, 5, 5], [3, 3, 3], [3, 3, 4], [3, 3, 5], [3, 4, 4], [3, 4, 5], [3, 5, 5], [4, 4, 4], [4, 4, 5], [4, 5, 5], [5, 5, 5]]
# 我们可以将这里的0视为不选，也可以视为选择一个包含0个6的数，因为“包含0个6的数”可以是任意多个。

然后我们就可以通过这些操作来进行状态转移了。

一个状态可以描述为五元组$(cnt[1],cnt[2],…,cnt[5])$ 的取值。

之后我们进行搜索即可。

优化

本体的关键在于优化，下面详细讲一下优化策略：

最刚需的优化就是记忆化搜索：

我们发现对于某个状态，我们可能会重复了很多很多次，比如初始状态为$(0,0,3,3,3)$ ，那么如下两种序列都可以得到$(0,0,1,1,3)$ , 于是我们就会计算两次(甚至更多次)状态$(0,0,1,1,3)$

序列一：

$(0,0,3,3,3) \overset{ope(0,3,3)}{\to} (0,0,1,3,3)\overset{ope(0,4,4)}{ \to} (0,0,1,1,3) \\ (0,0,3,3,3) \overset{ope(0,3,4)}{\to} (0,0,1,3,3)\overset{ope(0,4,4)}{ \to} (0,0,1,1,3) \\$

所以我们每次计算出一个状态的结果后，立刻把他放到字典当中。$dic(state) = value$ .

当下次再一次遇到这个状态时，我们就可以直接返回这个值了。

剪枝

本题的剪枝主要是计算答案的上界。假设我们要从状态$u$ 转移到状态$v$ 。 $v = (s_1,s_2,s_3,s_4,s_5)$

那么状态v的贡献一定不会超过这两个值：

首先，必须选择至少两个数来组成一组，所以

$ans_v \le \frac{s_1+s_2+...s_5}{2}$

其次，每组必须有至少6个6.所以

$ans_v \le \frac{s_1 + 2 * s_2 + ...+ 5*s_5}{6}$

当我们在取到等号时，仍然无法做到$ans_v + 1 > ans_u$ 即更新状态u的答案，那么我们再对v搜索就是徒劳的。这时候应该直接跳过本次搜索。

代码

import sys
input = sys.stdin.readline
n = int(input()) 
a = list(map(int,input().split()))
# n = 1000
# a = [6,66,666,6666,66666] * 200
ope = []
for i in range(6):
    for j in range(i,6):
        for k in range(j,6):
            if(i + j + k >= 6):
                ope.append((i,j,k))

cnt = [0] * 7
for i in range(n):
    x = a[i]
    cc = 0
    while(x):
        if(x % 10 == 6):
            cc += 1
        x //= 10
    cnt[min(cc,6)] += 1

cnt[0] = int(1e12)
# 给cnt[0]一个足够大的值，代表我们可以选择任意数量的无效数。
# 可以减少特判

visit = {} # 记忆化字典
def dfs():    
    # 如果当前完全凑不够6个6就该返回了。
    cc = 0
    for i in range(1,6):
        cc += cnt[i] * i
    if(cc < 6):
        return 0
    ans = 0 # 当前dfs最大可能的取值
    gt = visit.get(tuple(cnt[1:6]),None)
    if(gt != None): # 如果之前计算过，直接返回
        return gt
    for x,y,z in ope:
        ## 尝试选择这组ope
        cnt[x] -= 1
        cnt[y] -= 1
        cnt[z] -= 1
        ok = 0 # 这组ope是否是合法的     
        if(cnt[x] >= 0 and cnt[y] >= 0 and cnt[z] >= 0):
            ok = 1 # 是合法的
        if(ok):
            # 两个剪枝
            c1 = 0
            for i in range(1,6):
                c1 += cnt[i]
            # 是否通过剪枝
            c2 = 0
            for i in range(1,6):
                c2 += cnt[i] * i
            if(c1//2 + 1 > ans and c2 //6 + 1 > ans):
                ans = max(ans,dfs()+1)
        # 不管有没有进入dfs，都要返回现场
        cnt[x] += 1
        cnt[y] += 1
        cnt[z] += 1

    # 最后记得更新visit
    visit[tuple(cnt[1:6])] = ans
    return ans
print(dfs()+cnt[6]) #  别忘了加cnt[6]

"""
6
6 66 666 6666 66666 666666

4
666 66 666666 123456

6
6 6 6 6 6 6
"""

G. 登山

题意

有一个n行m列的矩阵$h$ 。描绘了一个地图上每个格子的高度。$h[i][j]$ 表示第$i$行第$j$ 列的高度。

你当前的节点位置为$(p,q)$每次可以选择下面操作之一：

选择一个$i>p$ 的节点，并且$h[i][q] < h[p][q]$ , 走到节点$(i,q)$
选择一个$i h[p][q]$ , 走到节点$(i,q)$
选择一个$j>q$ 的节点，并且$h[p][j] < h[p][q]$ , 走到节点$(p,j)$
选择一个$j<q$ 的节点，并且$h[p][j] < h[p][q]$ , 走到节点$(p,j)$

设你从(x,y) 节点出发，能够到达的最高的高度为$v_{x,y}$ , 本题你需要求的是从所有的节点出发能到达的最高高度的总和，数学表示为：

$\underset{x = 1}{\overset{n}{\sum}}\underset{y = 1}{\overset{m}{\sum}} v_{i,j}$

保证$1 \le n,m \le 10^4 , n*m \le 10^6$

思路

首先我们可以发现：

节点之间的路径是无向的，即如果可以从$(x_1,y_1)$ 移动到$(x_2,y_2)$ ，那么反过来一定可以从$(x_2,y_2)$ 移动到$(x_1,y_1)$ 。

即节点之间的边均为无向边。那么又可以得到如下的结论：

如果$(x1,y_1)$ 与$(x_2,y_2)$ 之间有(无向)边, 那么$v{x1,y_1} = v{x_2,y_2}$

于是我们边很容易地想到了染色法求连通块的属性，具体为使用bfs/dfs搜索连通块，或者使用并查集来维护点的联通关系。

一个会超时的反例

以dfs为例，我们的伪代码如下：

height = 0
cnt = 0
def dfs(x,y):
    height = max(height,h[x][y])
    cnt += 1
    for i in range(n):
        if 满足条件 and vis == 0:
            vis[x2][y] = 1
            dfs(x2,y)
    for i in range(m):
        if 满足条件 and vis == 0:
            vis[x][y2] = 1
            dfs(x,y2)
最终这个连通块的贡献就是height * cnt

该dfs的复杂度如下：

我们对每个节点都要进入一次dfs循环($vis[x][y]$从0到1的那一次)，因此一共有$n*m$ 个dfs。

而对于每一个dfs函数，我们都使用了两个循环来找答案。

总的时间复杂度是$O(nm(n+m))$

在本题这是不被允许的。

复杂度的问题在于，在我们染色时，很多时候遇到的都是之前已经遇到过的节点。而这些节点只会花时间判断if为False然后结束，并没有高效地更新答案。

正确的思路

我们改用并查集维护颜色，并尝试借用单调属性进行优化。过程如下：

我们发现，本体的难点在于计算出哪些节点之间是联通的。

我们先逐行分析，取出第一行$h[1]$ , 我们叫他$a$ , 那么根据行动规则：

$a[i]$ 会和所有$j < i, a[j] > a[i]$ 的节点连通。(说人话就是这个节点会和前面所有比他大的节点连通) 。

假设我们的a数组如下：

$\text{1 3 5 4 7 2 9 8 10}$

我们枚举每个元素。下面详细讲解过程：

遇到了1，3，5 。他们之间不能连接。此时有三个小组(1),(3),(5)
遇到了4，他可以和(5) 连接，此时三个小组(1),(3),(5,4)
遇到了7，他不能和任何组(如果7比一个组中的最大值要大，那么就可以和这一组连接)连接，此时四个小组(1),(3),(5,4),(7)
遇到了2，能和(3),(5,4),(7)连接，这三个组合并,现在两个组(1),(3,5,4,7,2)
遇到了9，无法连接，现在三个组(1),(3,5,4,7,2),(9)
遇到了8，和9连接，(1),(3,5,4,7,2),(9,8)
遇到了10，无法连接(1),(3,5,4,7,2),(9,8),(10)

这样我们就分好了组。同组之间的节点可以相互到达。

接下来对每行都进行如上处理。然后对每列再进行处理。行列合并后就得到了连通块。

如何保证时间复杂度？

我们知道我们只关心每组最大的那个成员，所以我们称它为“代表”

每组选择一个代表，可以证明他们本身就是有序关系的（如果后面一个组的max小于前面某个组的max，那么就会触发合并操作），于是我们倒序地找所有比x大的组，将这些组和x一起合并。

于是总的复杂度是$O(n*m)$ 的。

代码

本题代码来自我的队友csdn主页

n, m = map(int, input().split())

mp = [[0] * (m+5) for _ in range(n+5)]
for i in range(1, n+1):
    mp[i][1:m+1] = map(int, input().split())

f = [0] * (n*m+5)
maxh = [0] * (n*m+5)
for i in range(1, n*m+1):
    f[i] = i
    maxh[i] = mp[(i-1)//m+1][(i-1)%m+1]

def to_idx(x, y):
    return (x-1)*m+y-1+1

def findf(x):
    if f[x] == x:
        return x
    else:
        f[x] = findf(f[x])
        return f[x]

def merge(u, v):
    fu, fv = findf(u), findf(v)
    maxh[fu] = max(maxh[fu], maxh[fv])
    f[fv] = fu


for i in range(1, n+1):
    stack = list()  # 高度 并查集位置
    for j in range(1, m+1):
        idx = to_idx(i, j)
        while stack and stack[-1][0] > mp[i][j]:
            merge(stack[-1][1], idx)
            stack.pop()
        stack.append((mp[i][j], idx))

for j in range(1, m+1):
    stack = list()  # 高度 并查集位置
    for i in range(1, n+1):
        idx = to_idx(i, j)
        while stack and stack[-1][0] > mp[i][j]:
            merge(stack[-1][1], idx)
            stack.pop()
        stack.append((mp[i][j], idx))

ans = 0
for i in range(1, n+1):
    for j in range(1, m+1):
        fa = findf(to_idx(i, j))
        ans += maxh[fa]
    #     print(maxh[fa], end=" ")
    # print()

print(ans/(n*m))

"""
2 2
1 4
4 3

2 3
2 4 1
4 2 3

"""

H.原料采购

题意

在一条直线道路上，你在道路的最左边（原点），在原点的右边有n个采购点。

对于第i个采购点，他的单价是$a_i$元 ,一共有$b_i$ 个物品，距离原点$c_i$

你需要采购总共m个物品。公路的行驶单价为$o$ ,这意味着每当你在公路上行走了$2x$米。你就会花费$o x$ 元。(这里的单价是往返单价，所以你到达距离x再返回，则会花费$o*x$ 元 )

那么请问，购买恰好m个物品，最少需要花费多少钱。

思路

很经典的反悔贪心。（解决的问题是可能会在未来遇到更好条件（在本体是更低的单价），而可能又必须在现在就执行的问题）

假设我们要在前i个采购点采购物品。那么路费就是$o * c_i$ 。

此时我们可以在这i个采购点中选择单价最小的m个物品来购买。假设购买清单如下：${(cost_t,buy_t)}_k$

表示买了$buy_t$ 个单价为$cost_t$ 的物品，这样的元组一共有k个（即有k种不同的单价）。

我们便可以算出他们的总花费$COSTi = \sum{t=1}^k cost_t * buy_t$ （这里体现了贪心，即尽量选择单价小的物品）

当我们再多考虑一个采购点时，我们先假设购买第$i+1$ 个采购点的所有物品。那么这时候可能会发生购买的物品超过了m。这时候我们需要“退货” ，假设需要退货$refund_i$件物品, 我们就选择已购买的物品中单价最大的$refund_i$ 个退货就好了。找单价最大的物品可以用单调队列（也就是堆）实现（这里体现了反悔）

重复此过程，答案即为$\underset{i = k} {\overset{n}\sum} (COST_i + o * c_i)$ , 这里的i要从k开始，k的含义为，全买下来所有前k个采购点的物品，恰好大于等于m个物品。（即k-1就不够了）

代码

import sys
from queue import PriorityQueue
input = sys.stdin.readline
INlist = lambda: list(map(int,input().split()))
n,m,o = INlist()
cgd = [] # 采购点
for i in range(n):
    cgd.append(INlist())
class Node():
    def __init__(self,buy,cost):
        self.buy = buy
        self.cost = cost
    def __lt__(self,other):# 花费高的在前面,优先出队
        return self.cost > other.cost 

pq = PriorityQueue()

buy_cnt = 0 #买了几件物品了
cost_cnt = 0 # 购买花费了多少
ans = float('inf') # 总花费
for i in range(n):
    pq.put(Node(cgd[i][1],cgd[i][0]))# 全买下来
    buy_cnt += cgd[i][1]
    cost_cnt += cgd[i][0] * cgd[i][1]
    if(buy_cnt > m):
        while(buy_cnt > m):
            node = pq.get()
            t = min(node.buy,buy_cnt - m)
            buy_cnt -= t
            cost_cnt -= node.cost * t
            node.buy -= t
            if(node.buy > 0) : # 还有剩余,还要购买
                pq.put(node)
        ans = min(ans,cost_cnt+o*cgd[i][2]) # 总花费=商品花费+路程花费

print(ans)