蓝桥杯第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 xelse:fa[x]=find(fa[x])return fa[x]

# 并查集模板
N=int(800000)  # 注意将初始并查集设置大一点，不然可能出现段错误
fa=[]
def init():  # 初始化，默认自身为根接点for i in range(N):fa.append(i)def merge(x,y):   # 发现可以合并，默认选x的根节点为根接点global ansif find(x)!=find(y):  # 不同才合并ans-=1fa[find(x)]=find(y)def find(x):  # 相等就是根结点，不然就递归查找根接点if fa[x]==x:return xelse: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)//2if (a[mid]>=x):high=midelse:low=mid+1#-----------------------------------------------------##在单调递增序列a中查找<=x的数中最小的一个（即x或x的前驱）
while (low<high):mid =(low+high+1)//2if (a[mid]<=x):low=midelse: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=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

一元三次方程求解

#一半测试案例错误 已改正，注意学会使用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)/2if f(x1)*f(mid)<0:x2=midelse:x1=midans.append(x1)
a,b,c,d = map(float,input().split())
for i in range(-100,100): # 100取不到，最后需单独判断if f(i)==0:ans.append(i)continueelse: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=iright=i+1y1=y(left)y2=y(right)if y1==0:  print("{:.2f}".format(left),end=" ")if y1*y2<0 :while (right-left) >= 0.001:                 #eps=0.001mid = (left+right)/2if y(mid)*y(right) <=0: left = midelse:                   right = midprint("{:.2f}".format(right),end=" ")

求立方根问题

学会善用break语句，continue语句

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

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,2if i*i*i==a:print("{:.3f}".format(i))breakelse:left=i;right=i+1for _ in range(10):mid=(left+right)/2if mid*mid*mid > a:right=midelse:left =midprint('{:.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))breakif i*i*i>a:left=i-1;right=ifor _ in range(10):mid=(left+right)/2if mid*mid*mid > a:right=midelse:left =midprint('{:.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=0for x,y in save:mark += (x//i)*(y//i)if mark<k:  # 当前分法不够分continuelength = max(length,i)
print(length)

#二分法解决

注意是找<=x的第一个，应该用
mid=(left+right+1)//2 True:left=midFalse:right=mid-1

import os
import sys# 请在此输入您的代码
def check(d):  # 检查蛋糕大小为d是否可分num = 0for i in range(n):num+=(w[i]//d)*(h[i]//d)if(num>=k):return Trueelse:return Falseh = [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=midelse:R=mid-1
print(L)

翻硬币问题

贪心，从左到右遍历。关键在与当发现不同，只需要更改后面的值即可，同时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)

巧克力

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 = 0days = [i for i in range(1, n+1)]  # [1-n] 天days = sorted(days, reverse=True)  # 从大到小排序for i in days:tmp_c = 0for 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] -= 1break  # 记录了一天，弄另一天if tmp_c == 0:return -1else:c += tmp_creturn cprint(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 = 0days = [i for i in range(1, n+1)]  # [1-n] 天#days = sorted(days, reverse=True)  # 从大到小排序for i in days:tmp_c = 0for 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] -= 1break  # 记录了一天，弄另一天if tmp_c == 0:return -1else:c += tmp_creturn cprint(solve(n, all_list))

顺子日期（手算题）

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)

平方和（送分）

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*ibreak
print(ans)

乘积求0（送分）

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+=1else:break
print(c)

蓝肽子序列

审题：思路上是求最大子序列，需要注意将原来的序列分隔，用到的方法有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]==' '):breakif(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] == ' '):breakif(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]+1else: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

合唱队形

#这里的代码思想贪心，没有维护最值这些情况，只能过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+=1i+=1continueif(a[j]>=a[j-1]):ans+=1j-=1continuewhile a[i]<a[i+1]:i+=1while a[j]<a[j-1]:j-=1
print(ans)

标准答案

if __name__ == "__main__":# 输入并赋初值n = int(input().strip())t = list(map(int, input().split()))dp1 = [1] * ndp2 = [1] * n# 预处理，从左往右LISfor i in range(1, n):for j in range(i):if t[i] > t[j]:dp1[i] = max(dp1[i], dp1[j] + 1)# 预处理，从右往左LISfor 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 = 0for i in range(n):maxx = max(maxx, dp1[i] + dp2[i] - 1)# 自己算了两次，所以-1print(n - maxx)