洛谷 P3131 [USACO16JAN]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。

输入格式

The first line of input contains NN (1 leq N leq 50,0001≤N≤50,000). The next NN

lines each contain the NN integer IDs of the cows (all are in the range

0 ldots 1,000,0000…1,000,000).

输出格式

Please output the number of cows in the largest consecutive group whose IDs sum

to a multiple of 7. If no such group exists, output 0.

思路

是不是觉得还是不理解？

没关系！本蒟蒻来发一篇所有蒟蒻都可以看懂的题解！

首先：

这个题肯定不能直接模拟，你要是暴力枚举端点，看看数据范围。。。。50000^3 下辈子都过不去

然后:

我们就想到了一个求区间和的好东西：

当然是 “前缀和” 了啊！

我们只要先预处理前缀和，然后用pre[r]-pre[l]就是区间和了，这样只要再那他%7就可以判断了，最后求最大长度就可以了！

发现不行。。。。n^2的复杂度啊。。。预计得分70。

改思路！

我们可以先直接求%7意义下的前缀和，然后只要看看余数的重复就可以了。

这里需要用到一个小定理：若两个数相减%7==0,那么这两个数%7的余数一定相同！！（很好证明，自己有兴趣不妨去试试证明）

这样的话瞬间就简单了我们只要求出相同的一个余数第一次和最后一次之间的长度即是最长长度！但是我们不知道哪个余数最长，所以：枚举0~6 共7个余数各自的最长长度，再在他们7个里找最长的！

代码:

#include <bits/stdc++.h>

using namespace std;

#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
typedef long long ll;
const int N = 5e4 + 10;

int n, a[N], first[N], last[N];

int main() {
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		a[i] = (a[i] + a[i - 1]) % 7;
	}
	for (int i = n; i >= 1; i--) first[a[i]] = i;
	for (int i = 1; i <= n; ++i) last[a[i]] = i;
	int res = 0;
	for (int i = 0; i < 6; ++i) res = max(res, last[i] - first[i]);
	cout << res;
    return 0;
}