小美的区间删除

[编程题]小美的区间删除

热度指数：1222 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小美拿到了一个大小为 $n$ 的数组，她希望删除一个区间后，使得剩余所有元素的乘积末尾至少有 $k$ 个 0。小美想知道，一共有多少种不同的删除方案？

输入描述:

第一行输入两个正整数。
第二行输入个正整数，代表小美拿到的数组。

输出描述:

一个整数，代表删除的方案数。

示例1

输入

5 2
2 5 3 4 20

输出

说明

第一个方案，删除[3]。
第二个方案，删除[4]。
第三个方案，删除[3,4]。
第四个方案，删除[2]。

算法知识视频讲解

Python

牛萧犇

n, k = map(int, input().split())
li = list(map(int, input().split()))
numli = []

for x in li:
    t = x
    a = b = 0
    while t % 2 == 0&nbs***bsp;t % 5 == 0:
        if t % 2 == 0:
            t //= 2
            a += 1
        if t % 5 == 0:
            b += 1
            t //= 5
    numli.append((a, b))
# print(numli)
sm2 = [0] * (n + 1) # 求2的数量的前缀和
sm5 = [0] * (n + 1)
for i in range(1, n + 1):
    sm2[i] = sm2[i - 1] + numli[i - 1][0]
    sm5[i] = sm5[i - 1] + numli[i - 1][1]

# print(sm2)
# print(sm5)

i= 0
j = 0
res = 0
while i < n + 1:
    while j < n + 1:
        a2 = sm2[-1] - sm2[j] + sm2[i]
        a5 = sm5[-1] - sm5[j] + sm5[i]
        if min(a2, a5) < k:
            break
        j += 1
    if i >= j:
        break
    res += j - 1 - i
    i += 1
print(res)

发表于 2024-03-14 08:24:23 回复(2)