突击蓝桥杯

现在是2023.3.31号，还有8天就要蓝桥杯比赛了，初次打这种算法比赛，发给帖子做一下最近准备的全面总结。全部是围绕python语言实现的。

2023.4.4更新

目录

输入和输出

有关数论的题目

[蓝桥杯 2015 省 A] 饮料换购

[蓝桥杯 2021 省 AB2] 完全平方数

[蓝桥杯 2019 省 B] 等差数列

[蓝桥杯 2017 省 B] k 倍区间

[蓝桥杯 2022 省 A] 数的拆分

[蓝桥杯2022初赛] 质因数个数

[蓝桥杯2022初赛] 寻找整数

有关模拟的题目

[蓝桥杯 2020 省 AB1] 解码

 [蓝桥杯2021初赛] 卡片

[蓝桥杯 2021 省 AB2] 负载均衡

贪心算法的题目 

堆——heapq

栈/队列——list

排序——sort

[蓝桥杯2022初赛] 技能升级

[蓝桥杯2022初赛] 最优清零方案

有关动态规划的算法

[蓝桥杯2022初赛] 全排列的价值

[蓝桥杯 2016 省 A] 密码脱落

 [蓝桥杯 2021 省 AB] 砝码称重

[蓝桥杯 2014 省 A] 波动数列

有关图论的算法

[蓝桥杯 2013 省 A] 剪格子

 [蓝桥杯 2018 省 AB] 全球变暖

 [蓝桥杯2021初赛] 路径

[蓝桥杯2021初赛] 回路计数

输入和输出

首先是输入，蓝桥杯主要输入有几种：

1.输入列表，这是最常用的

2.输入单个数字，或者几个数字

3.字符串

一般来说我是这么实现的

# 输入列表
arr = [int(i) for i in input().split(" ")]# 几个数字
m,n = map(int,input().split(" "))# 字符串
str = input()

 都是基础知识，下面开讲输出

一般来说，输出有以下几种情况

1.输出单个结果

2.输出指定行数，每行包含一个结果

3.字符串

输出不赘述了，基本print搞定全部，可以要注意输出数字的格式，我一般就用%实现

pi = 3.1415926
print('pi=%.2f'%(pi))

 在练习的过程中，发现一个事实，一次性input完，再output会节省大量时间（大佬不要骂

有关数论的题目

蓝桥杯有不少关于数论知识的题目，我把刷到的都列举出来，过于简单的和利用暴搜填空的我就不给了。（从简单到难

[蓝桥杯 2015 省 A] 饮料换购

题目链接：P8627 [蓝桥杯 2015 省 A] 饮料换购 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

简单的，主要就是利用模和整除的性质，在python要特别注意/和//的区别，我吃了几次亏了，python没有数据类型定义，一不小心就整数和浮点数转换了。

AC代码如下：

n = int(input())
res = n
while n>=3:res += n//3n = n%3 + n//3
print(res)

[蓝桥杯 2021 省 AB2] 完全平方数

题目链接：P8754 [蓝桥杯 2021 省 AB2] 完全平方数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 

涉及到了唯一分解定律，插一嘴，后面好多地方都会用到，下面进行简要说明：

简单来说就是对于任意一个数 n，它都可以分解为若干个质数的乘积。 比如 60 就可以分解为 2**2×3×5。

解决这个题目，首先要求解质因数和其指数，下面为改编自洛谷题解的质因数模板，非常感谢这位朋友，博客主页：文章列表 - pxb0801 的博客 - 洛谷博客 (luogu.com.cn)

# 质因数分解模板,p为质因数，g为指数
def factor(n:int,p:list,g:list):pivot = -1for i in range(2,int(n**0.5+2)):if n%i==0:pivot += 1while n%i==0:p[pivot] = ig[pivot] += 1n = n//iif n>1:pivot += 1p[pivot] = ng[pivot] += 1

完整代码如下，可AC：

# 质因数分解模板,p为质因数，g为指数
def factor(n:int,p:list,g:list):pivot = -1for i in range(2,int(n**0.5+2)):if n%i==0:pivot += 1while n%i==0:p[pivot] = ig[pivot] += 1n = n//iif n>1:pivot += 1p[pivot] = ng[pivot] += 1if __name__ == '__main__':n = int(input())p = [0]*1000g = [0]*1000factor(n,p,g)res = 1for i in range(len(g)):if g[i]%2!=0:res*=p[i]print(res)

不再解释，可以好好想想主函数在干嘛，不行看一看题目链接里面的题解。

[蓝桥杯 2019 省 B] 等差数列

题目链接：P8682 [蓝桥杯 2019 省 B] 等差数列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

该题目核心思想就是求最小公约数，同时注意d=0的情况。代码如下，可AC：

from math import gcd
n = int(input())
if n<=1:print(n)
else:arr = [int(i) for i in input().split(" ")]arr.sort()d = arr[1]-arr[0]for i in range(1,n):d = gcd(arr[i]-arr[i-1],d)if d==0:print(n)else:print(arr[-1]//d-arr[0]//d+1)

利用了math库函数里面的gcd函数和sort。

[蓝桥杯 2017 省 B] k 倍区间

题目链接：P8754 [蓝桥杯 2021 省 AB2] 完全平方数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

相信大部分人和我思路差不多，直接暴力枚举，从i从1-n，j从1-i。时间复杂度为n^2。

如果学过前缀和，直接拿前缀和，时间复杂度还是n^2，不过系数等有所降低。

但是上面两个方法都不行，需要用到前缀和+同余定理（又是一个一说有点印象，但完全不会用到的数论小知识

同余定理就不解释了，具体搜一下吧，直接给代码了

n,k = map(int,list(input().split(" ")))
arr = []
sm = [0]*n
num = [0]*kfor i in range(n):arr.append(int(input()))sm[0] = arr[0]%k
num[sm[0]] += 1
for i in range(1,n):sm[i] = (sm[i-1]+arr[i])%k # 类似前缀和，运用了前缀和num[sm[i]] +=1 # 统计次数count = 0
for i in num:count += (i*(i-1))//2 # 利用组合知识
count += num[0] # 加上每个mod==0的
print(count)

[蓝桥杯 2022 省 A] 数的拆分

题目链接：P8778 [蓝桥杯 2022 省 A] 数的拆分 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

套质因数分解模板，然后遍历分析即可。

跑不出来，太难了，放弃了

[蓝桥杯2022初赛] 质因数个数

题目链接：P2055 - [蓝桥杯2022初赛] 质因数个数 - New Online Judge (ecustacm.cn)

可以利用质因数分解模板，轻轻松松拿到70%

代码如下：

n = int(input())
res = 0
for i in range(2,int(n**0.5+2)):if n%i==0:res+=1while n%i==0:n = n//i
if n>1:res+=1
print(res)

[蓝桥杯2022初赛] 寻找整数

题目链接：P2049 - [蓝桥杯2022初赛] 寻找整数 - New Online Judge (ecustacm.cn)

运用到了中国剩余定理，之前我写过一篇blog总结

blog链接： (93条消息) [蓝桥杯2022初赛] 寻找整数_YiYo832的博客-CSDN博客

关于数论的题目就写了这么多，总结一下，主要有整除，模，最大公约数，同余定理，质因数分解，中国剩余定理。

有关模拟的题目

前言：其实蓝桥杯关于模拟的题目单独考察都是很简单的，涉及到其他算法才变得难，我简单地举一两个例子感受一下，知道模拟是干什么就好了。

[蓝桥杯 2020 省 AB1] 解码

题目链接：P8706 [蓝桥杯 2020 省 AB1] 解码 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

代码如下：

arr = list(input())
c = ''
res = []
for i in arr:if 'A'<=i<='Z' or 'a'<=i<='z':res.append(i)c = ielif '0'<=i<='9':for j in range(int(i)-1):res.append(c)
print("".join(res))

 [蓝桥杯2021初赛] 卡片

题目链接：P1550 - [蓝桥杯2021初赛] 卡片 - New Online Judge (ecustacm.cn)

不给题解了，简单的

[蓝桥杯 2021 省 AB2] 负载均衡

题目链接：​​​​​​tP8755 [蓝桥杯 2021 省 AB2] 负载均衡 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

 纯靠模拟就可以做出来了，主要就是利用sort函数

n,m = map(int,input().split(" "))
v = [int(i) for i in input().split(" ")]
r = [[] for i in range(n)]
res = []
ipt = [input() for i in range(m)]
for i in ipt:a,b,c,d = map(int,i.split(" "))pivot = b-1flag = True
# 释放空间while flag:if r[pivot]==[]:flag = Falsecontinueelse:t,tt = r[pivot].pop()if t<=a:v[pivot]+=ttelse:r[pivot].append((t,tt))flag = False
# 判断是否能加入if v[pivot]>=d:v[pivot]-=dr[pivot].append((a+c,d))r[pivot].sort(reverse=True)res.append(v[pivot])else:res.append(-1)
# 输出结果
for i in range(m):print(res[i])

贪心算法的题目 

一提到贪心一定离不开最小值或者最大值，一般来说用的多的有二分寻找，最小堆，最大堆，栈这些基本数据结构。

所以在开始讲解题目前，先把python中有关的库函数讲一下，便于后面操作。

堆——heapq

python有自带的实现最小堆的库函数，就是heapq。

关于堆的知识不赘述，heapq的方法可以看看我之前的blog

链接：(93条消息) 【蓝桥杯 路径 python】Dij算法_YiYo832的博客-CSDN博客

我简单地讲述以下：

1.heapq.heappop(heap)

2.heapq.heappush(heap,item)

3.heapq.heapify(heap) 

最大堆只需要在最小堆的基础上对item稍作改变就可以实现了的，比如加个负号，具体实现看题目。

栈/队列——list

栈的实现在python中非常easy，随便一个数组就好了

# 栈
stack = []
stack.append(item)
stack.pop()# 队列
deque = []
deque.append(item)
deque.pop(0)

 具体题目考虑空列表就好了

排序——sort

arr = []
arr.sort()# 反转靠切片
arr2 = arr[::-1]

[蓝桥杯2022初赛] 技能升级

题目链接：P2047 - [蓝桥杯2022初赛] 技能升级 - New Online Judge (ecustacm.cn)

利用贪心算法和python自带的heapq库函数

虽然没有AC，但是也有50%，而且思路简单，实现也简单，感觉还是很好的一个解法。

代码如下：

import heapq
n,m = map(int,list(input().split()))
arr = []
for i in range(n):a,b = map(int,list(input().split()))arr.append((-a,b))
res = 0
heapq.heapify(arr)
for i in range(m):if arr == []:breaka,b = heapq.heappop(arr)a = -ares += aif a-b<=0 or a==0:continueelse:a = a-bheapq.heappush(arr,(-a,b))
print(res)

[蓝桥杯2022初赛] 最优清零方案

题目链接：P2054 - [蓝桥杯2022初赛] 最优清零方案 - New Online Judge (ecustacm.cn)

贪心算法，以k间距为窗口寻找最小值，然后减去，再处理单个的。

代码如下：

N,k = map(int,input().split())
nums = list(map(int,input().split()))count = 0flag = Truewhile flag:flag = False# 循环遍历 有无连续k个数减一i = 0while i < N - k + 1:k_list = nums[i:i + k]# 有0 不可减if 0 in k_list:ind = (k - 1) - k_list[::-1].index(0)  # 最后一个0的位置i = i + ind + 1  # 下次直接从0的后一个位置开始找continue# 无0 连续k个数可减一min_num = min(k_list)flag = Truefor t in range(k):nums[i + t] -= min_num  # 直接一次性减完 减到0count += min_numi += 1count += sum(nums)  # 无需做减一操作 直接求和就是print(count)

或者

N,k = map(int,input().split())
nums = list(map(int,input().split()))count = 0
flag = Truewhile flag:flag = False# 循环遍历 有无连续k个数减一i = 0while i < N - k + 1:k_list = nums[i:i + k]mini = min(k_list)ind = k_list.index(mini)if mini == 0:i = i+ind+1continueflag = Truefor t in range(k):nums[i + t] -= mini  # 直接一次性减完 减到0count += minii += 1count += sum(nums)  # 无需做减一操作 直接求和就是print(count)

有关动态规划的算法

动态规划我也是刚入门，门槛都跨不过去的小白，因此刷到的题目，有些都写不出来，真能写写简单的dp。

动态规划的核心我觉得是找转移方程，明确各个变量下标的意义。

[蓝桥杯2022初赛] 全排列的价值

题目链接：P2052 - [蓝桥杯2022初赛] 全排列的价值 - New Online Judge (ecustacm.cn)

 dp[i]表示第i个数字加入后的价值。转移方程如下：

dp[i] = dp[i-1]*i + i*(i-1)/2*(i-1)!

一维dp而且只有前后两项有关联，可以压缩成单个变量的迭代。

代码如下（70%）：

n = int(input())
res = 0
tem = 1
for i in range(2,n+1):res = res*i + int((i*i-i)/2)*temtem *= i
print(int(res%998244353))

 注意：由于数字过大，后续计算量过大，可以进行优化，主要是运用同余定理。

代码如下（AC）：

n = int(input())
res = 0
tem = 1
for i in range(2,n+1):res = res*i + i*(i-1)//2*temres = res%998244353tem *= item = tem%998244353
print(res)

[蓝桥杯 2016 省 A] 密码脱落

题目链接：P8638 [蓝桥杯 2016 省 A] 密码脱落 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目可以转化为求字符串与其反转字符串的最大不连续子字符串问题。

运用动态规划

dp[i][j]表示第1个字符串的前i个与第2个字符串的前j个最大子字符串个数。

转移方程为：

if a[i]==b[j]:

        dp[i][j] = dp[i-1][j-1]+1

else:

       dp[i][j] = max(dp[i-1][j],dp[i][j-1])

比较好理解，可以画以下就明白了

代码如下（AC）：

arr = [i for i in input()]
arr2 = arr[::-1]
n = len(arr)
#print(arr,arr2)
dp = [[0]*(n+1) for i in range(n+1)]
for i in range(1,n+1):for j in range(1,n+1):if arr[i-1] == arr2[j-1]:dp[i][j] = dp[i-1][j-1]+1else:dp[i][j] = max(dp[i-1][j],dp[i][j-1])print(n-dp[n][n])

 [蓝桥杯 2021 省 AB] 砝码称重

题目链接：P8742 [蓝桥杯 2021 省 AB] 砝码称重 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

 也是比较简单的dp

转移方程不打了，直接看代码吧

分数在70-80，满分的代码还没想出来：

n = int(input())
arr = [int(i) for i in input().split(" ")]
res = set()
tem = set()for i in arr:tem.add(i)for j in res:tem.add(i+j)tem.add(abs(i-j))res = set(tem)if 0 in res:print(len(res)-1)
else:print(len(res))

[蓝桥杯 2014 省 A] 波动数列

题目链接：P8614 [蓝桥杯 2014 省 A] 波动数列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这个我真不会，看题解的，学了挺久的，感谢

RoMantic_Queue 的个人中心 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

提供的题解，下面为python代码：

n,s,a,b = map(int,input().split(" "))
dp = [[0]*n for i in range(n)]
dp[0][0] = 1
for i in range(1,n):for j in range(n):dp[i][j] = (dp[i-1][((j-i*a)%n+n)%n]+dp[i-1][((j+i*b)%n)%n])%100000007
print(dp[n-1][(s%n+n)%n])

有关图论的算法

我刷到的题目，主要涉及深搜，广搜，Dij算法，剩余有难度的还没开始学，嘿嘿

[蓝桥杯 2013 省 A] 剪格子

题目来源：P8601 [蓝桥杯 2013 省 A] 剪格子 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

先看数据量，发现不大，可以使用 暴力搜索（深搜）

主要点我觉得是判断是否访问过。

代码如下（67%）：

import sys
sys.setrecursionlimit(999999)
m,n = map(int,input().split(" "))
arr = [ list( int(j) for j in input().split(" ")) for i in range(n)]
visit = [[0]*m for i in range(n)] # 0表示没访问过，1表示访问过ans = 0
for sub in arr:ans += sum(sub)
ans = ans//2count = []
cot = 0
sum = 0def f(i,j,sum,cot):# 先判断特殊情况if i>=n or j>=m or i<0 or j<0:return# 再判断是否访问if visit[i][j]:returnsum += arr[i][j]cot += 1if sum == ans:count.append(cot)returnif sum>ans:returnvisit[i][j] = 1# 上下左右搜索f(i+1,j,sum,cot)f(i,j+1,sum,cot)f(i,j-1,sum,cot)f(i-1,j,sum,cot)visit[i][j] = 0f(0,0,sum,cot)
if count:print(min(count))
else:print(0)

注意：python对于递归深度有限制，可以使用sys库函数改变

 [蓝桥杯 2018 省 AB] 全球变暖

 题目链接：P8662 [蓝桥杯 2018 省 AB] 全球变暖 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

一开始，我的思想如下：

判断有多少个孤岛

然后进行“淹没”

在判断有多少个孤岛

前者减去后者 

这个想法是错误的，具体读者可以自己想一想

准确方法是广度搜索，进行“是否完全被淹没”表示

代码如下（AC）：

n = int(input())
arr = [input() for i in range(n)]
visit = [[0]*n for i in range(n)]
ans = 0
hp = [(0,1),(0,-1),(1,0),(-1,0)] # 辅助数组def bfs(i,j):global flag # 判断是否被完全淹没visit[i][j] = 1deque = [(i,j)]while deque:x,y = deque.pop()if arr[x][y+1]=='#' and arr[x+1][y]=='#' and arr[x][y-1]=='#' and arr[x-1][y]=='#':flag = 1 # 四周都有岛屿则不被淹没for k in range(4):sx = x+hp[k][0]sy = y+hp[k][1]if visit[sx][sy]==0 and arr[sx][sy]=='#':deque.append((sx,sy))visit[sx][sy] = 1 # 把所有连起来的岛屿都标记为1for i in range(n):for j in range(n):if arr[i][j]=='#'and visit[i][j]==0:flag = 0bfs(i,j)if flag == 0:ans += 1 # 进行统计
print(ans) 

利用了deque数组作为队列进行广度搜索。 

 [蓝桥杯2021初赛] 路径

题目链接：P1553 - [蓝桥杯2021初赛] 路径 - New Online Judge (ecustacm.cn)

 这个是典型的Dij算法

模板如下：

import heapq
MAX = 99999999
def Dij(arr,start):n = len(arr)dis = [MAX]*nvis = [0]*nheap = []# 初始化dis[start] = 0vis[start] = 1for i in range(n):if arr[start][i]!=MAX:dis[i] = arr[start][i]heapq.heappush(heap,(dis[i],i))while heap:pre,pivot = heapq.heappop(heap)if vis[pivot]:continuevis[pivot] = 1for i in range(n):now = pre+arr[pivot][i] # 松弛if dis[i]>now:dis[i]=nowheapq.heappush(heap,(dis[i],i))return dis

模板是自己打的，可读性会差一点

然后算出路径就好了

def f(x,y):if x==y:#当到自身是路径为0return 0x,y = max(x,y),min(x,y)add = xwhile True:if x%y==0:return xelse:x += addarr = []
for i in range(1,2022):tem = []if i<=22:for j in range(1,i+22):tem.append(f(j,i))tem = tem + [9999999999]*(2021-len(tem))elif i>=2000:for j in range(i-21,2022):tem.append(f(j,i))tem = [9999999999]*(2021-len(tem)) + temelse:for j in range(i-21,i+22):tem.append(f(j,i))tem = [9999999999]*(i-22) + tem + [9999999999]*(2021-i-21)arr.append(tem)
print("over!arr")
print(len(arr))
res = Dij(arr,0)
print(res[2020])

 答案与网上对比准确，填空题无所谓时间复杂度，能跑出来就行。

下面是利用floyd算法实现的：

from math import gcdn = 2021
dp = [float('inf')] * (n + 1)
dp[1] = 0
for i in range(1, n + 1):for j in range(1, 22):if i + j > n:breakdp[i + j] = min(dp[i + j], dp[i] + i*(i+j)//gcd(i, i + j))
print(dp[n])

[蓝桥杯2021初赛] 回路计数

题目链接：P1554 - [蓝桥杯2021初赛] 回路计数 - New Online Judge (ecustacm.cn)

好难，不会emmm

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！