python蓝桥杯2021省赛A组

试题A-卡片

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

小蓝有很多数字卡片，每张卡片上都是数字0到9
小蓝准备用这些卡片来拼一些数，他想从 1 开始拼出正整数，每拼一个，就保存起来，卡片就不能用来拼其它数了
小蓝想知道自己能从 1拼到多少
例如，当小蓝有 30 张卡片，其中0到9各3张，则小蓝可以拼出1到10但是拼 11 时卡片1已经只有一张了，不够拼出 11。现在小蓝手里有0到9的卡片各 2021张，共 20210张，请问小蓝可以从 1拼到多少?

提示：建议使用计算机编程解决问题。

运行限制

最大运行时间：1s
最大运行内存: 128M

解法1：把拥有的数根据出来在匹配

import sys
## 先构建0，9的组合
numblist = []
for j in range(0,2021):
    for i in range(0,10):
        numblist.append(i)
## print(numblist)
calnumber = 1
while True:
    for item in str(calnumber):
        itemint = int(item)
        ## 说明在我们的卡片中能找到这个数
        if itemint in numblist:
            ## 找到之后把这个卡片拿出来
            numblist.remove(itemint)
        ## 找不到就说明需要的卡片不够了，说明最多只能拼到当前这个数
        else:
            print(calnumber-1)
            ## 直接退出程序
            sys.exit()
    calnumber = calnumber+1

解法2:拼这些数字，最先不够的就是1，所以只需要判断1用完的时候就是结果了

## 能拼数字的上限其实是1最先用完的时候，因为所有数字1最先用完
calnumber = 1
use_one_count = 0
## 直接一个死循环计算1用了的次数
isFind = True
while isFind:
    for item in str(calnumber):
        itemint = int(item)
        ## 计算1用了的次数
        if(itemint==1):
            use_one_count = use_one_count+1
        ## 用的次数到了2021就退出
        if(use_one_count==2021):
            isFind = False
            break
    calnumber = calnumber+1
print(calnumber-1)

试题F-时间显示

小蓝要和朋友合作开发一个时间显示的网站
在服务器上，朋友已经获取了当前的时间，用一个整数表示，值为从1970年1月1日 00:00:00到当前时刻经过的毫秒数现在，小蓝要在客户端显示出这个时间。小蓝不用显示出年月日，只需要显示出时分秒即可，毫秒也不用显示，直接舍去即可。给定一个用整数表示的时间，请将这个时间对应的时分秒输出。
输入描述
输入一行包含一个整数，表示时间。
输出描述
输出时分秒表示的当前时间，格式 HH: MM: SS ,其中 表示时，值为0到 23，表示分，值为0到 59，S5表示秒，值为0到 59时、分、秒不足两位时补前导0。

输入输出样例

示例1

输入

46800999

输出

13:00:00

示例2

输入

1618708103123

输出

01:08:23

解法1：直接把除掉天之后的秒数来计算时分秒

## n = 1618708103123
n =(int)(input())
## 舍去毫秒,转化为秒
n = n//1000
######## 计算除掉天剩下的秒数
## 计算一天的秒数
daySeconds = 24*60*60
## 计算除掉天剩下的秒数(不足一天的秒数)，直接取模即可
restSeconds = n%daySeconds
## print(restSeconds)
######## 计算小时数
hour = restSeconds//(60*60)
## 计算除掉小时剩下的秒数(不足一小时的秒数)
restSeconds = restSeconds%(60*60)
######## 计算分钟数
minute = restSeconds//(60)
## 计算除掉分钟剩下的秒数(不足一分钟的秒数)
restSeconds = restSeconds%(60)
## print(hour,minute,restSeconds)
print("%02d:%02d:%02d"%(hour,minute,restSeconds))

解法2：直接利用python的timedelta函数来计算

from datetime import datetime, timedelta
start = datetime(year=1970, month=1, day=1)
dela = timedelta(milliseconds=1)
now = 1618708103123
now = start + now * dela
#print(now)
print('%02d:%02d:%02d' % (now.hour, now.minute, now.second))

试题 H: 杨辉三角形

问题描述

下面的图形是著名的杨辉三角形:

如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列:
1, 1, 1, 1, 2,1,1, 3, 3,1, 1, 4, 6, 4, 1, …
给定一个正整数 N，请你输出数列中第一次出现 N 是在第几个数?

[输入格式]

输入一个整数 N。

[输出格式]

输出一个整数代表答案。

[样例输入]

6

[样例输出]

13

评测用例规模与约定

对于 20的评测用例，1<N <10; 对于所有评测用例，1<N1000000000

运行限制

最大运行时间: 1s
最大运行内存:256M

解法1：利用二项式定理来生成杨辉三角形，然后遍历匹配

利用二项式定理来生成杨辉三角形：

def CalNResult(n):
    result = 1
    for i in range(1,n+1):
        result=result*i
    return result
def CalNumberByLine(n):
    resultList = []
    for r in range(0,n):
       caln = n-1
       result = CalNResult(caln)//(CalNResult(r)*CalNResult(caln-r))
       resultList.append(result)
    return  resultList

当然生成方法有很多，比如递归就可以很简洁,这里我们先用二项式定理生成

然后遍历匹配即可得解：

## 需要找的数
n = 15
## 找的次数
findcount = 0
line = 1
while True:
    resultList = CalNumberByLine(line)
    for j in range(0,len(resultList)):
        ## print(resultList[j])
        ## 每找一次就加1
        findcount = findcount+1
        if resultList[j]== n:
            print(findcount)
            sys.exit()
    line = line+1

当然上面的解法计算量太大了，肯定是不好的。其实我们可以使用二分查找发，或者是我们可以找到要找的这个数在哪一行的话，直接就生成哪一行的数字匹配就行了，这里就要涉及到二项式极值的计算，简化算法下次直播在说。