蓝桥杯第14天(Python版)

这篇具有很好参考价值的文章主要介绍了蓝桥杯第14天(Python版)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

并查集的使用
# 并查集模板
N=400
fa=[]
def init():  # 初始化,默认自身为根接点
    for i in range(N):
        fa.append(i)

def merge(x,y):   # 发现可以合并,默认选x的根节点为根接点
    fa[find(x)]=find(y)

def find(x):  # 相等就是根结点,不然就递归查找根接点
    if fa[x]==x:
        return x
    else:
        fa[x]=find(fa[x])
        return fa[x]
蓝桥杯第14天(Python版)
蓝桥杯第14天(Python版)
蓝桥杯第14天(Python版)
# 并查集模板
N=int(800000)  # 注意将初始并查集设置大一点,不然可能出现段错误
fa=[]
def init():  # 初始化,默认自身为根接点
    for i in range(N):
        fa.append(i)

def merge(x,y):   # 发现可以合并,默认选x的根节点为根接点
    global ans
    if find(x)!=find(y):  # 不同才合并
        ans-=1
        fa[find(x)]=find(y)

def find(x):  # 相等就是根结点,不然就递归查找根接点
    if fa[x]==x:
        return x
    else:
        fa[x]=find(fa[x])
        return fa[x]

n,m=map(int,input().split())
k = int(input())
ans =n*m
init()  # 初始化
for i in range(k):
    a,b = map(int,input().split())
    merge(a,b)
print(ans) #合根多少次就有多少个合根植物
二分查找

关于二分法的两个模板

#在单调递增序列a中查找>=x的数中最小的一个(即x或x的后驱)
while (low<high):
    mid =(low+high)//2
    if (a[mid]>=x):
        high=mid
    else:
        low=mid+1

#-----------------------------------------------------#

#在单调递增序列a中查找<=x的数中最小的一个(即x或x的前驱)
while (low<high):
    mid =(low+high+1)//2
    if (a[mid]<=x):
        low=mid
    else:
        high=mid-1

找>=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


一元三次方程求解
蓝桥杯第14天(Python版)

#一半测试案例错误 已改正,注意学会使用continue语句

import os
import sys

# 请在此输入您的代码
ans =[]
def f(x):  # 函数
  return x*x*x*a+x*x*b+x*c+d  

def search(x1,x2):
  for i in range(30):
    mid=(x1+x2)/2
    if f(x1)*f(mid)<0:
      x2=mid
    else:
      x1=mid
  ans.append(x1)
a,b,c,d = map(float,input().split())
for i in range(-100,100): # 100取不到,最后需单独判断
  if f(i)==0:
    ans.append(i)
    continue
  else:
    if f(i)*f(i+1)<0:  # 有根
      search(i,i+1)

if f(100)==0:
  ans.append(100)

ans.sort()
for i in ans:
  print('{:.2f}'.format(i),end=' ')

标注答案(我感觉没判断f(100)处)

n = input().split()
a,b,c,d = eval(n[0]),eval(n[1]),eval(n[2]),eval(n[3])
def y(x):
   return a*x*x*x+b*x*x+c*x+d
for i in range(-100,100):
   left=i
   right=i+1
   y1=y(left)
   y2=y(right)
   if y1==0:  print("{:.2f}".format(left),end=" ")
   if y1*y2<0 :
       while (right-left) >= 0.001:                 #eps=0.001
           mid = (left+right)/2
           if y(mid)*y(right) <=0: left = mid
           else:                   right = mid
       print("{:.2f}".format(right),end=" ")
求立方根问题
学会善用break语句,continue语句
蓝桥杯第14天(Python版)

之前写的有问题的(判断条件有问题的)

t = int(input())
for _ in range(t):
    a= int(input())
    for i in range(0,10000,1):
        if i*i*i=<a and (i+1)*(i+1)*(i+1)>=a:  #问题处在这里,例如求8时 i=1,2
            if i*i*i==a:
                print("{:.3f}".format(i))
                break
            else:
                left=i;right=i+1
                for _ in range(10):
                    mid=(left+right)/2
                    if mid*mid*mid > a:
                        right=mid
                    else:
                        left =mid
                print('{:.3f}'.format(left))
                break
 

#自我改进写法,改正后答案

t = int(input())
for _ in range(t):
    a= int(input())
    for i in range(0,10000,1):
        if i*i*i==a:
                print("{:.3f}".format(i))
                break
        if i*i*i>a:
                left=i-1;right=i
                for _ in range(10):
                    mid=(left+right)/2
                    if mid*mid*mid > a:
                        right=mid
                    else:
                        left =mid
                print('{:.3f}'.format(left))
                break
分蛋糕问题

#暴力方法做的 75%通过率,会超时

import os
import sys

# 请在此输入您的代码
n,k = map(int,input().split())
length = 1
save=[]
for i in range(n):
  save.append(list(map(int,input().split())))
for i in range(1,1000):  #遍历大小
  mark=0
  for x,y in save:
    mark += (x//i)*(y//i)
  if mark<k:  # 当前分法不够分
    continue
  length = max(length,i)
print(length)

#二分法解决

注意是找<=x的第一个,应该用
mid=(left+right+1)//2 
    True:
        left=mid
    False:
        right=mid-1
import os
import sys

# 请在此输入您的代码
def check(d):  # 检查蛋糕大小为d是否可分
  num = 0
  for i in range(n):
    num+=(w[i]//d)*(h[i]//d)
  if(num>=k):return True
  else:return False

h = [0]*100010
w = [0]*100010
n,k = map(int,input().split())
for i in range(n):  # 读入蛋糕大小
  h[i],w[i] = map(int,input().split())

L,R = 1,100010   # 结尾更大防止出现边界问题
while L<R:
  mid=(L+R+1)//2    #偶数中值为左值  [1,2] -->1  ,没有则取后
  if(check(mid)): # 当前分发可分,二分法取左值
    L=mid
  else:
    R=mid-1
print(L)
翻硬币问题
蓝桥杯第14天(Python版)
蓝桥杯第14天(Python版)
贪心,从左到右遍历。关键在与当发现不同,只需要更改后面的值即可,同时ans++
import os
import sys

# 请在此输入您的代码
ans=0
# 因为要反转,即改变值,字符串不能改变,所以转为列表处理
begin = list(input())
end = list(input())
for i in range(len(begin)-1):  # 每次翻两个,只能遍历到 [1 - n-1]
  if begin[i]!=end[i]: # 翻转
    if begin[i+1]=='*':
      begin[i+1]='o'
    else:
      begin[i+1]='*'
    ans+=1   #记录翻转次数
print(ans)
巧克力
蓝桥杯第14天(Python版)
蓝桥杯第14天(Python版)
n, kind = map(int, input().split())
all_list = []  # 存储信息
for i in range(kind):
   info_list = [int(i) for i in input().split(' ')]
   all_list.append(info_list)
all_list.sort(key=lambda x: x[0])  # 按照单价从大到小排序


def solve(n, all_list):
   c = 0
   days = [i for i in range(1, n+1)]  # [1-n] 天
   days = sorted(days, reverse=True)  # 从大到小排序
   for i in days:
       tmp_c = 0
       for j in all_list:
           if j[2] > 0:   #还剩下货物
               if j[1] >= i:  # 是否大于保质期
                   tmp_c += j[0]
                   index = all_list.index(j)  # 更新剩余量
                   all_list[index][2] -= 1
                   break  # 记录了一天,弄另一天
       if tmp_c == 0:
           return -1
       else:
           c += tmp_c
   return c


print(solve(n, all_list))
建议的写法:
根据单价排序后,创建一个列表来记录每天吃什么,首先判断是否还有,然后判断是否过保质期,没过就添加,过了就选择下一款,选择了就break,选择下一天的食物
n, kind = map(int, input().split())
all_list = []  # 存储信息
for i in range(kind):
   info_list = [int(i) for i in input().split(' ')]
   all_list.append(info_list)
all_list.sort(key=lambda x: x[0])  # 按照单价从小到大排序
#print(all_list)

def solve(n, all_list):
   c = 0
   days = [i for i in range(1, n+1)]  # [1-n] 天
   #days = sorted(days, reverse=True)  # 从大到小排序
   for i in days:
       tmp_c = 0
       for j in all_list:
           if j[2] > 0:   #还剩下货物
               if j[1] >= i:  # 是否大于保质期
                   tmp_c += j[0]
                   index = all_list.index(j)  # 更新剩余量
                   all_list[index][2] -= 1
                   break  # 记录了一天,弄另一天
       if tmp_c == 0:
           return -1
       else:
           c += tmp_c
   return c


print(solve(n, all_list))
顺子日期(手算题)
蓝桥杯第14天(Python版)
import os
import sys

# 请在此输入您的代码
# 2022  #非闰年  year%400==0 or( year %4==0 and year%100!=0)
#012 10 [0-9]  
#02
#03
#04
#05
#06
#07
#08
#09
#10   1  12
#11   1  23
#123  2 [0-1]


print(14)
平方和(送分)
蓝桥杯第14天(Python版)
import os
import sys

# 请在此输入您的代码
ans=0
mark=['2','0','1','9']
for i in range(1,2020):
  #if( '2' or '0'or '1'or'9' in str(i)):  #这样的话相当于累加1-2019的所有数,判定条件有问题
  for j in mark:
    if j in str(str(i)):
      ans+=i*i
      break
print(ans)
乘积求0(送分)
蓝桥杯第14天(Python版)
a = '''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'''
a = a.split()
b=1
c=0
for i in a:
    b=b*int(i) #计算结果
b=str(b)
b=b[::-1]  # 倒叙查看看有多少个0
for j in b:
    if j=='0':
        c+=1
    else:
        break
print(c)
蓝肽子序列
蓝桥杯第14天(Python版)
审题:思路上是求最大子序列,需要注意将原来的序列分隔,用到的方法有str.upper()方法,以及注意索引出界问题,同时将dp数组转为下标从1开始处理
import os
import sys

# 请在此输入您的代码
# 公共子序列问题
# 给他添加结尾,便于分隔,避免出现索引出界问题
ss1=input()+' '
ss2=input()+' '
s1=['']
s2=['']
# 分隔序列
temp_s=''
i=0
while i <len(ss1)-1:
  temp_s+=ss1[i]
  if(ss1[i+1]==' '):
    break
  if(ss1[i+1].isupper()):
    s1.append(temp_s)
    temp_s=''
  i+=1
s1.append(temp_s)
temp_s=''
i=0
while i <len(ss2)-1:
  temp_s+=ss2[i]
  if (ss2[i + 1] == ' '):
    break
  if(ss2[i+1].isupper()):
    s2.append(temp_s)
    temp_s=''
  i+=1
s2.append(temp_s)

dp=[[0]*1001 for i in range(1001)]
for i in range(1,len(s1)):
  for j in range(1,len(s2)):
    if s1[i]==s2[j]:
      dp[i][j]=dp[i-1][j-1]+1
    else:
      dp[i][j]=max(dp[i-1][j],dp[i][j-1])
print(dp[len(s1)-1][len(s2)-1])  #下标索引从1开始,
# print(s1)
# print(s2)
# s1=012  len(s1) = 3
合唱队形
蓝桥杯第14天(Python版)

#这里的代码思想贪心,没有维护最值这些情况,只能过10%的点,有问题

import os
import sys

# 请在此输入您的代码
n=int(input())
a = list(map(int,input().split()))
#print(sorted(save))   # [130, 150, 160, 186, 186, 197, 200, 220]
# 原序列,抽人,不要动相应位置
i,j=0,len(a)-1
ans=0
while (i<j):
  if(a[i]>=a[i+1]):
    ans+=1
    i+=1
    continue
  if(a[j]>=a[j-1]):
    ans+=1
    j-=1
    continue
  while a[i]<a[i+1]:
    i+=1
  while a[j]<a[j-1]:
    j-=1
print(ans)

标准答案文章来源地址https://www.toymoban.com/news/detail-407648.html

if __name__ == "__main__":

    # 输入并赋初值
    n = int(input().strip())

    t = list(map(int, input().split()))

    dp1 = [1] * n
    dp2 = [1] * n

    # 预处理,从左往右LIS
    for i in range(1, n):
        for j in range(i):
            if t[i] > t[j]:
                dp1[i] = max(dp1[i], dp1[j] + 1)

    # 预处理,从右往左LIS
    for i in range(n - 1, 0, -1):
        for j in range(n - 1, i, -1):
            if t[i] > t[j]:
                dp2[i] = max(dp2[i], dp2[j] + 1)


    maxx = 0

    for i in range(n):
        maxx = max(maxx, dp1[i] + dp2[i] - 1)
        # 自己算了两次,所以-1
        
    print(n - maxx)
    

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

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

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

相关文章

  • 蓝桥杯第十三届决赛真题-左移右移

    题目链接 问题描述 小蓝有一个长度为 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)
  • 蓝桥杯必备模板(python)

    🔥只有把基础的算法模板熟练掌握,才有可能解决考场上变化的题目,本篇文章最适合了解这些算法的同学进行全盘复习,不断背诵使用。当然如果是小白,大部分算法模板我都放了视频链接,相信你们一定能看懂的,蓝桥杯冲冲冲!文章最下方还有篇文章链接哦!!!🚀🚀

    2023年04月09日
    浏览(38)
  • 蓝桥杯【第14届省赛】Python B组

    居然是全省第二 (广东 B 组省一共 91 人,前 2.1%),差点没把我笑死 运气成分比较多,当时比赛的时候只做对了 A、C、I,然后在 D、F、J 混了点分 (本题解是赛后思考修正的),归功于 I 的分值比较高又刚好会做哈哈 测试链接:https://www.dotcpp.com/oj/train/1093/ 【问题描述】     

    2023年04月19日
    浏览(46)
  • 蓝桥杯【第14届国赛】Python B组

    倒数第二题交的时候多了一个print,只拿了国二,吐血 本题解仅代表个人观点,仅供参考,欢迎各位指正 【问题描述】         小蓝有 20230610 颗磁力弹珠,他对金字塔形状尤其感兴趣,如下图所示:         高度为 1 的金字塔需要 1 颗弹珠;         高度为 2 的

    2024年02月08日
    浏览(103)
  • 蓝桥杯之算法模板题 Python版

    记录一下算法模板题,这样方便查阅和学习,希望好好加油 dp, LIS ** 01背包 动态转移方程 f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] , f [ i − 1 ] [ j − v ] + w ) ( j v ) f[i][j] = max(f[i-1][j], f[i-1][j-v] + w)(jv) f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] , f [ i − 1 ] [ j − v ] + w ) ( j v ) 完全背包 一般就是

    2023年04月08日
    浏览(48)
  • 蓝桥杯【第14届省赛】Python B组 76.10分

    居然是全省第二 (广东 B 组省一共 91 人,前 2.1%),差点没把我笑死 运气成分比较多,当时比赛的时候只做对了 A、C、I,然后在 D、F、J 混了点分 (本题解是赛后思考修正的),归功于 I 的分值比较高又刚好会做哈哈 测试链接:https://www.dotcpp.com/oj/train/1093/ 【问题描述】     

    2024年02月05日
    浏览(40)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包