【蓝桥杯2021初赛】-爱代码爱编程

好久没写了，发现自己啥也不会（悲

今天练习了蓝桥杯2021初赛的题目，只会写简单题目。不过收获也不少。

题目链接：问题 - New Online Judge (ecustacm.cn)

题目1：卡片

简简单单的暴力，代码如下：

n = 2021
arr = [n]*10
i = 1
while True:
    tem = i
    while tem>=10:
        pivot = tem%10
        if arr[pivot] != 0:
            arr[pivot] -= 1
        else:
            break
        tem = tem//10
    pivot = tem%10
    if arr[pivot] != 0:
        arr[pivot] -= 1
    else:
        break
    i+=1
print(i)
            
        
        

结果为：

3182

题目2：直线

初中知识啦，算个斜率k和截距b，用元组存到数组里面，一样的就不存，对于斜率为无穷和0的单独计算就完事了，代码如下：

res = []
width = 20
height = 21
for x1 in range(width):
    for y1 in range(height):
        for x2 in range(width):
            for y2 in range(height):
                if x1==x2 or y1 == y2:
                    continue
                else:
                    k = (y1-y2)/(x1-x2)
                    b = (x1*y2-y1*x2)/(x1-x2)
                    if (k,b) not in res:
                        res.append((k,b))
print(width+height+len(res))

计算量也不大，反正主打的就是一个暴力，结果为：

40257

还是学习到了东西的，比如元组存在数组中，用in判断是否存在，还是很好用的。 

 题目3：货物摆放

一开始做的时候脑子有点抽风，没get到点。其实把全部因子求出来，然后三重循环就好了，想通了就很简单。代码如下：

n = 2021041820210418
sq_n = int(n**0.5+1)
arr = []
num = 0
for i in range(1,sq_n):
    if n%i == 0:
        if i not in arr:
            arr.append(i)
        if n//i not in arr:
            arr.append(n//i)
print(arr)
ln = len(arr)
for n1 in arr:
    for n2 in arr:
        for n3 in arr:
            if n1*n2*n3==n:
                num +=1
print(num)
    

由于因子不多，三重循环快的，结果如下：

2430

题目4： 路径

这道题目真不会写，主要是python的Dij算法还没写过，之前只是写过Java版本的，过几天学了再写，先放出一部分代码（给出路径矩阵）

def f(x,y):
    if x==y:#当到自身是路径为0
        return 0
    x,y = max(x,y),min(x,y)
    add = x
    while True:
        if x%y==0:
            return x
        else:
            x += add

arr = []
for i in range(1,2022):
    tem = []
    if i<=21:
        for j in range(1,i+22):
            tem.append(f(j,i))
    elif i>=2000:
        for j in range(i-21,2022):
            tem.append(f(j,i))
    else:
        for j in range(i-21,i+22):
            tem.append(f(j,i))
    arr.append(tem)
print("over!")

跑出矩阵的速度还是很快的，主要是我Dij算法不会写，过几天一定学呜呜呜

题目5~6：不会，放一下

题目7：左孩子右兄弟

最开始的想法比较简单，就是从叶节点开始一层一层遍历回去，就是从数组最后一个遍历回根节点，因为左边是孩子节点，右边是兄弟节点，当遍历的时候只需要比较两边那边最大，然后存下来。只能说很幼稚，很暴力的想法，只是有深度搜索的雏形。果不其然，只跑出来了10%。

代码如下：

n = int(input())
tree = [0]
for i in range(n-1):
    tree.append(int(input())-1)
tree.sort()
deep = [0]*n
has_child = [0]*n
#print(tree)
for i in range(n-1,0,-1):
    deep[tree[i]] = max(deep[tree[i]],1+deep[i]+has_child[tree[i]])
    has_child[tree[i]] += 1
    #print(deep)
    #print(has_child)
print(deep[0])

上述代码的缺陷如下：

1.有深搜的影子但是还是贪心算法，而且只是按照输入的顺序暴力搜索

2.在从前往后遍历的时候，要求输入必须是按照顺序输入的，就是子节点要连在一起。

在网上找到了一篇博客学习： (77条消息) 第十二届蓝桥杯python_niuniuyi~的博客-CSDN博客

n = int(input())
tree = [[] for i in range(n+1)]

for i in range(2,n+1):
    father = int(input())
    tree[father].append(i)

def dfs(t):
    deep = 0
    for i in range( len(tree[t]) ):
        deep = max(deep,dfs(tree[t][i])+len(tree[t]))
    return deep

print(dfs(1))

有时候真佩服这么想出来这么简洁的代码却能跑出这么好的效果。

题目8：括号序列

哦，完全不会，不过上课讲过一种利用栈判断括号是否完备的小小算法。练手一下。

代码如下：

s = input()
arr = [ 1 if s[i]=='(' else 0 for i in range(len(s))]
def isR(arr):
    vertify = []
    for tem in arr:
        if tem == 1:
            vertify.append(tem)
        else:
            if len(vertify)==0:
                return False
            vertify.pop()
    return len(vertify)==0

if isR(arr):
    print(0)
else:
    pass

题目9：时间显示

简简单单的，甚至不需要判断年份，非常体贴。

import time
T = int(input())
arr = []
for i in range(T):
    arr.append(int(input()))
ans = []
for i in range(T):
    tem = arr[i]
    tem //= 1000
    hour = str((tem//3600)%24)
    min = str((tem//60)%60)
    sec = str(tem%60)
    if len(hour)==1:
        hour = "0"+hour
    if len(min)==1:
        min = "0"+min
    if len(sec)==1:
        sec = "0"+sec
    s = str(hour+":"+min+":"+sec)
    ans.append(s)

for i in ans:
    print(i)

这种题目就算繁琐一点也是简单的，不解释了。

题目10：杨辉三角形

没什么思路，主要就是求一下中间最大值，然后判断区间，接着暴力，只通过了10%，标准答案是利用二分法，我简单看了一下，很巧妙，回头学习，放出我写的代码：

def C(n,m):
    if n==0:
        return 1
    if n==1:
        return m
    x = 1
    y = 1
    for i in range(1,n+1):
        x *= i
    for i in range(m,m-n,-1):
        y *= i
    return y//x

def find(tem,arr):
    for i in range(len(arr)):
        if tem <= arr[i]:
            return i
    return -1

res = [1, 1, 2, 3, 6, 10, 20, 35, 70, 126, 252, 462, 924, 1716, 3432, 6435, 12870, 24310, 48620, 92378, 184756, 352716, 705432, 1352078, 2704156, 5200300, 10400600, 20058300, 40116600, 77558760, 155117520, 300540195, 601080390, 1166803110]
T = int(input())
arr = []
for i in range(T):
    arr.append(int(input()))
ans = []
for i in range(T):
    tem = arr[i]
    if tem==1:
        ans.append(1)
        continue
    pivot = find(tem,res)
    #print(pivot,"p")
    n,m = 0,0
    flag = False
    for i in range(pivot,tem+1):
        if flag:
            break
        for j in range(i//2,0,-1):
            cn = C(j,i)
            if tem > cn:
                i += 1
                break
            if tem == cn:
                n = j
                m = i
                flag = True
                break
    count = (m+1)*m//2+n+1
    ans.append(count)
    
for i in range(T):
    print(ans[i])

写得真的很烂，也没注释。

总结：

第二次开始写算法题目，一些简单的暴力题目还是可以的，也学习到了一些python小技巧，设计难一点的算法就不会了，还得多多学习，未来会更新Dij算法，括号序列和杨辉三角的二分法。