【蓝桥杯python组】【2021年第十二届省赛填空题】【2】
文章目录
- 货物摆放
- 最短路径问题
- 回路计数
货物摆放
小蓝拥有一处极大容量的仓库，在这里可以存放大量的货物。为了提高空间利用效率，小蓝规定了一套严格的仓储规则：确定了长、宽、高三个互相垂直的方向，并要求每箱货物的边必须与之平行。所有货物最终应当堆叠成一个大长方体：在长、宽、高的方向上分别堆叠L箱、W箱和H箱货物（即在长、宽、高的方向上分别堆L, W, H个箱子），使得n = L \times W \times H成立。给定n值，请计算满足条件的不同堆放方案总数是多少？例如，在n=4时有6种不同的堆放方式：(1, 1, 4), (1, 4, 1), (4, 1, 1), (1, 2, 2), (2, 1, 2), (2, 2, 1)。请问当n = \texttt{2021041820210418}（这是一个由十六位数字组成的数值）时共有多少种不同的堆放方案？
答案：2430
解题思路：采用暴力分解法。
通过多层循环结构实现求解。
计算量较大。
但其思维方式较为直接。
解题思路：采用暴力分解法。
通过多层循环结构实现求解。
计算量较大。
但其思维方式较为直接。
import os
import sys
# 请在此输入您的代码
n=2021041820210418
a=[]
i=1;
while i*i<=n: #找出所有因子
if n%i==0:
a.append(i)
if n/i!=i:
a.append((n/i));
i=i+1
cnt=0
for i in range(len(a)):
for j in range(len(a)):
if a[i]*a[j]<=n :
for k in range(len(a)):
if a[i]*a[j]*a[k]==n:
cnt=cnt+1;
print(cnt)最短路径问题
_2. 小蓝在学习完最短路径后感到非常开心,他设计了一个独特的图,并致力于探索该图中的最短路径问题。这个图包含连续编号从1到2021的共2021个节点。对于任意两个不同的节点a和b,如果它们之间的编号差超过21,则这两个节点之间没有连接;反之,则以它们编号最小公倍数为长度的无向边相连。例如:节点1与节点23之间没有连接;而节点3与节点24之间存在一条无向边,其长度为精确计算得出的具体数值;同样地,节点15与节点25之间也有一条无向边,其长度为75。
请计算出从节点1到节点2021之间的最短路径总长度是多少。
答案：10266837
解题思路：
无向边的长度LCM=(a*b)/ [a和b的最大公约数]
由于蓝桥杯是闭卷，也就是不让带参考材料，很多人记不住Dijkstra算法,或者比赛的时候一紧张写错了，导致跑出来的答案差了那么一丢丢，就很尴尬了。考虑这道题是填空题，那么不需要在规定时间内完成，那么简单好记的粗暴算法 Floyd就纳入我们的选择。为什么说 Floyd 算法粗暴，因为他用的是DP 的思想，复杂度高达 O(n^3）。
#方法一：Floyd
import math
def lcm(a, b):
return int(a * b / math.gcd(a, b))
n = 2021
g = [[0 for i in range(1, n + 2)] for j in range(1, n + 2)]
for i in range(1, n + 1):
for j in range(1, n + 1):
if i == j:
g[i][j] = g[j][i] = 0
elif abs(i - j) <= 21:
g[i][j] = g[j][i] = lcm(i, j)
else:
g[i][j] = 1000000000
for k in range(1, n + 1):
for i in range(1, n + 1):
for j in range(1, n + 1):
if g[i][j] > g[i][k] + g[k][j]:
g[i][j] = g[i][k] + g[k][j]
print(g[1][n])
#方法二：Dijkstra
import os
import sys
import math
n=2021
def lcm(i,j):
return i*j/math.gcd(i,j);
dp=[float('inf')] * (n+1)
dp[1]=0
for i in range(1,n):
for j in range(i+1,i+22):
if j>n:
break
dp[j]=min(dp[j],dp[i]+lcm(i,j))
print(int(dp[n])) #题目要求代码为int类型回路计数
_3、蓝桥学院拥有编号为1至21的教学楼共21幢。对于任意两幢教学楼a和b, 当且仅当a和b互质时,二者之间有一条直接相连的走廊;否则这两幢教学楼之间没有直接连接的走廊。小蓝目前位于第一幢教学楼,并计划依次参观所有其他teaching buildings exactly once before returning to the first building (i.e., seeking the number of distinct Hamiltonian circuits).
两个行程方案被认为是不同的,如果存在一个特定的教学楼编号i,在这两次行程中完成第i号之后前往的是不同的下一号。
答案：881012367360
解题思路：采用状压动态规划方法。考虑到教学楼的数量较少，在程序实现中我们用一个21位的二进制数来表示教学楼的状态。其中每一位对应一幢教学楼的状态信息：若第k位为1，则表示第k幢教学楼已经被访问过；若第k位为0，则表示第k幢教学楼尚未被访问过。在此基础上定义动态规划状态dp[i][j]为当前状态下达到状态i且最后访问过的教学楼是j的方案总数。那么状态转移方程可表示为：dp[i | (1 << k)][j] += dp[i][j]（其中i与第k位无交集且存在从j到k的教学路径）。需要注意的是，在程序实现时请确保代码中使用long long类型来处理数值。
import math
dp = [[0] * (22) for i in range(2100000)]
g = [[0 for i in range(22)] for i in range(22)]
n = 1 << 21
for i in range(1, 22):
for j in range(1, 22):
if math.gcd(i, j) == 1:
g[i - 1][j - 1] = g[j - 1][i - 1] = 1
dp[1][0] = 1
i = 1
while i < n:
for j in range(0, 21):
if (i >> j & 1) == 0:
continue
for k in range(0, 21):
if g[j][k] == 0 or (i >> k & 1) != 0:
continue
dp[(i + (1 << k))][k] += dp[i][j]
i += 1
res = 0
for i in range(0, 21):
res += dp[n - 1][i]
print(res)蓝桥杯python组
第十二届Python编程组
如有错误之处还请多多指教~