首页 > 其他 > 详细

[USACO16JAN]子共七Subsequences Summing to Sevens

时间:2018-02-14 15:22:46      阅读:70      评论:0      收藏:0      [点我收藏+]

标签:printf   inpu   vertical   ike   表示   ati   stream   input   过去   

题目描述

Farmer John‘s NNN cows are standing in a row, as they have a tendency to do from time to time. Each cow is labeled with a distinct integer ID number so FJ can tell them apart. FJ would like to take a photo of a contiguous group of cows but, due to a traumatic childhood incident involving the numbers 1…61 \ldots 616 , he only wants to take a picture of a group of cows if their IDs add up to a multiple of 7.

Please help FJ determine the size of the largest group he can photograph.

给你n个数,求一个最长的区间,使得区间和能被7整除

输入输出格式

输入格式:

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

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

0…1,000,0000 \ldots 1,000,00001,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.

输入输出样例

输入样例#1: 复制
7
3
5
1
6
2
14
10
输出样例#1: 复制
5

说明

In this example, 5+1+6+2+14 = 28.

同余的性质

(a mod m) + (b mod m) ≡ a + b (mod m)
(a mod m) - (b mod m) ≡ a - b (mod m)
(a mod m) * (b mod m) ≡ a * b (mod m)

 

给出序列,求出最长的区间,满足区间和为7的倍数
预处理出前缀和
(pre[j] - pre[i ]) mod 7 = 0
=> pre[i] ≡ pre[j] (mod 7)
维护7个值,分别表示模7余0到6的最前d的前缀和
扫一遍过去就行了

 

 1 //2018年2月14日14:15:25
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 const int N = 100001;
 8 int n, a[N], sum[N], last[N], first[N], ans;
 9 
10 int main(){
11     scanf("%d", &n);
12     for(int i=1;i<=n;i++){
13         scanf("%d", &a[i]);
14         sum[i] = (sum[i-1] + a[i]) % 7;
15     }
16     for(int i=1;i<=n;i++)
17         last[sum[i]] = i;
18     for(int i=n;i>=1;i--)
19         first[sum[i]] = i;
20     for(int i=0;i<7;i++)
21         ans = max(ans, last[i]-first[i]);
22     printf("%d\n", ans);
23 
24     return 0;
25 }

 

[USACO16JAN]子共七Subsequences Summing to Sevens

标签:printf   inpu   vertical   ike   表示   ati   stream   input   过去   

原文:https://www.cnblogs.com/sineagle/p/8448354.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号