蓝桥杯
结果填空
空间
256*1024*1024*8/32=67108864
卡片
n=1 #卡片1所用数量
x=1
while n<2021:
x+=1
n+=str(x).count("1")
if n == 2021:
print(x)
else:
print(x-1)
#3181
直线
这题的话借鉴大佬的思路，用两点式直线方程：(y1-y2) * x +(x2-x1) * y +( x1 * y2 - x2 * y1)=0
最后算出的结果是Ax+By+C=0的格式，只要约分后的A、B、C不相同即可视为不同直线
lt=[]
for i in range(20):
for j in range(21):
lt.append((i,j))
def gcd(x,y):
if y==0:
return x
return gcd(y,x%y)
out=set()
for i in range(len(lt)-1):
x1,y1=lt[i]
for j in range(i+1,len(lt)):
x2,y2=lt[j]
A=y1-y2
B=x2-x1
C=x1*y2-x2*y1
k=gcd(gcd(A,B),C) #最大公约数
out.add((A/k,B/k,C/k))
print(len(out))
#40257
货物摆放
import math
n=2021041820210418
lt=set() #集合会比列表更快
out=0
for i in range(1,int(math.sqrt(n))+1):
if n%i==0:
lt.add(i)
lt.add(n//i)
for i in lt:
for j in lt:
for k in lt:
if i*j*k ==n:
out+=1
print(out)
#2430
路径
开始想用Floyd解法，发现要跑很久，后面参考大佬博客学习了一下DP(动态规划)。
思路：
lcm(x,y)函数用于返回x和y的最小公倍数
列表out中存放最短距离，例如out[i]是从节点1到节点i的最短距离，当i在[1,22]范围时，out[i]=i.
但是从i=23开始，就有out[i]=min(out[i-1]+lcm(i-1,i),out[i-2]+lcm(i-2,i),…out[i-20]+lcm(i-20,i),out[i-21]+lcm(i-21,i))
以此类推，一直算到out[2021]即可
out = [0]*2022
def gcd(x,y): #最大公约数
if y==0:
return x
return gcd(y,x%y)
def lcm(x,y): #最小公倍数
g=gcd(x,y)
return x*y//g
for i in range(1,2022):
d = 21 #间隔
if i < 23:
out[i] = i
else:
out[i] = out[i-d] + lcm(i-d,i)
while d:
if out[i-d]+lcm(i-d,i) < out[i]:
out[i] = out[i-d] + lcm(i-d,i)
d -= 1
print(out[2021])
程序设计
时间显示
n=input()
x=int(n[:-3])%(3600*24)
h,d=divmod(x,3600)
m,s=divmod(d,60)
print("{}:{}:{}".format(str(h).zfill(2),str(m).zfill(2),str(s).zfill(2)))
砝码称重
我最初的想法是给每一个砝码质量分配一个系数k，k的值是[1,0,-1]的其中之一，每一个质量乘上系数k之后放在同一侧，看共有多少个可能性，但是太繁琐了…
看了下大佬们的思路发现这题也可以DP，思路就是定义二维数组f[i][j]，i是砝码数量，j是总重量，如果用i个砝码可以称出重量j，则f[i][j]=1。每加入一个新砝码(重为x)，则有：
f[i][x] = 1
同时若用i-1个砝码可以称出重量j，则用i个砝码也可以称出重量j，即f[i][j] = f[i-1][j]
在已有组合的基础上，在天平左右各放一次新砝码，即f[i][j+x]=1、f[i][abs(j-x)]=1
最后统计f[n-1]中1的个数即可，最后两个测试点超时了
n=int(input())
count=0
_max = 0 #能称出的最大重量
a=list(map(int,input().split())) #存放每个砝码的质量
for i in a:
_max += i
f = [[0]*2*_max for i in range(n+1)] #用于dp的数组
f[0][a[0]] = 1 #f[i][j]的值为1代表用i个砝码可以称出质量j
for i in range(1,n):
x = a[i] #当前加入砝码的质量
f[i][x] = 1
for j in range(1,_max+1):
if f[i-1][j]:
f[i][j] = f[i-1][j] #i-1个砝码能称出的质量i个砝码也可以
for j in range(1,_max+1):
if f[i-1][j]: #在前一状态的基础上进行新砝码的摆放
f[i][j+x]=1
f[i][abs(j-x)]=1
#统计
for i in range(1,_max+1):
if f[n-1][i]:
count += 1
print(count)
杨辉三角形
自己写老是超时，参考y神博客写的，大佬的思路真的强…
n=int(input())
def c(a,b):
res = 1
i = a
for j in range(1,b+1):
res = res * i / j
if res > n:
return res
i -= 1
return res
def check(k):
l = 2 * k
r = max(n,l)
while l<r:
mid = l + r >>1
if c(mid,k) >= n:
r = mid
else:
l = mid +1
if c(r,k) != n:
return False
print(int(r*(r+1)/2+k+1))
return True
for i in range(16,0,-1):
if check(i):
break
括号序列
可以用DP做，合法的括号序列需要满足两个条件：
1.左右括号数相同
2.任意前缀中左括号数不小于右括号数
结合这两个条件，可以先用count来表示左括号比右括号多多少个，遍历一遍括号序列，当遇到左括号，count+=1，否则count-=1。当count<0时不满足第二个条件，需要添加一个左括号，同时count+=1，最后得到count的值就是需要添加右括号的个数。
然后定义二维数组f[i][j]为前i个括号中，左括号比右括号多j个的方案数.因而有f[i][j]=f[i-1][j+1]+f[i][j-1]
具体思路看y神博客