P3131 [USACO16JAN]Subsequences Summing to Sevens S

Problem

给一个长度为(n)的序列，求最长连续子序列，满足子序列和是7的倍数。(n le 50000)。

Solution

不难发现先将每个(a_i mod 7)，随后前缀和，令(q_i = sum_{j = 1}^i a_j)。再将(q_i mod 7)。题目转变为求一个二元组((i,j))，使得(q_j - q{i - 1})是0且(j - i + 1)最大。
不难发现可以用桶做，把(q_i mod 7)作为下标，存最大和最小。

# include <bits/stdc++.h>
using namespace std;
const int N = 50005;
int a[N],q[N],n;
int Max[8],Min[8];
int main(void)
{
    scanf("%d",&n);
    memset(Min,0x3f,sizeof(Min));
    memset(Max,0xcf,sizeof(Max));
    for(int i = 1; i <= n; i++) 
    {
        scanf("%d",&a[i]);a[i] %= 7;
        q[i] = q[i - 1] + a[i];
    }
    for(int i = 1; i <= n; i++) 
    {
        q[i] %= 7;
        Max[q[i]] = max(Max[q[i]],i);
        Min[q[i]] = min(Min[q[i]],i);
    }
    int ans = 0;
    for(int i = 0; i < 7; i++) ans = max(ans,Max[i] - Min[i]);
    printf("%d
",ans);
    return 0;
}