<>A卡片

cards = [2021]*10 i = 1 while True: s = str(i) for j in s: cards[int(j)] -= 1
flag= False for j in cards: if j < 0: flag = True break if flag: break i += 1
print(i-1) # 3181
<>B直线

cnt = 0 dots = [(i, j) for i in range(20) for j in range(21)] # 生成所有点 lines =
set() for i in range(len(dots)): for j in range(i+1, len(dots)): if dots[j][0]-
dots[i][0] != 0: x1, x2 = dots[i][0], dots[j][0] y1, y2 = dots[i][1], dots[j][1]
k= (y2-y1)/(x2-x1) b = (y1*(x2-x1)-x1*(y2-y1))/(x2-x1) # 这么写不会炸精度 lines.add((k,
b)) print(len(lines)+20) # 40257
<>C货物摆放

from math import * n = 2021041820210418 cnt = 0 fac = [] for i in range(1, int(
sqrt(n))+1): if n % i == 0: fac.append(i) fac.append(n//i) for i in fac: for j
in fac: for k in fac: if i*j*k == n: cnt += 1 print(cnt) # 2430
<>D路径

from math import * n = 2021 vis = [False]*(n+1) dis = [float('inf')]*(n+1)
graph= [[float('inf') for i in range(n+1)] for j in range(n+1)] for i in range(1
, n+1): for j in range(1, n+1): if abs(i-j) > 21: continue graph[i][j] = lcm(i,
j) dis[1] = 0 while True: point = 0 for i in range(1, n+1): if (not vis[i]) and
dis[i] < dis[point]: point = i if point == 0: break vis[point] = True for i in
range(1, n+1): if dis[i] > dis[point]+graph[point][i]: dis[i] = dis[point]+graph
[point][i] print(dis[n]) # 10266837
<>E回路计数

答案:881012367360

思路:状压dp,不会dp位操作的建议先看一下位操作

先用一个邻接矩阵e来表示某两个教学楼之间能否通行,e[i][j]=True表示i号和j号可以通行,否则不能通行。利用gcd函数求出两个数的最大公因数(原理为广义欧几里得除法),若为1代表互质,即可以通行。

设置一个二维数组f,f[i][j]表示在状态i下从1号到j号的方案数。这里解释一下状态的含义:一共21个教学楼,对应21个二进制位,某一位为1表示访问对应的教学楼,否则为不访问,易知状态i最大取值为
2 21 − 1 2^{21}-1221−1。

由于1号和其他所有号都互质,所以1号和其他所有都联通。题目要求从1号出发走遍所有教学楼最终再回到1号,也就是状态i的所有二进制位上都是1,十进制就是 2
21 − 1 2^{21}-1221−1,不妨记为a。回到1号我可以从2号返回,也可从3号,4号,……,21号返回。那么最终方案总数就是这20种返回的累加和:

∑ j = 2 21 f [ a ] [ j ] \sum_{j=2}^{21}f[a][j] j=2∑21​f[a][j]

对于某一个特定的状态i,21个二进制位上有0有1。对于其中每一位的1,代表访问对应的教学楼,那么是从哪个教学楼来到这个教学楼的呢?自然是从其他为1的位对应的教学楼,前提是这两个教学楼要联通,这就要用到前面的邻接矩阵e了,后面表述为了方便省略了联通的前提。所以状态转移时,f[i][j](j代表了i的某一位上的1所对应的教学楼的编号)要加上其他所有为1的位的f[i][j](这个j和前面的j不是同一个,它代表了其他为1的二进制位所对应的教学楼编号)。对于某一状态i,其中每一个二进制位1都有可能是从其他为1的为过来的,所以要遍历状态i二进制的所有1,对每一位1都进行上述状态转移操作。

代码如下,跑起来略慢:
def gcd(x, y): if x % y == 0: return y return gcd(y, x % y) n = 21 m = 1 << n e
= [[False]*n for _ in range(n)] # 1-21的编号映射成0-20 f = [[0]*n for _ in range(m)]
# f[i][j]表示在状态i下从1号到j号的方案数 # 状态指二进制下对应位的教学楼访问与否,转成十进制即为状态i for i in range(n):
for j in range(n): if gcd(i+1, j+1) == 1: e[i][j] = True f[1][0] = 1 #
初始化,在状态1下从第0个教学楼到第0个教学楼的方案数为1 for i in range(1, m): for j in range(n): if (i >>
j) & 1 == 1: # 确保该状态是访问j号的 for k in range(n): if ((i-(1 << j)) >> k) & 1 == 1
and e[k][j]: f[i][j] += f[i-(1 << j)][k] ans = 0 for i in range(1, n): ans += f[
m-1][i] print(ans) # 881012367360
<>F时间显示

time = int(input()) time %= 24*60*60*1000 h = time//(60*60*1000) time -= h*60*
60*1000 m = time//(60*1000) time -= m*60*1000 s = time//1000 print(
"{:0>2d}:{:0>2d}:{:0>2d}".format(h, m, s))
<>G杨辉三角形

def generate(tri): tmp = [1] for i in range(len(tri)-1): tmp.append(tri[i]+tri[
i+1]) tmp.append(1) return tmp n = int(input()) res = 0 tri = [1] while True: if
nin tri: res += tri.index(n)+1 break res += len(tri) tri = generate(tri) print(
res) # 运行超时,40分
<>H左孩子右兄弟

可能有以下 3 种 (这里只列出 3 种,并不是全部) 不同的 “左孩子右兄弟” 表示:

n = int(input()) tree = [[] for i in range(n+1)] for i in range(2, n+1): tree[
int(input())].append(i) def dfs(i): if len(tree[i]) == 0: return 0 maxn = 0 for
jin tree[i]: maxn = max(maxn, dfs(j)) return len(tree[i])+maxn print(dfs(1)) #
90分
<>I异或数列

<>J括号序列

技术
今日推荐
阅读数 7246
阅读数 2080
阅读数 1522
阅读数 1330
阅读数 1311
阅读数 1134
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信