洛谷P3131 Subsequences Summing to Sevens S

题目大意

给你\(n\)个数，分别是\(a[1],a[2],...,a[n]\)。求一个最长的区间\([x,y]\)，使得区间中的数\(a[x],a[x+1],a[x+2],...,a[y-1],a[y]\)的和能被7整除。输出区间长度。若没有符合要求的区间，输出0。

分析

由题目最先想到使用前缀和算法，枚举区间的左右端点，并更新最大值。题目数据范围\(N (1 \leq N \leq 50,000)\)如果采用直接枚举端点\(O(n^2)\)的时间复杂度基本是要挂的。下面针对暴力方法一步一步进行优化。

原始的暴力代码

int len = -1;
for (int i = 1; i <= n; i ++)
    for (int j = i + 1; j <=n; j ++)
        if ((s[j]-s[i-1]) % 7 == 0) len = max(len, s[j]-s[i-1])

​ 之后仔细观察发现，由于所求的是区间长度的最大值，所以内层循环可以从\(n\)开始想前枚举，遇到可以除尽7的情况\(break\)即可。但是这么做只能从60分变到70分。

70分暴力

int len = -1;
for (int i = 1; i <= n; i ++)
    for (int j = n; j > i; j --)
        if ((s[j]-s[i-1]) % 7 == 0) { len = max(len, j-i+1); break; }

进行到目前为止，已经意识到必须改变方法了。这里要用到一个关于\(mod\)运算的小定理

如果\((a - b) \mod k == 0\) 则\(a\mod k = b \mod k\)

通俗的来讲就是两个数相减可以除尽一个数，那这两个数除这个数的余数一定相等

​ 那我们只需要计算所有前缀和对除7的余数，将余数相同的前缀和下标，从小到大的放在vector数组中，由于是从小到大，所以只需要将最后一个下标减去第一个下标即可。

需要注意的几个事情

1. 最后结果直接就是下标相减不要加一，因为由上面暴力解法可知，下标相减就是\(j-i+1\)
2. 一定要注意加上h[0].push_back(0)如果没有这句会少一种情况。
3. vector数组并不是每一中余数都相等，所以有的余数对应的数组size是0，一定要注意，否则会造成数组越界，一定要在看见数组中出现a[i-1]这种情况时考虑是不是会造成数组越界

附上完整AC代码

#include<bits/stdc++.h>
using namespace std;

const int N = 50010;
int a[N], n;
long long s[N];
vector<int> h[20];

int main ()
{
    cin >> n;
    for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    h[0].push_back(0);
    for (int i = 1; i <= n; i ++) {
        s[i] = s[i-1] + a[i];
        h[s[i] % 7].push_back(i);
    }

    int len = -1;
    for (int i = 0; i < 7; i ++) {
        int l = h[i].size();
        if (!l) continue;
        len = max(h[i][l-1] - h[i][0], len);
    }

    if (len == -1) cout << 0;
    else cout << len;

    return 0;
}