文章目录

• 货物摆放
• 最短路径问题
• 回路计数

货物摆放

1、小蓝有一个超大的仓库，可以摆放很多货物。现在，小蓝有 nn 箱货物要摆放在仓库，每箱货物都是规则的正方体。小蓝规定了长、宽、高三个互相垂直的方向，每箱货物的边都必须严格平行于长、宽、高。小蓝希望所有的货物最终摆成一个大的长方体。即在长、宽、高的方向上分别堆 L、W、H 的货物,满足 n = L×W×H。给定 n，请问有多少种堆放货物的方案满足要求。例如，当 n = 4时，有以下 6 种方案：1×1×4、1×2×2、1×4×1、2×1×2、2 × 2 × 1、4 × 1 × 1。请问，当 n = 2021041820210418（注意有 16 位数字）时，总共有多少种方案？

答案：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、小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图 中的最短路径。小蓝的图由 2021 个结点组成，依次编号 1 至 2021。对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点 之间没有边相连；如果 a 和 b 的差的绝对值小于等于 21，则两个点之间有一条 长度为 a 和 b 的最小公倍数的无向边相连。例如：结点 1 和结点 23 之间没有边相连；结点 3 和结点 24 之间有一条无向边，长度为 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、蓝桥学院由 21 栋教学楼组成，教学楼编号 1​​ 到 21​​。对于两栋教学楼 a 和 b，当 a 和 b 互质时，a 和 b 之间有一条走廊直接相连，两个方向皆可通行，否则没有直接连接的走廊。小蓝现在在第一栋教学楼，他想要访问每栋教学楼正好一次，最终回到第一栋教学楼（即走一条哈密尔顿回路），请问他有多少种不同的访问方案？
两个访问方案不同是指存在某个 i，小蓝在两个访问方法中访问完教学楼 i 后访问了不同的教学楼。

答案：881012367360

解题思路：状压 dp。由于教学楼的个数很少，我们考虑用一个二进制位数等于 21 的数来表示教学楼的访问状态。对于该二进制数，如果它的第 i 位（二进制下）的值为 1，则表示当前状态下第 i 栋教学楼已经访问过一次了；若它的第 i 位（二进制下）的值为 0，则表示当前状态下第 ii 栋教学楼还未访问。于是可以定义 dp[i][j] 表示当前的状态为 i，最后走到的教学楼为 j 的方案数。那么转移方程为：dp[i + 1 <<k ][j] += dp[i][j]。其中需满足对于状态 i，教学楼 k 并未访问过（即 (i(i>>k&1)=0） 且 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组2021年省赛：
【蓝桥杯python组】【2021年第十二届省赛填空题】【1】

如有错误之处还请多多指教~