欧拉计划 Problem 8

欧拉计划 Problem 8

 思路：

对于如此长的数据，第一反应是用字符串来存储，这里介绍一种方法叫滑动窗口法。

由于这里是求固定的13个数字的乘积，则可以想出：

1 先固定住13个数字的乘积这里用变量now来记录

2 每向前遍历一个数字str[i]，则now = now *  str[i]

3 由于要维护这个13的固定窗口，所以我们还要 now /= str[i - 13]，不断更新乘积的最大值

4 直至遍历完为止

注意：

1 如果我们向前遍历的数字为0时，则不能继续执行上面的第三步（前面计算的乘积可能是最大的，并且之后的乘积都为零），从窗口出去的数字为0，执行上面的第三步会报错（除数不能为0）

2 所以可以设置一个zero_cnt，只有为0时我们才更新答案

3 向前遍历的数字为0，则zero_cnt++

4 从窗口出去的数字，则zero_cnt--

#include 
using namespace std;

char str[1005];

int main() {
    cin >> str;
    long long ans = 0, zero_cnt = 0, now = 1;
    for (int i = 0; i < 1000; i++) {
        if (i < 13) {
            now *= str[i] - '0';
        } else {
            if (str[i] == '0') {
                zero_cnt++;
            } else {
                now *= str[i] - '0';
            }
            if (str[i - 13] == '0') {
                zero_cnt--;
            } else {
                now /= str[i - 13] - '0';
            }
        }
        if (zero_cnt == 0) {
            ans = max(ans, now);
        }
    }
    cout << ans << endl;
    return 0;
}