美团2024年春招第一场笔试【技术】第五题：小美的区间删除

题目如下：

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

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 256M，其他语言512M

输入描述：

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

输出描述：

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

示例1

输入例子：

5 2
2 5 3 4 20

输出例子：

4

例子说明：

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

题解直接写到代码注释里面了，我的滑窗解法基本是最优解，但在取元素的次数上可能会多于网上看见的一种非常巧妙的提前移入再删除的滑窗Python解法，放到我的代码后面了。

#include <iostream>
#include <utility>
#include <vector>
using namespace std;
/* 多个整数数相乘后末尾的0的个数完全等于所有数能够拆解出的因数2和因数5的组数，所以只需获取每个数能够拆解的2和5的次数，而后根据需要的0个数来保留足够多的2和5组数。
使用移动窗格逐步得到所有可删除区间对应的最长区间，最后算出每个区间的组合种数即可。
种数计算时由于新最长区间可能和上一最长区间有重合部分，所以需要减去重合部分区间的组合种数。
至于一个区间长为m的组合种数，实际上就是m到1的循环递减相加，即f(m)=1+2+...+n */

//计算len长度的区间在有coincidence长度的重合下的方案数，必须使用长整形，int可能溢出
inline long long F_CalcScheme(long long len, long long coincidence)
{
    if (coincidence > 0) { //新区间和上一区间重合
        return len*(len+1)/2-coincidence*(coincidence+1)/2;
    }
    else {
        return len*(len+1)/2;
    }
}

int main()
{
    int n, k, a;
    int sum_2 = 0, sum_5 = 0; //输入阶段分别表示所有数中的因数2和因数5的总数，计算阶段表示还能删除多少个2和5
    cin >> n >> k;
    vector<pair<int, int>> vec(n, {0, 0}); //pair的2字段为此数的因数2和因数5的次数
    for (int i = 0; i < n; i++) { //读入数字并分解出因数为2和5的次数
        cin >> a;
        while (!(a%2)) {
            vec[i].first++;
            sum_2++;
            a /= 2;
        }
        while (!(a%5)) {
            vec[i].second++;
            sum_5++;
            a /= 5;
        }
    }

    sum_2 -= k; //得到可删除的2和5的个数
    sum_5 -= k;
    if (sum_2 < 0 || sum_5 < 0) { //如果没有足够组数则无法删除
        cout << 0;
        return 0;
    }
    long long res = 0;
    int l = 0, r = 0, pre_r = 0; //可删除区间的左下标和右下标+1，以及前一个区间的r
    while (r < n) { //遍历数组直到出界
        int temp_2 = sum_2-vec[r].first, temp_5 = sum_5-vec[r].second;
        if (temp_2 >= 0 && temp_5 >= 0) { //可以再在区间右侧多删一个数，此处可以循环添加到无法添加为止
            sum_2 = temp_2;
            sum_5 = temp_5;
            r++;
        }
        else {
            if (l != r) { //目前区间有长度，则移除区间左侧已经删除的一个数
                if (pre_r != r) { //计算此区间的方案数并更新pre_r。此处的情况是当前区间右侧无法再添加删除的元素，并且r不同于上一个区间，即表示这是一个新区间
                    res += F_CalcScheme(r-l, pre_r-l);
                    pre_r = r;
                }
                sum_2 += vec[l].first;
                sum_5 += vec[l].second;
                l++;
            }
            else { //区间为空则继续查看右侧其它的数
                l++;
                r++;
            }
        }
    }
    if (l != r) { //上述循环完成后可能有2种情况，一个是右侧添加新的删除元素时出界，另一个是区间为空的情况下右移出界，这里需要再加上情况1的方案数
        res += F_CalcScheme(r-l, pre_r-l);
    }
    cout << res;
}

更加巧妙的解法，它是先移入右侧元素直到移入第一个不能被删除的元素，这期间进行加窗格长度的操作，而后再移出左侧元素直到窗格合理或为空。这种做法可能会减少执行取元素的次数，但逻辑上看似简单实则晦涩：

n, k = map(int, input().split())
arr = list(map(int, input().split()))

# n, k = 5, 2
# arr = [2, 5, 3, 4, 20]

# 统计数组中各个数字的2/5的因子总数
cnt2 = [0] * n
cnt5 = [0] * n
for i in range(n):
    while arr[i] % 2 == 0:
        arr[i] //= 2
        cnt2[i] += 1
    while arr[i] % 5 == 0:
        arr[i] //= 5
        cnt5[i] += 1

all2, all5 = sum(cnt2), sum(cnt5)
# 双指针
left = ans = 0
for right in range(n):
    all2 -= cnt2[right]
    all5 -= cnt5[right]
    while left <= right and min(all2, all5) < k:
        all2 += cnt2[left]
        all5 += cnt5[left]
        left += 1
    ans += right - left + 1
print(ans)