2025蓝桥杯python A组省赛 题解

真捐款去了，好长时间没练了，感觉脑子和手都不转悠了。$BF$ 赛时都写假了，$G$ 也只写了爆搜。

题解其实队友都写好了，我就粘一下自己的代码，稍微提点个人的理解水一篇题解

队友题解

2025蓝桥杯C++ A组省赛 题解

注：所有代码均已通过洛谷数据（除了 $F$ 题爆搜，有三个点 $TLE$，这个洛谷时限只有一秒，但是赛时是十秒），但是民间数据较弱，不排除会有 $bug$。

---

B

思路：

我是直接枚举八个段是否填 $0$，确定哪些段填 $0$ 后，缩写形式也就唯一确定了。接下来我们只需要确定填非 $0$ 的段的长度和可能数。

确定填 $0$ 段和冒号的长度重点在于确定缩写的位置，无外乎三种情况：

1. 开头或结尾的连续 $0$ 段缩写
2. 中间的连续 $0$ 段缩写
3. 不缩写（其实只要缩写就一定不差于不缩写）

假设总共有 $n$ 段（其实就是 $8$），总共有 $num0$ 个 $0$，开头或结尾的最长连续 $0$ 段长度为 $ans1$，中间的最长连续 $0$ 段长度为 $ans2$，那么三种情况的答案分别是：

1. 除缩写部分的剩余部分长度为 $n-ans1$，需要 $n-ans1-1$ 个冒号分割。缩写需要 $2$ 个冒号。剩余未被缩写的 $0$ 的个数为 $num0-ans1$，因此总长度为 $(n-ans1-1)+2+(num0-ans1)$
2. 除缩写部分的剩余部分总长度为 $n-ans2$，需要 $n-ans2-2$ 个冒号分割（因为是左右两个部分）。缩写需要 $2$ 个冒号。剩余未被缩写的 $0$ 的个数为 $num0-ans2$，因此总长度为 $(n-ans2-2)+2+(num0-ans2)$
3. $n-1+num0$

非零段长度变化时，以外的部分（填 $0$ 段和冒号）的长度是不变的，假设这个填 $0$ 段和冒号总长度是 $len$。接下来需要确定非 $0$ 的段的所有情况的总长度，这个部分我们直接爆搜，假设有 $pos$ 个非零段，每个段分别有 $16^1-16^0=15,16^2-16^1=240,16^3-16^2=3840,16^4-16^3=61440$ 种情况，长度分别为 $1,2,3,4$，这样爆搜的次数是 $4^{pos}\le 4^8=65536$ 次，可以跑得动。

另外因为全 $0$ 段的时候比较特殊，所以单独计数。

code：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;int get_len(string s){//得到简化后的冒号和0位置的总长度 int n=s.length();int ans1=0,ans2=0,num0=0;for(int i=0;i<n;i++)if(s[i]=='0')num0++;for(int i=0;i<n;i++)if(s[i]!='0'){ans1=max(ans1,i);break;}for(int i=n-1;i>=0;i--)if(s[i]!='0'){ans1=max(ans1,n-i-1);break;}for(int l=1,r=0;l<n-1;l=r+1){r++;while(s[r]=='0' && r<n-1)r++;ans2=max(ans2,r-l);}
//	cout<<ans1<<" "<<ans2<<" "<<num0<<endl;return min(min(n-ans1-1+2+(num0-ans1),n-ans2-2+2+(num0-ans2)),n-1+num0);
}ll tm[]={15,240,3840,61440};
ll len;//某种选取情况的长度 
vector<ll> take;//某种选取情况 
ll tot;//所有情况的总长度 
void dfs(int pos){if(pos<=0){ll t=1;for(auto x:take)t=t*x%mod;//这种选取情况下的情况数 tot=(tot+t*len%mod)%mod;return;}for(int i=0;i<4;i++){len+=i+1;take.push_back(tm[i]);dfs(pos-1);take.pop_back();len-=i+1;}
}signed main(){ll ans=2; for(int i=1;i<(1<<8);i++){string s;for(int j=0;j<8;j++)s += "01"[(i>>j)&1];len=get_len(s);int num1=0;for(int i=0;i<s.length();i++)if(s[i]=='1')num1++;dfs(num1);ans=(ans+tot)%mod;tot=0;
//		cout<<s<<" "<<get_len(s)<<" "<<num1<<" "<<tot<<endl;
//		cout<<ans<<endl;}cout<<ans;return 0;
} 

---

C

code：

import sys
input = sys.stdin.readlineh, w = map(int, input().split())
s = "2025" * 1145
for i in range(h):print(s[i:i+w])

---

D

思路：

$python$ 的 $sort$ 只能指定按照某个位置的值进行排序，不能对两个数做操作来确定大小。

为了解决这个问题可以用 functools 的 cmp_to_key，或者重写类的 __lt__ 方法。

因为这个答案可能会很大，所以可能需要手动调大 int 的存储位数。

code：

from functools import cmp_to_key
import syssys.set_int_max_str_digits(1000000)n = int(input())
s = [bin(x)[2:] for x in range(1, n+1)]def cmp(a: str, b: str)-> int:if a+b < b+a:return -1elif a+b == b+a:return 0else:return 1s.sort(key=cmp_to_key(cmp), reverse=True)
print(int("".join(s), 2))

---

E

思路：

队友写假了，这个水是不能往前面的位置倒的，所以就不能求平均数了。

这个题正解是二分答案，很板。

大体思路就是二分答案，对一个需要验证的答案，如果一个位置的水量高于答案，就把多余的部分都给后面。如果这个位置水量不够答案，就说明通过前面的努力是不够填满它的，这个答案就不成立。

如果不会写整数二分，可以在 $l,r$ 范围缩到足够小时，对小范围进行暴力枚举验证。

code：

import copy
import sys
input = sys.stdin.readline
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))def check(height):t = copy.deepcopy(a)for i in range(n):if t[i] < height:return Falseif i + k < n:t[i + k] += t[i] - heightreturn Truel, r = 1, 10**20
while l < r:mid = (l + r + 1) // 2if check(mid):l = midelse:r = mid - 1print(l)"""
8 3
5 6 4 8 3 4 1 9"""

---

F

思路：

赛时写完发现想假了，不过没时间了就直接交了。思路和队友是一样的，直接看他的讲解吧。

这题 $n=1000$ 还能暴力啊……

不怎么会写暴搜，暴力杯吃大亏。

code：

n = int(input())
cnt = [0]*7
for x in input().split():cnt[min(6, x.count("6"))] += 1# n = 1000
# cnt = [200 for _ in range(7)]visit = dict()
ans, cur = 0, 0def dfs(status):# status状态下的最大值global ans, curif len(tuple(x for x in status if x < 0)) > 0:returnif visit.get(tuple(status)):return visit.get(tuple(status))if sum(status) // 2 + cur <= ans:returnif sum([i*x for i, x in enumerate(status, start=1)]) // 6 + cur <= ans:return# print(status)ans = max(ans, cur)for i in range(1, 6):for j in range(max(6-i, i), 6):status[i - 1] -= 1status[j - 1] -= 1cur += 1dfs(status)cur -= 1status[i - 1] += 1status[j - 1] += 1for i in range(1, 6):for j in range(i, 6):for k in range(max(6-i-j, j), 6):status[i - 1] -= 1status[j - 1] -= 1status[k - 1] -= 1cur += 1dfs(status)cur -= 1status[i - 1] += 1status[j - 1] += 1status[k - 1] += 1visit[tuple(status)] = curdfs(cnt[1:6])print(ans + cnt[6])"""
8
666666 666 666 666 66 6 6 6"""

---

G

思路：

队友说是染色，其实就是并查集合并连通块，并额外处理一个连通块内所有点的最大高度（因为一个连通块内是互相可达的）

假设我们处理前面一段高度，得到了若干组，你会发现这些组的值域互不覆盖，且位置越靠后，值越大。

当我们加入一个更高高度的点时（比前面所有高度都高），因为不能到达前面任何一个点，它就会成为新的组。

当我们加入一个低于前面若干高度的点时，它就会和前面所有存在高于它的点的组进行合并，成为一个组。

发现我们其实只需要知道每个组的最大高度就可以了，所以我们可以用单调栈来维护每个组的最大值，并从顶到底按照从大到小的顺序放好。

之后每一行跑一遍，每一列跑一遍就好了。

code：

原代码的下标映射有些混乱，所以改成了从 $(0,0)$ 到 $(n-1,m-1)$

n, m = map(int, input().split())mp = [[0] * m for _ in range(n)]
for i in range(n):mp[i][:] = map(int, input().split())f = [0] * (n*m)
maxh = [0] * (n*m)
for i in range(n*m):f[i] = imaxh[i] = mp[i // m][i % m]def to_idx(x, y):return x*m+ydef findf(x):if f[x] == x:return xelse: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] = fufor i in range(n):stack = list()  # 高度 并查集位置for j in range(m):idx = to_idx(i, j)maxx = mp[i][j]while stack and stack[-1][0] > mp[i][j]:maxx = max(maxx, stack[-1][0])merge(stack[-1][1], idx)stack.pop()stack.append((maxx, idx))for j in range(m):stack = list()  # 高度 并查集位置for i in range(n):idx = to_idx(i, j)maxx = mp[i][j]while stack and stack[-1][0] > mp[i][j]:maxx = max(maxx, stack[-1][0])merge(stack[-1][1], idx)stack.pop()stack.append((maxx, idx))ans = 0
for i in range(n):for j in range(m):fa = findf(to_idx(i, j))ans += maxh[fa]print("{:.6f}".format(ans/(n*m)))"""
2 2
1 4
4 32 3
2 4 1
4 2 3"""

---

H

思路：

感觉 $H<F<G$，这题是个标准的反悔贪心。

优先队列还是前一天晚上临时看的。

感觉没什么好写的，就丢个类似的题吧 你是银狼