2021年第十二届蓝桥杯python组省赛
前言：
最近忙着备战期末考，刷算法的时间是越来越少了...
目录
填空题
卡片
直线
货物摆放
回路计数
路径
编程大题
时间显示
杨辉三角
左孩子右兄弟
异或数列
括号序列
填空题
卡片
题目：
小蓝拥有成百上千张分别标有数字0至9的卡片。他打算利用这些卡片来排列出一系列的整数，并将生成的数字记录下来。需要注意的是，在生成每一个新的数字后，所使用的卡片就不能再被用于后续的拼接工作了。因此，在这个过程中形成的每一个连续整数都会被保留下来。
小蓝的目标是从1开始连续生成所有的正整数，并将生成的数字记录下来。然而，在实际操作中由于资源限制，并不能无限地进行下去。
现在的情况是小蓝拥有的是数量充足的数字卡片——每种数字各有2021张（总数为2021×10=20210张）。那么在这种情况下，请问他最多能从1开始连续拼出哪些正整数呢？
提示：建议使用计算机编程的方法来解决这个问题
思路：
for循环走一遍，直到其中一个数字不够用
代码：
def main():
nums=[2021 for _ in range(10)]
n=1
while 1:
for i in str(n):
nums[int(i)] -= 1
if nums[int(i)]<0:
return n-1
n += 1
print(main())答案：3181
直线
题目：
在平面直角坐标系中任意取定两个不同点，则这两点唯一对应一条直线。
给定点集S = {(x, y) | x为整数且满足0 ≤ x < 20，
y为整数且满足0 ≤ y < 21}，
即所有横坐标为从0到19（包括端点），
纵坐标为从0到20（包括端点）的整数坐标的点。
那么这些整点总共能构成多少条互不相同的直线？
思路：
当斜率为0或无穷大时, 直线上点的数量为m+n个. 随后建立一个包含所有直线参数(k, b) 的集合, 并将每个点对应的k 和 b 值加入到该集合中. 最后使用 len() 函数计算该集合中元素的数量.
代码：
def main(m,n):
res=set()
point=[[x,y] for x in range(m) for y in range(n)]
for i in range(len(point)-1):
for j in range(i+1,len(point)):
x1,y1=point[i][0],point[i][1]
x2,y2=point[j][0],point[j][1]
if x1==x2 or y1==y2:
continue
else:
k=(y2-y1)/(x2-x1)
b=(x2*y1-x1*y2)/(x2-x1)
#print((x1,y1),(x2,y2),(k,b))
res.add((k,b))
return len(res)+m+n
print(main(20,21))答案：40257
货物摆放
题目：
小蓝拥有一个极大容量的仓库空间，在此可容纳大量货物。
目前，在仓库中存放着n箱货物。
这些货物均为标准规格的立方体形状。
为了便于管理与存储效率最大化，在确定放置方向时，
规定所有货物必须严格平行于长度、宽度和高度这三个相互正交的方向。
小蓝的目标是将所有货物堆叠形成一个大立方体，
即在长度、宽度和高度方向上分别堆叠L、W、H层货物，
且满足总体积关系式：n = L × W × H。
当已知n值，请计算符合摆放要求的不同方案总数。
举例来说，在n=4的情况下，则共有6种不同的摆放方式符合条件。
那么对于n=2021041820210418这个数值而言，请问有多少种符合条件的摆放方案？
思路：
找出n的所有因子，然后三层循环依次取值，找出满足的个数
代码：
import math
n=2021041820210418
nums=set()
for i in range(1,int(math.sqrt(n))+1):
t1=n/i
if t1 == int(t1):
nums.add(i)
nums.add(int(n/i))
x = 0
for l in nums:
for k in nums:
for m in nums:
if l * k * m == n:
x = x + 1
print(x)答案：2430
回路计数
题目：
蓝桥学院由21栋单体建筑构成，在建筑内部设置了21个独立空间区域。
每个区域按照编号从1至21依次排列分布。
当两栋建筑的编号互质时，在其对应位置设有直接通道连接。
这些通道设计采用双向通达方式以确保任意两栋互质编号建筑之间都可以实现便捷沟通。
从第一栋建筑出发，请问你能否设计一条路线使得你能够遍历所有建筑恰好一次并最终返回原点？这里所说的路径不同是指存在某个i，在完成第i个建筑之后所前往的下一个建筑有所区别。
思路：
图论不会
<>
代码：
from math import gcd
n = int(input())
m = 1 << n
dp = [[0 for j in range(n)] for i in range(m)] # dp[i][j]对于状态i，i的二进制表示中为1的位置 表示走过了教学楼j
load = [[False for j in range(n)] for i in range(n)] # 存储i, j之间是否有路
for i in range(1, n + 1):
for j in range(1, n + 1):
if gcd(i, j) == 1:
load[i - 1][j - 1] = True
dp[1][0] = 1
for i in range(1, m): # 枚举每一种状态
for j in range(n):
if i >> j & 1: # 判断状态i是否包含第j栋教学楼
for k in range(n): # 枚举所有可能从教学楼k走到教学楼j的情况
if i - (1 << j) >> k & 1 and load[k][j]: # 判断状态i除去j后是否包含k
dp[i][j] += dp[i - (1 << j)][k]
print(sum(dp[m - 1]) - dp[m - 1][0])
21
881012367360答案：10266837
路径
题目：
小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图中的最短路径。
小蓝的图由2021个结点组成，依次编号1至2021
对于两个不同的结点a,b,如果a和b的差的绝对值大于21,则两个结点之间没有边相连；如果a和b的差的绝对值小于等于21,则两个点之间有一条长度为a和b的最小公倍数的无向边相连。
例如：结点1和结点23之间没有边相连；结点3和结点24之间有一条无向边，长度为24;结点15和结点25之间有一条无向边，长度为75.
请计算，结点1和结点2021之间的最短路径长度是多少。
思路：
1.找出最小公倍数
2.用dp
代码：
def gbs(x, y):
a, b = x, y
while b:
a, b = b, a % b
# 此时a是最大公约数
return x * y // a
dp=[float("inf") for _ in range(2022)]
dp[0],dp[1]=0,0
for i in range(1,23):
dp[i]=i
for i in range(23,2022):
for j in range(1,22):
dp[i]=min(dp[i],dp[i-j]+gbs(i-j,i))
print(dp[2021])答案：10266837
编程大题
时间显示
题目：
小蓝与朋友共同开发一个基于时间显示的网站。在服务器端,朋友已获取当前系统时间,以整数形式表示,取值范围为从1970年1月1日00:00:00至当前时刻经过的毫秒数。
现由小蓝在客户端展示该时间信息,仅需显示小时、分钟与秒钟部分即可,毫秒数值则予以舍弃。
给定一个整数形式的时间数值,请将其对应的小时、分钟与秒钟结果输出。
输入要求:
输入一行包含一个整数,表示待转换的时间值。
输出要求:
输出格式为HH:MM:SS的形式,其中H代表小时(0-23),MM代表分钟(0-59),SS代表秒(0-59)。当小时、分钟或秒钟数值不足两位时需补前导零以确保格式正确。
样例输入：
46800999
样例输出：
13:00:00
思路：
直接写就完了
代码：
def t(num):
if int(num)<10:
return '0'+str(num)
return num
n=int(input())
n2=n%(24*60*60*1000) # 天数以下
h=n2//(60*60*1000)
m=n2%(60*60*1000)//(60*1000)
s=n2%(60*1000)//(1000)
h,m,s=t(h),t(m),t(s)
print(h,end=':')
print(m,end=':')
print(s,end='')杨辉三角
题目：
下面的图形是著名的杨辉三角形：
如果我们按照从上到下和从左到右的方向将这些数字排列成一列，则会得到以下序列：
1,\ 1,\ 1,\ 1,\ 2,\ 1,\ 1,\ 3,\ 3,\ 1,\ 1,\ 4,\ 6,\ 4,\ 1,
请根据给定的正整数N（记为N），计算并返回结果作为整数值。
输入参数：
- 输入：一个正整数N。
输出参数： - 输出：一个整数值表示答案。
样例输入：
6
样例输出：
13
思路：
[备战蓝桥杯历年试题：杨辉三角形 省赛B组 Python详解_Py小郑的博客-博客]( "备战蓝桥杯历年试题：杨辉三角形 省赛B组 Python详解_Py小郑的博客-博客")
代码：
##左孩子右兄弟
题目：
对于一棵多叉树，我们可以通过“左孩子右兄弟”表示法，将其转化成一棵二叉树。
如果我们认为每个结点的子结点是无序的，那么得到的二叉树可能不唯一。换句话说，每个结点可以选任意子结点作为左孩子，并按任意顺序连接右兄弟。
给定一棵包含N个结点的多叉树，结点从1至N编号，其中1号结点是根，每个结点的父结点的编号比自己的编号小。请你计算其通过“左孩子右兄弟”表示法转化成的二叉树，高度最高是多少。注：只有根结点这一个结点的树高度为0。
输入格式：
输入的第一行包含一个整数N。
以下N-1行，每行包含一个整数，依次表示2至N号结点的父结点编号。
输出格式：
输出一个整数表示答案。
样例输入：
5
1
1
1
2
样例输出：
4
思路：
无法
代码：
##异或数列
题目：
Alice 和 Bob 正在玩一个异或数列的游戏。游戏开始时他们各自拥有一个整数 a 和 b 都初始化为 0。
给定一个长度为 n 的公共数列 X₁, X₂, ⋯, Xₙ。
Alice 和 Bob 轮流进行操作 Alice 先手 每次可以选择以下两种操作之一：
- 从数列中选择一个 Xᵢ 将其与 Alice 的 a 进行异或运算 令 a 变为 a ⊕ Xᵢ（其中 ⊕ 表示按位异或）
- 从数列中选择一个 Xᵢ 将其与 Bob 的 b 进行异或运算 令 b 变为 b ⊕ Xᵢ
每个 Xᵢ 只能使用一次 当所有 Xi 均被使用完（n 轮后）游戏结束。
游戏结束时 拥有数值较大的一方获胜 若双方数值相同则平局。
假设双方都采取最优策略 现在问题是 Alice 能赢吗？
输入格式
输出格式
输入输出样例
解释
样例输入：
4
1 1
1 0
2 2 1
7 992438 1006399 781139 985280 4729 872779 563580
样例输出：
1
0
1
1
思路：
代码：
##括号序列
题目：
考虑给定的一个左中缀表达式S = s₁ s₂ ... sn由圆括号组成，请计算所有本质上不同的附加方案的数量。其中每个附加方案都是通过在适当的位置插入圆括号对使得S成为一个有效的表达式。两个方案被认为是本质上相同的当且仅当对于每一个插入位置i，在第一个方案中插入左圆 bracket 而在第二个方案中没有插入左圆 bracket；或者在第一个方案中没有插入右圆 bracket 而在第二个方案中有插入右圆 bracket 两种情况之一成立。
例如，在这种情况下共有5种本质上不同的附加方案。
具体来说，在这种情况下共有5种本质上不同的附加方案。
假设初始的左右括号排列情况如图所示，请计算完成这些附加后的有效表达式的数量模1e9+7的结果。
样例输入：
（（（）
样例输出：
5
思路：
还是不会，这年题太难了！
代码：
##