2013暑期多校联合训练\第五场 Problem F Magic Pen 6

旧城等待， 2021-11-09 02:36 223阅读 0赞

借鉴：

题意转化一下就是：

给出一列数a\[1\]...a\[n\]，求长度最长的一段连续的数，使得这些数的和能被M整除。

分析：

设这列数前i项和为s\[i\],

则一段连续的数的和 a\[i\]+a\[i+1\]+...+a\[j-1\]+a\[j\]=s\[j\]-s\[i-1\]，

所以这段连续的数的和能被m整除的条件就是 (s\[j\]-s\[i-1\]) % m == 0，

即 s\[j\]%m-s\[i-1\]%m == 0，

因此，只需要每一个余数找使s\[i\]%m等于该余数的最小的i，和s\[j\]%m等于该余数的最大的j，相减即为最长的连续的数的长度。

而M只有10000，余数比较小，方法可行。

Wrong key

c++好像不能用下标是负的数组，要把负数+M加成正的，我错了好久，拙计Add笨~

#include <iostream>
    #include <stdio.h>
    using namespace std;
    
    int a[100001],s[100001],ans,i,j,n,m,l,f[10001][2];
    
    int main()
    {
    	while (scanf("%d%d",&n,&m)!=EOF)
    	{
    		ans=0;
    		memset(s,0,sizeof(s));
    		for (i=1;i<=n;i++)
    			scanf("%d",&a[i]);
    		for (i=1;i<=n;i++)
    		{		s[i]=(s[i-1]+a[i])%m;
    				while (s[i]<0) s[i]+=m;
    		}
    		for (i=0;i<m;i++)
    		{
    			f[i][0]=1000000;
    			f[i][1]=-1000000;
    		}
    		for (i=0;i<=n;i++)
    		{
    			if (i<f[s[i]][0]) f[s[i]][0]=i;
    			if (i>f[s[i]][1]) f[s[i]][1]=i;
    		}
    		for (i=0;i<m;i++)
    			if ((f[i][1]-f[i][0])>ans)
    				ans=f[i][1]-f[i][0];
    		printf("%d\n",ans);
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，223人围观）

还没有评论，来说两句吧...

相关阅读

相关 2019牛客暑期多校训练营（第五场）B generator 1

[传送门][Link 1] 题意：先输入X0,X1,a,b然后按照Xi=a\X(i-1)+b\X(i-2) (i>=2) 之后再输入n，mod，让你根据公式求X

ゝ一纸荒年。/ 2023年10月11日 09:30/ 0 赞/ 31 阅读

相关 2019牛客暑期多校训练营（第四场）

Contest Info -------------------- [Contest Link][] <table> <thead> <tr> <t

淡淡的烟草味﹌/ 2023年06月04日 11:58/ 0 赞/ 142 阅读

相关 2013暑期多校联合训练\第三场\Problem H

虽然题解说是简单题，但是本弱菜还是花了很长时间才订正好。咨询了一位大神，在此先表示感谢。题解说的O（3^N）的方法没学会，现在有种O（2^N\M），M为

灰太狼/ 2021年12月02日 01:36/ 0 赞/ 218 阅读

相关 2013暑期多校联合训练\第三场\Problem G

简单题，发出来纪念一下，我一开始还用了高精度的额比经历。一开始用int64没有把运算的两个数都定义成int64，后来测了个10^9就跪了，以为范围不够，以后谨

向右看齐/ 2021年12月01日 15:54/ 0 赞/ 243 阅读

相关 2019牛客暑期多校训练营（第一场）

Solutions -------------------- A：Equivalent Prefixes 题意：若$\\text\{RMQ(u,l,r)=RM

约定不等于承诺〃/ 2021年11月27日 04:44/ 0 赞/ 477 阅读

相关 2013暑期多校联合训练\第四场\Problem H Hehe

水题，发一下，凑数 (\^\_\_^\) 统计一下每一部分的he数就好，规律是斐波那契数列，后来每一个部分相乘得解。

小咪咪/ 2021年11月26日 10:14/ 0 赞/ 204 阅读

相关 2013暑期多校联合训练\第五场 Problem F Magic Pen 6

借鉴：题意转化一下就是：给出一列数a\[1\]...a\[n\]，求长度最长的一段连续的数，使得这些数的和能被M整除。分析：设这列数前i项和为s\[i\],

旧城等待，/ 2021年11月09日 02:36/ 0 赞/ 224 阅读

相关 2019牛客暑期多校训练营第六场

题目链接：[https://ac.nowcoder.com/acm/contest/886\question][https_ac.nowcoder.com_acm_contes

今天药忘吃喽~/ 2021年11月02日 13:38/ 0 赞/ 388 阅读

相关 2019牛客暑期多校训练营（第五场）C - generator 2 (BSGS)

[题目链接][Link 1] 题意：给定\\(n,x\_0,a,b,p\\)，有递推式\\(x\_i = (a \\cdot x\_\{i-1\} +b)\\%p

我不是女神ヾ/ 2021年10月29日 07:48/ 0 赞/ 262 阅读

相关 2019牛客暑期多校训练营（第五场）

比赛链接：[https://ac.nowcoder.com/acm/contest/885\question][https_ac.nowcoder.com_acm_contes

左手的ㄟ右手/ 2021年10月26日 18:24/ 0 赞/ 392 阅读