NC24021. [USACO 2016 Jan S]Subsequences Summing to Sevens
描述
输入描述
The first line of input contains N (1≤N≤50,000). The next N lines each contain the N integer IDs of the cows (all are in the range 0…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.
You may want to note that the sum of the IDs of a large group of cows might be too large to fit into a standard 32-bit integer. If you are summing up large groups of IDs, you may therefore want to use a larger integer data type, like a 64-bit "long long" in C/C++.
示例1
输入:
7 3 5 1 6 2 14 10
输出:
5
说明:
In this example, 5+1+6+2+14 = 28.Java 解法, 执行用时: 135ms, 内存消耗: 16168K, 提交时间: 2023-07-29 07:43:03
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int[] IDs = new int[n+1];
for(int i=0; i<n; i++) {
st = new StringTokenizer(br.readLine());
IDs[i+1] = IDs[i]+Integer.parseInt(st.nextToken());
IDs[i+1] %=7;
}
int maxSize = 0;
for(int i=0; i<7; i++) {
int start=0;
int end=0;
for(int j=1; j<n+1; j++) {
if(IDs[j]==i) {
start=j;
break;
}
}
for(int j=n; j>0; j--) {
if(IDs[j]==i) {
end=j;
break;
}
}
maxSize=Math.max(maxSize, end-start);
}
bw.write(maxSize+"\n");
bw.flush();
}
}
C++ 解法, 执行用时: 18ms, 内存消耗: 400K, 提交时间: 2022-06-29 16:25:42
#include<bits/stdc++.h>
using namespace std;
int n,f[8],t,ans;
long long s,y;
int main()
{
memset(f,-1,sizeof(f));
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>t;
s+=t;
y=s%7;
if(f[y]==-1)
{
f[y]=i;
}
else
{
ans=max(ans,(i-f[y]));
}
}
cout<<ans;
return 0;
}