蓝桥杯第19天（Python）（疯狂刷题第2天）

题型：

1.思维题/杂题：数学公式，分析题意，找规律

2.BFS/DFS：广搜（递归实现），深搜（deque实现）

3.简单数论：模，素数（只需要判断到 int（sqrt（n））+1），gcd，lcm，快速幂（位运算移位操作），大数分解（分解为质数的乘积）

4.简单图论：最短路（一对多（Dijstra，临接表，矩阵实现），多对多（Floyd，矩阵实现）），最小生成树（并查集实现）

5.简单字符串处理：最好转为列表操作

6.DP：线性DP，最长公共子序列，0/1背包问题，最长连续字符串，最大递增子串

7.基本算法：二分，贪心，组合，排列，前缀和，差分

8.基本数据结构：队列，集合，字典，字符串，列表，栈，树

9.常用模块：math，datetime，sys中的设置最大递归深度（sys.setrecursionlimit(3000000)），collections.deque（队列），itertools.combinations（list,n）（组合），itertools.permutations（list,n）（排列）  heapq（小顶堆）

目录

1.一元三次方程求解（二分，格式化输出）

2.解立方根（二分）

3.分巧克力（二分，注意二分的两个模板）

4.翻硬币（贪心）

5.巧克力（贪心） 

6.顺子日期（思维题，细心，手数）

7.乘积尾零（大数运算或者大数分解）

8. 平方和 （字符串运算）

9.快乐司机（贪心）

10.蓝肽子序列（DP，最长公共子序列）

11.合唱队形（最长递增子序列）

12.字符串编辑距离（DP，经典问题DP）

13.小明的背包1（经典0/1背包问题DP）

14.最长公共子序列（模板题）

15.最长连续递增子序列（DP模板）

---

1.一元三次方程求解（二分，格式化输出）

import sys  #设置递归深度
import collections  #队列
import itertools  # 排列组合
import heapq  #小顶堆
import math
sys.setrecursionlimit(300000)a,b,c,d = map(float,input().split())
def f(x):return x*x*x*a+x*x*b+x*c+dans=[]
for i in range(-100,100):if f(i)==0:ans.append(i)if f(i)*f(i+1)<0:  # 在（i，i+1）内有根l=i;r=i+1while(r-l>=0.001):  # 保留精度,2位小数,注意循环条件mid=(l+r)/2if f(l)*f(mid)<0:r=midelse:l=midans.append(l)
if f(100)==0:ans.append(100)
for i in ans:print("{:.2f}".format(i),end=' ')

算是送分题，主要考查了二分法的使用，同时边界处理，即不要漏掉区间范围，注意格式化输出语句。

2.解立方根（二分）

import sys  #设置递归深度
import collections  #队列
import itertools  # 排列组合
import heapq  #小顶堆
import math
sys.setrecursionlimit(300000)T=int(input())
for i in range(T):n=int(input())for i in range(100000):if i**3==n:   # 优先判定是否相等，结果为整数print('{:.3f}'.format(i))breakelif i**3>n:  # 最后的结果为小数，通过二分处理left=i-1;right=i;while(right-left>0.00001):mid=(left+right)/2if(mid**3>n):right=midelse:left=midprint('{:.3f}'.format(l))break

送饭送分，实数二分题不需要考虑边界加一减一问题，对于精度问题用一个while语句就可以了，例如保留两位小数，那么语句为 while ( right - left) >= 0.001 

3.分巧克力（二分，注意二分的两个模板）

import sys  #设置递归深度
import collections  #队列
import itertools  # 排列组合
import heapq  #小顶堆
import math
sys.setrecursionlimit(300000)n,k = map(int,input().split())
save = [] #存放巧克力
Max=1
for i in range(n):temp=list(map(int,input().split()))Max=max(max(temp),Max)  # 记录大巧克力边长，之后用于二分save.append(temp)def check(i):count=0for a,b in save:count+=(a//i)*(b//i)if count>=k:return Trueelse:return False
left=1
right=Max
while(left<right):  # 找<=x的第一个mid=(left+right+1)//2#print(left,mid,right)#print('-'*40)if check(mid):left=midelse:right=mid-1
print(left)
#print(right)
#print(mid)'''
2 10
6 5
5 6
测试结果
1 4 6
----------------------------------------
1 2 3
----------------------------------------
2 3 3
----------------------------------------
2
2
3'''

这里不是实数二分，需要将题目转为二分题来进行解决，注意两个二分模板的不同使用情况，当找的是<=x的第一个时，需要令mid=（left+right+1）//2，找>=x的第一个，mid=（right+left）//2。

两个二分模板

找>=x的第一个，mid=（low+high）//2

a=[0,3,5,7,9,11,13]
# [0,1,2,3,4,5,6]
# low = 0 high =6 mid =3  ----->   low=4  high =6
# low = 4 high =6 mid =5  ----->   low=4  high =5
# low = 4 high =5 mid =4  ----->   low=5  high =5
# break   low=high=5
# 找的是靠右的那一个
low=0
high=len(a)-1
def search(low,high,x):  # 查找的是后一个while (low<high):mid =(low+high)//2   # (2+3)//2=2  偏左if (a[mid]>=x):high=midelse:low=mid+1print(a[low])print(a[high])
search(low,high,10)  # 查找结果10

找<=x的第一个，mid=（low+high+1）//2 

a=[0,3,5,7,9,11,13]
# [0,1,2,3,4,5,6]
# low = 0 high =6 mid =3  ----->   low=3  high =6
# low = 3 high =6 mid =5  ----->   low=3  high =4
# low = 3 high =4 mid =4  ----->   low=4  high =4
# break   low=high=4
# 找的是靠左的那一个
low=0
high=len(a)-1
def search(low,high,x):  # 查找的是前一个while (low<high):mid =(low+high+1)//2   # (2+3+1)//2=3  偏右if (a[mid]<=x):low=midelse:high=mid-1print(a[low])print(a[high])
search(low,high,10)  # 查找结果10

4.翻硬币（贪心）

 

s = input()
t = input()
cnt = 0
for i in range(len(s) - 1):if s[i] != t[i]:if s[i + 1] == '*':s = s[:i + 1] + 'o' + s[i + 2:]else:s = s[:i + 1] + '*' + s[i + 2:]cnt += 1
print(cnt)

重点在于怎么想到这是贪心题，靠运气，想不出来就按着贪心做，暴力循环

5.巧克力（贪心） 

import sys  #设置递归深度
import collections  #队列
import itertools  # 排列组合
import heapq  #小顶堆
import math
sys.setrecursionlimit(300000)x,n=map(int,input().split())  # 天数，巧克力种类数
#day=[0]*(x+1)  #记录吃什么
thing =[]
for i in range(1,n+1):  # 存储商品thing.append(list(map(int,input().split())))
ans=0
thing.sort(key=lambda x:x[0] )  # 按单价从小到大排序
thing=[0]+thing  # 转为下标从一开始# 开始分配每天的食物    thing-》 [单价，保质期，数量]
for i in range(1,x+1): # 遍历天数for j in range(1,n+1):  # 遍历货物if thing[j][1]>=i and thing[j][2]>0:  # 没过保质期且还有剩余#print(j)#day[i]=j    ans+=thing[j][0]  # 第i天选第j类食物thing[j][2]-=1  # 用了一个需要减一break
if ans==0:print(-1)
else:print(ans)# 没有用到记录数组，直接遍历的过程中就可以算出答案然后进行输出

中档题目难度吧，感觉就是贪心想法，然后按照题目要求来做就行了，注意便于处理，可以转换下标，即从1开始处理，下标从1开始，有时候需要记录数组，有时候不需要，需要在代码编写过程中自己注意。

6.顺子日期（思维题，细心，手数）

 

 手数，枚举所有可能情况就可以了，注意细心，不要急，将所有情况统计完，算是送分题，主要是读懂题意

7.乘积尾零（大数运算或者大数分解）

import sys  #设置递归深度
import collections  #队列
import itertools  # 排列组合
import heapq  #小顶堆
import math
sys.setrecursionlimit(300000)# 因为只有2,5有用，所以只记录2和5的数量
count1=0
count2=0s="""5650 4542 3554 473 946 4114 3871 9073 90 4329 
2758 7949 6113 5659 5245 7432 3051 4434 6704 3594 
9937 1173 6866 3397 4759 7557 3070 2287 1453 9899 
1486 5722 3135 1170 4014 5510 5120 729 2880 9019 
2049 698 4582 4346 4427 646 9742 7340 1230 7683 
5693 7015 6887 7381 4172 4341 2909 2027 7355 5649 
6701 6645 1671 5978 2704 9926 295 3125 3878 6785 
2066 4247 4800 1578 6652 4616 1113 6205 3264 2915 
3966 5291 2904 1285 2193 1428 2265 8730 9436 7074 
689 5510 8243 6114 337 4096 8199 7313 3685 211"""
save=list(map(int,s.split()))
#print(save)
for i in save:while i%2==0:count1+=1i=i//2while i%5==0:count2+=1i=i//5print(min(count1,count2))

 python可以处理大数，直接分隔字符串进行相乘，最后统计有多少个零就行了，可以转为字符串或者列表统计，也可以通过整数取余来统计。

或者将整数分解为2,5，看谁的数量更少，就有多少个0

8. 平方和 （字符串运算）

送分题， 直接遍历1-2019，转为字符串判定数字是否存在这些数中，然后平方求和就可以了

 9.快乐司机（贪心）

 送分题，因为没有限制，可以装散的，那么直接按照最大单位价值排序，然后从大到小装就可以了

10.蓝肽子序列（DP，最长公共子序列）

 

import sys  #设置递归深度
import collections  #队列
import itertools  # 排列组合
import heapq  #小顶堆
import math
sys.setrecursionlimit(300000)s1=input()+'!'
s2=input()+'!'# 拆分字符串
temp=''
ss1=[]
ss2=[]
for i in range(len(s1)):temp+=s1[i]if s1[i+1]=='!':ss1.append(temp)temp=''breakif s1[i+1].isupper():ss1.append(temp)temp=''for i in range(len(s2)):temp+=s2[i]if s2[i+1]=='!':ss2.append(temp)breakif s2[i+1].isupper():ss2.append(temp)temp=''# 处理公共最长字符串
ss1=[0]+ss1
ss2=[0]+ss2
dp = [[0]*1010 for i in range(1010)]
for i in range(1,len(ss1)):for j in range(1,len(ss2)):dp[i][j]=max(dp[i-1][j],dp[i][j-1])if ss1[i]==ss2[j]:dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1)print(dp[len(ss1)-1][len(ss2)-1])

考察最长公共子序列，这里有个难点就是需要拆分，我这里通过给输入加结束符便于处理，需要牢记最长公共自序列模板

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

if s1=s2:
        dp=max( dp[i][j] , dp[i-1][j-1]+1 )

11.合唱队形（最长递增子序列）

import sys  #设置递归深度
import collections  #队列
import itertools  # 排列组合
import heapq  #小顶堆
import math
sys.setrecursionlimit(300000)# 两次连续最长递增字符列
n=int(input())
rem = [0]+list(map(int,input().split()))  # 处理下标
dp1=[1]*(n+1)  # 从左到右
dp2=[1]*(n+1)  # 从右到左for i in range(2,n+1):  # 顺序找最长公共子序列for j in range(1,i):if rem[j]<rem[i]:dp1[i]=max(dp1[i],dp1[j]+1)
#print(*dp1)
for i in range(n-1,-1,-1):  # 逆序找最长公共子序列for j in range(n,i,-1):if rem[j]<rem[i]:dp2[i]=max(dp2[i],dp2[j]+1)
#print(*dp2)ans=0
for i in range(1,n+1):  # 计算最大值ans=max(dp1[i]+dp2[i]-1,ans)# print(ans)
print(n-ans)

记住最递增子序列从1开始，初始化dp全为1，因为本身就算一个，其次注意最长递增子序列的递推式。

12.字符串编辑距离（DP，经典问题DP）

 

import sys  #设置递归深度
import collections  #队列
import itertools  # 排列组合
import heapq  #小顶堆
import math
sys.setrecursionlimit(300000)def init(s,t):dp = [[0 for i in range(len(t) + 1)] for j in range(len(s) + 1)]for i in range(len(s) + 1):dp[i][0] = 0for j in range(1,len(t) + 1):dp[0][j] = 999999return dpif __name__ == '__main__':s = list(input())t = list(input())dp=init(s,t)for i in range(len(s)):for j in range(len(t)):if s[i] == t[j]:dp[i + 1][j + 1] = dp[i][j]else:dp[i + 1][j + 1] = min(dp[i][j] + 1, dp[i][j + 1])print(dp[-1][-1])

编辑距离的动态规划不太会，这个需要多练
 

模板Python

def init(s,t):dp = [[0 for i in range(len(t) + 1)] for j in range(len(s) + 1)]for i in range(len(s) + 1):dp[i][0] = 0for j in range(1,len(t) + 1):dp[0][j] = 999999return dpif __name__ == '__main__':s = list(input())t = list(input())dp=init(s,t)for i in range(len(s)):for j in range(len(t)):if s[i] == t[j]:dp[i + 1][j + 1] = dp[i][j]else:dp[i + 1][j + 1] = min(dp[i][j] + 1, dp[i][j + 1])dp[i + 1][j + 1] = min( dp[i + 1][j + 1] ,dp[j+1][i]+1)print(dp[-1][-1])

模板C++

#include<iostream>
#include<algorithm>
#include<set>
#include<string>using namespace std;
#define INF 99999999
string s, t;
int dp[1010][1010];void init(){for (int i = 0; i <= s.size(); i++) dp[i][0] = 0;for (int j = 1; j <= t.size(); j++) dp[0][j] = INF;
}int main() {cin >> s >> t;init();for (int i = 1; i <= s.size(); i++) {for (int j = 1; j <= t.size(); j++) {if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1];else  dp[i][j] = min(dp[i - 1][j - 1],min(dp[i - 1][j], dp[i][j - 1])) + 1;}}cout << dp[s.size()][t.size()];return 0;
}

13.小明的背包1（经典0/1背包问题DP）

 

def solve(N,C):  # 从左到右，从上到下 （先种类，再体积）for i in range(1,N+1): # N种物品，先1种，再2种......for j in range(1,C+1):  # 当前背包体积if c[i]>j : dp[i][j] = dp[i-1][j]    # 新增的第i种物品的体积大于背包重量，只有不选，继承上一个选择else: dp[i][j] = max(dp[i-1][j-c[i]]+w[i],dp[i-1][j])  # 装或者不装，找最大值return dp[N][C]
N,C= map(int,input().split())
n=3010
dp = [[0]*n for i in range(n)]  # 初始化dp数组，预留更大空间
c=[0]*n  # 记录体积
w=[0]*n # 记录价值
for i in range(1,N+1):   #读入N种物品的价值和体积c[i],w[i] = map(int,input().split())
print(solve(N,C))

14.最长公共子序列（模板题）

import sys  #设置递归深度
import collections  #队列
import itertools  # 排列组合
import heapq  #小顶堆
import math
sys.setrecursionlimit(300000)n,m=map(int,input().split())
a=[0]+list(map(int,input().split()))
b=[0]+list(map(int,input().split()))
dp=[[0]*1010 for i in range(1010)]
for i in range(1,n+1):for j in range(1,m+1):dp[i][j]=max(dp[i-1][j],dp[i][j-1])if a[i]==b[j]:dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1)
print(dp[n][m])

 最长公共子序列，模板题，注意初始化dp数组为0就可以了。

15.最长连续递增子序列（DP模板）

import sys  #设置递归深度
import collections  #队列
import itertools  # 排列组合
import heapq  #小顶堆
import math
sys.setrecursionlimit(300000)n=int(input())
save=[0]+list(map(int,input().split()))
dp=[1]*(n+1)  # 注意初始化从1开始
for i in range(2,n+1):for j in range(1,i):if save[i]>save[j]:dp[i]=max(dp[i],dp[j]+1)
print(max(dp))   #最长公共子序列，dp[n]不一定是最大的#a ： 1 4 5 2 1
#DP： 1 2 3 2 1

误区：dp[ n ]不一定是最大的， 一定要注意误区，现在才发现，dp[ i ] 是以i为尾元素的子序列的最大值。