第十二届蓝桥杯填空题

• 试题A：卡片
  • 法一、暴力测试法
  • 法二、另解
• 试题B：直线
  • 题解
• 试题C：货物摆放
  • 法一、暴力
  • 法二、在遍历之前筛掉不是n的因数的
• 试题D：路径
  • 法一、改进的迪杰斯特拉算法
  • 法二、动态规划
• 试题E：回路计数
  • 法一、

试题A：卡片

• 分析：11年是从1到2020，2出现的次数，这个题感觉反过来了，求1到多少0-9出现的次数是2021

法一、暴力测试法

• 最后结果是3181

cnt,cnt1,cnt2,cnt3,cnt4,cnt5,cnt6,cnt7,cnt8,cnt9=0,0,0,0,0,0,0,0,0,0
for i in range(1,3182):#左闭右开
    i=str(i)
    cnt+=i.count("0")
    cnt1 += i.count("1")
    cnt2 += i.count("2")
    cnt3 += i.count("3")
    cnt4 += i.count("4")
    cnt5 += i.count("5")
    cnt6+=i.count("6")
    cnt7 += i.count("7")
    cnt8 += i.count("8")
    cnt9 += i.count("9")
print(cnt,cnt1,cnt2,cnt3,cnt4,cnt5,cnt6,cnt7,cnt8,cnt9)#928 2021 1938 1120 938 938 938 938 930 928

法二、另解

• 卡片1最先用完

n=1#卡片1的使用情况
x=1#能拼到的数
while n<2021:
    x+=1
    n+=str(x).count("1")
print(x)#3181

试题B：直线

• 分析：11年有一个题直线划分平面，同样涉及到求斜率
• 已知两点坐标则：斜率 = (y2 - y1) / (x2 - x1)；截距 = y1 - 斜率 * x1=y1-((y2 - y1) / (x2 - x1))x1=(通分)(y1(x2-x1)-x1*(y2-y1))/(x2-x1)

题解

dots = [(i, j) for i in range(20) for j in range(21)]  # 生成所有点
lines = set()
for i in range(len(dots)):
    for j in range(i+1, len(dots)):
        if dots[j][0]-dots[i][0] != 0:#两点的x坐标不相等时进入下面，也是保证了分母不为0
            x1, x2 = dots[i][0], dots[j][0]
            y1, y2 = dots[i][1], dots[j][1]
            k = (y2-y1)/(x2-x1)
            b = (y1*(x2-x1)-x1*(y2-y1))/(x2-x1)  # 这么写不会炸精度
            lines.add((k, b))
print(len(lines)+20)#+20是上面排除的垂直与x轴的情况

• 最后结果为：40257

试题C：货物摆放

法一、暴力

n=2021041820210418
res=0
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            if i*j*k==n:
                res+=1
                # print(i,j,k)
print(res)

• 跑不出结果，n太大了

法二、在遍历之前筛掉不是n的因数的

from math import *
n=2021041820210418
res=0
x=[]
for i in range(1,int(sqrt(n))+1):
    if n%i==0:
        if i not in  x:
            x.append(i)
        if((n//i)  not in x):
            x.append(n//i)
for i in x:
    for j in x:
        for k in x:
            if i*j*k==n:
                res+=1
print(res)

• 最后结果为：2430

试题D：路径

• 下面内容待更新....

法一、改进的迪杰斯特拉算法

法二、动态规划

• 最后结果为：

试题E：回路计数

• 动态规划，状态压缩

法一、