"Inference"

NC220775. "Inference"

描述

给定n个正整数： $a_{1},a_{2},\cdots，a_{n}$ ，如果你认为存在 $t\geq1$ ，使得序列中有连续的 t 个数的和能被 n 整除，那么请输出最大的 t 的值，如果你认为不存在这样的 t ，那么就请输出-1。

输入描述

输入一共两行；
第一行一个正整数 
第二行 n个正整数： 。

输出描述

一个整数，如果你认为存在这样的 t ，那么输出最大的 t ，否则输出-1。

示例1

输入:

7
2 4 6 3 5 5 6

输出:

说明:

其中 6+3+5=14，能被 7整除，并且也只有这一个子序列，所以这也是最大的，所以就输出它的长度是 3。

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++11) 解法, 执行用时: 410ms, 内存消耗: 32316K, 提交时间: 2021-04-10 14:34:12

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,ans,a[N];
unordered_map<int,int>mp;
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) 
	{
		scanf("%d",&a[i]);
		a[i]=(a[i]+a[i-1])%n;
		if (a[i]==0) ans=i;
		if (!mp[a[i]]) mp[a[i]]=i;
		else ans=max(ans,i-mp[a[i]]);
	}
	printf("%d",ans); 
	return 0;
}

上一题

下一题

详情