[TOC] ## 试题A-卡片 **本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。** 小蓝有很多数字卡片，每张卡片上都是数字0到9 小蓝准备用这些卡片来拼一些数，他想从 1 开始拼出正整数，每拼一个，就保存起来，卡片就不能用来拼其它数了 小蓝想知道自己能从 1拼到多少 例如，当小蓝有 30 张卡片，其中0到9各3张，则小蓝可以拼出1到10但是拼 11 时卡片1已经只有一张了，不够拼出 11。现在小蓝手里有0到9的卡片各 2021张，共 20210张，请问小蓝可以从 1拼到多少? 提示：建议使用计算机编程解决问题。 ### 运行限制 最大运行时间：1s 最大运行内存: 128M tn2>解法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 ``` tn2>解法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 ``` tn2>解法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)) ``` tn2>解法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 tn2>解法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 ``` > 当然上面的解法计算量太大了，肯定是不好的。其实我们可以使用二分查找发，或者是我们可以找到要找的这个数在哪一行的话，直接就生成哪一行的数字匹配就行了，这里就要涉及到二项式极值的计算，简化算法下次直播在说。