蓝桥杯第19天(Python)(疯狂刷题第2天)

这篇具有很好参考价值的文章主要介绍了蓝桥杯第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.一元三次方程求解(二分,格式化输出)

蓝桥杯第19天(Python)(疯狂刷题第2天)

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+d

ans=[]
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+1
      while(r-l>=0.001):  # 保留精度,2位小数,注意循环条件
         mid=(l+r)/2
         if f(l)*f(mid)<0:
            r=mid
         else:
            l=mid
      ans.append(l)
if f(100)==0:
   ans.append(100)
for i in ans:
   print("{:.2f}".format(i),end=' ')

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

2.解立方根(二分)

蓝桥杯第19天(Python)(疯狂刷题第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))
         break
      elif i**3>n:  # 最后的结果为小数,通过二分处理
         left=i-1;right=i;
         while(right-left>0.00001):
            mid=(left+right)/2
            if(mid**3>n):
               right=mid
            else:
               left=mid
         print('{:.3f}'.format(l))
         break

         

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

3.分巧克力(二分,注意二分的两个模板)

蓝桥杯第19天(Python)(疯狂刷题第2天)

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=0
   for a,b in save:
      count+=(a//i)*(b//i)
   if count>=k:
      return True
   else:
      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=mid
   else:
      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=mid
        else:
            low=mid+1
    print(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=mid
        else:
            high=mid-1
    print(a[low])
    print(a[high])
search(low,high,10)  # 查找结果10
 
 

4.翻硬币(贪心)

蓝桥杯第19天(Python)(疯狂刷题第2天)

 

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.巧克力(贪心) 

蓝桥杯第19天(Python)(疯狂刷题第2天)

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.顺子日期(思维题,细心,手数)

蓝桥杯第19天(Python)(疯狂刷题第2天) 

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

7.乘积尾零(大数运算或者大数分解)

蓝桥杯第19天(Python)(疯狂刷题第2天)

import sys  #设置递归深度
import collections  #队列
import itertools  # 排列组合
import heapq  #小顶堆
import math
sys.setrecursionlimit(300000)

# 因为只有2,5有用,所以只记录2和5的数量
count1=0
count2=0

s="""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+=1
      i=i//2
   while i%5==0:
      count2+=1
      i=i//5

print(min(count1,count2))

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

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

8. 平方和 (字符串运算)

蓝桥杯第19天(Python)(疯狂刷题第2天)

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

 9.快乐司机(贪心)

蓝桥杯第19天(Python)(疯狂刷题第2天)

蓝桥杯第19天(Python)(疯狂刷题第2天)

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

10.蓝肽子序列(DP,最长公共子序列)

蓝桥杯第19天(Python)(疯狂刷题第2天)

 

蓝桥杯第19天(Python)(疯狂刷题第2天)

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=''
      break
   if s1[i+1].isupper():
      ss1.append(temp)
      temp=''

for i in range(len(s2)):
   temp+=s2[i]
   if s2[i+1]=='!':
      ss2.append(temp)
      break
   if 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.合唱队形(最长递增子序列)

蓝桥杯第19天(Python)(疯狂刷题第2天)

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)

蓝桥杯第19天(Python)(疯狂刷题第2天)

 

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] = 0

    for j in range(1,len(t) + 1):
        dp[0][j] = 999999

    return dp

if __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] = 0

    for j in range(1,len(t) + 1):
        dp[0][j] = 999999

    return dp

if __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)

蓝桥杯第19天(Python)(疯狂刷题第2天)

 

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.最长公共子序列(模板题)

蓝桥杯第19天(Python)(疯狂刷题第2天)

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模板)

蓝桥杯第19天(Python)(疯狂刷题第2天)

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为尾元素的子序列的最大值。文章来源地址https://www.toymoban.com/news/detail-421399.html

到了这里,关于蓝桥杯第19天(Python)(疯狂刷题第2天)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 蓝桥杯第14天(Python版)

    并查集的使用 二分查找 关于二分法的两个模板 找=x的第一个,mid=(low+high)//2 找=x的第一个,mid=(low+high+1)//2 一元三次方程求解 #一半测试案例错误 已改正,注意学会使用continue语句 标注答案(我感觉没判断f(100)处) 求立方根问题 学会善用break语句,continue语句 之前写

    2023年04月09日
    浏览(32)
  • 蓝桥杯第六讲--简单dp【例题】

    蓝桥杯官网:蓝桥杯大赛——全国大学生TMT行业赛事 ✨本博客讲解 蓝桥杯C/C++ 备赛所涉及算法知识,此博客为第六讲:简单dp【例题】 本篇博客所包含习题有: 👊 01背包问题 👊 摘花生 👊 最长上升子序列 简单dp【习题】见博客:蓝桥杯第六讲–简单dp【习题】 博客内容以

    2023年04月25日
    浏览(45)
  • 蓝桥杯第十三届决赛真题-左移右移

    题目链接 问题描述 小蓝有一个长度为 N 的数组, 初始时从左到右依次是 1,2,3, …N 。 之后小蓝对这个数组进行了 M 次操作, 每次操作可能是以下 2 种之一: 左移 x, 即把 x 移动到最左边。 右移 x, 即把 x 移动到最右边。 请你回答经过 M 次操作之后, 数组从左到右每个数是多少? 输

    2023年04月09日
    浏览(46)
  • 蓝桥杯第十三届单片机国赛程序

    写在前面: 做完总体来说感觉一年比一年难了(估计是被骂的),虽然十三届用的底层少,但是做起来困难重重。 最难的难点在于定时器安排问题。15F2K60S2系列单片机只有三个定时器,本届题目考到了频率测量、超声波、PWM输出,再加上刷新,每一个都需要一个定时器,比

    2024年02月08日
    浏览(52)
  • 【蓝桥杯嵌入式】蓝桥杯第十二届省赛程序真题,真题分析与代码讲解

    🎊【蓝桥杯嵌入式】专题正在持续更新中,原理图解析✨,各模块分析✨以及历年真题讲解✨都在这儿哦,欢迎大家前往订阅本专题,获取更多详细信息哦🎏 🎏【蓝桥杯嵌入式】蓝桥杯第十届省赛真题 🎏【蓝桥杯嵌入式】蓝桥杯第十三届省赛程序真题 🪔本系列专栏 -  

    2023年04月15日
    浏览(92)
  • 蓝桥杯第十四届蓝桥杯模拟赛第三期考场应对攻略(C/C++)

    这里把我的想法和思路写出来,恳请批评指正! 目录 考前准备 试题1: 试题2: 试题3: 试题4: 试题5: 试题6: 试题7: 试题8: 试题9: 试题10: 总结: 考前五分钟,开十个源文件,并把头文件等必须写的部分写出来,写完的程序一定要有顺序地保留 问题描述 请找到一个

    2024年02月02日
    浏览(167)
  • 蓝桥杯第十四届省赛完整题解 C/C++ B组

    没有测评,不知道对不对,仅仅过样例而已 本题总分:5 分 【问题描述】 小蓝现在有一个长度为 100 的数组,数组中的每个元素的值都在 0 到 9 的 范围之内。数组中的元素从左至右如下所示: 5 6 8 6 9 1 6 1 2 4 9 1 9 8 2 3 6 4 7 7 5 9 5 0 3 8 7 5 8 1 5 8 6 1 8 3 0 3 7 9 2 7 0 5 8 8 5 7 0 9 9 1 9

    2023年04月13日
    浏览(51)
  • 【蓝桥杯试题】暴力枚举题型

    💃🏼 本人简介:男 👶🏼 年龄:18 🤞 作者:那就叫我亮亮叭 📕 专栏:蓝桥杯试题 有一个 n×m 方格的棋盘,求其方格包含多少正方形、长方形(不包含正方形)。 输入格式 一行,两个正整数 n,m(n ≤ 5000, m ≤ 5000)。 输出格式 一行,两个正整数,分别表示方格包含多少

    2023年04月08日
    浏览(62)
  • 力扣python刷题day04|LeetCode24、19、160、142

    题目 来源:24:两两交换链表中的节点 建议使用虚拟头结点,这样会方便很多,要不然每次针对头结点(没有前一个指针指向头结点),还要单独处理。 接下来就是交换相邻两个元素了,此时一定要画图,不画图,操作多个指针很容易乱,而且要操作的先后顺序 方法: 题目

    2024年02月16日
    浏览(37)
  • Leetcode刷题第八天-回溯

    22:括号生成 链接:22. 括号生成 - 力扣(LeetCode) 括号是一对,所以每一次递归结束条件是字符串长度=2*n 有效括号判断:\\\'(\\\'个数==\\\')\\\'个数时,当前必须是\\\'(\\\',\\\'(\\\'个数==n时,必须是\\\')\\\',其他情况当前位置遍历两边,既可以是\\\'(\\\'又可以是\\\')\\\' generateParenthesis 89:格雷编码 链接:89.

    2024年02月19日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包