关注
第四题
其实是先看的第五题,回来看了半天没思路,想了想肯定会有方案数为0的情况,结果能过45%...
n, k = map(int, input().split())
a = [0] + list(map(int, input().split()))
1. dp[i][j] 表示枚举到数组前i位,删了j个数的方案数
2. 正难则反,用总方案数C(n, k)减去删除后不为倍数的方案, 算贡献
dp = [[0] * (k + 1) for _ in range(n + 1)]
MOD = 10 ** 9 + 7
now = 0
for i in range(n):
ok = 0
for j in range(n):
if i == j:
continue
else:
temp = math.gcd(a[i], a[j])
if temp == a[i] or temp == a[j]:
ok = 1
break
if ok:
if now < k:
dp[i][now + 1] *= dp[i - 1]
else:
if now < k:
dp[i][now + 1] = 0
print(dp[n][k])
注释是赛时的思路,但都没推出来,整份代码其实就是变着花样的print(0)
第五题
看着很有思路,一通乱敲,过样例了!好!提交!0%!遂怒,猜了个n/2看看能过多少,结果全过了,你这数据比上午的东子都水啊。。。
# 好像代码没存,总之硬模拟了一下
print(n // 2)
2
相关推荐
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 在大厂上班是一种什么样的体验 #
14334次浏览 195人参与
# 工作前VS工作后,你的心态变化 #
38384次浏览 267人参与
# 论秋招对个人心气的改变 #
15362次浏览 214人参与
# 从mentor身上学到了__ #
55537次浏览 886人参与
# 程序员找工作至少要刷多少题? #
23203次浏览 293人参与
# 我的省钱小妙招 #
37545次浏览 446人参与
# 机械人避雷的岗位/公司 #
44690次浏览 316人参与
# 为了减少AI幻觉,你注入过哪些设定? #
7174次浏览 201人参与
# 你的mentor是什么样的人? #
51481次浏览 730人参与
# 通信/硬件求职避坑tips #
139881次浏览 1086人参与
# 毕业论文进行时 #
27612次浏览 153人参与
# 牛客AI体验站 #
8983次浏览 223人参与
# 我和mentor的爱恨情仇 #
106575次浏览 957人参与
# 运营来爆料 #
77380次浏览 467人参与
# 你现在会用到哪些AI技能? #
24763次浏览 137人参与
# 应届生进小公司有什么影响吗 #
118718次浏览 1162人参与
# 找实习多的是你不知道的事 #
1789143次浏览 20670人参与
# 运营人的第一份offer应该如何选 #
218882次浏览 1260人参与
# 第一次找实习,我建议__ #
71229次浏览 846人参与
# 我现在比当时_,你想录用我吗 #
10013次浏览 140人参与