©2020-2024 ioDraw All rights reserved,
Privacy Policy
<>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∑21f[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括号序列