22 条题解
-
3逍遥♛子寒 LV 8 @ 2019-06-27 19:55:43
既然它题目要求要最大值,那我们就没必要较真把每个的分数求出来,只求那个最大的最后输出就好QAQ(注意数据hin大!!!)
(贴上代码QvQ)
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
using namespace std;
long long s[10000001],t[10000001],f[10000001],k[10000001];
long long maxn=-999999999,x,ans,n,p;
long long read()
{
long long x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}//快读不解释
int main()
{
n=read(); p=read();
for(int i=1;i<=n;i++)
{
x=read();
if(s[i-1]<0)
s[i]=x;
else
s[i]=s[i-1]+x;
maxn=max(s[i],maxn);
t[i]=maxn%p;
}
ans=f[1]=t[1];
maxn=-999999999;
for(int i=2;i<=n;i++)
{
maxn=max(t[i-1]+f[i-1],maxn);
f[i]=maxn;
if(ans<maxn)
ans=maxn%p;
}
cout<<ans<<endl;
return 0;
} -
32016-10-17 13:00:14@
#include<cstdio>
#include <iostream>
#include<cstring>
#include<algorithm>
using namespace std;
long long d[1000002],a[1000002],max1[1000002],maxf;
int main(void)
{
long long n,p;
cin>>n>>p;
for(int i=0;i<n;i++) scanf("%lld",&a[i]);
max1[0]=d[0]=a[0];
maxf=a[0]*2;
bool ok=0;
for(int i=1;i<n;i++){
d[i]=max(a[i],d[i-1]+a[i]);
max1[i]=max(d[i],max1[i-1]);
if(i!=1)maxf=(max((long long)0,max1[i-1])+maxf);
if(maxf>=1000000000) {maxf%=p;ok=1;}
}
if(ok) printf("%lld\n",maxf%p);
else printf("%lld\n",max(a[0],maxf)%p);
return 0;
} -
12016-11-15 19:23:11@
特征值直接累加,若小于零便重新将累加器赋为零;
观察可知最终结果必定是第一个或最后一个小朋友。
于是加一个判断判断它是第一或最后即可~
P.S. 注意数据有点大,记得开**int64** 或 long long
锑程序在下,请不要中毒。
```pascal
program ChildsNumberex;
var n,p,i,k:longint;
a,b,c:array[1..1000000]of int64;
s,max,maxx:int64;begin
readln(n,p);
for i:=1 to n do read(a[i]);max:=a[1];maxx:=-maxlongint;
s:=0;for i:=1 to n do
begin
s:=s+a[i];
if s>maxx then maxx:=s;
if s<0 then s:=0;b[i]:=maxx;
c[i]:=max;if (i=1)or(b[i]>0) then max:=b[i]+c[i];
if max>c[1] then
begin
max:=max mod p;
k:=233;
end;
end;if k=233 then writeln(c[n] mod p) else writeln(c[1] mod p);
end.
``` -
12013-11-29 13:41:07@
测试数据 #0: Accepted, time = 0 ms, mem = 24228 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 24224 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 24224 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 24224 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 24224 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 24224 KiB, score = 10
测试数据 #6: Accepted, time = 62 ms, mem = 24224 KiB, score = 10
测试数据 #7: Accepted, time = 109 ms, mem = 24224 KiB, score = 10
测试数据 #8: WrongAnswer, time = 280 ms, mem = 24224 KiB, score = 0
测试数据 #9: WrongAnswer, time = 546 ms, mem = 24224 KiB, score = 0
var
a,tz,fs:array[1..1000000] of int64;
n,p,i:longint;
temp,max,maf:int64;begin
readln(n,p);
temp:=0;
max:=-maxlongint;
for i:= 1 to n do
begin
read(a[i]);
temp:=temp+a[i];
if temp>max then max:=temp;
tz[i]:=max;
if temp<0 then temp:=0;
end;
fs[1]:=tz[1];
fs[2]:=tz[1]+fs[1];
max:=tz[1]+fs[1];
if fs[1]>fs[2] then maf:=fs[1]
else maf:=fs[2];
for i:= 3 to n do
begin
temp:=tz[i-1]+fs[i-1];
if temp>max then max:=temp;
fs[i]:=max;
if fs[i]>maf then maf:=fs[i];
end;
if max<0 then begin
write('-');
maf:=abs(maf);
end;
writeln(maf mod p);
end. -
12013-11-23 10:44:48@
##AC代码:##
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN 1000001
using namespace std;
long long init[MAXN],temp1[MAXN],temp2[MAXN],ans[MAXN];
int main()
{
//freopen("number.in","r",stdin);
//freopen("number.out","w",stdout);
memset(temp1,0,sizeof(temp1));
int n,p;
long long maxvalue;
scanf("%d%d",&n,&p);
for(int i=1;i<=n;i++) scanf("%lld",&init[i]);
maxvalue=init[1]; temp1[1]=init[1]; temp2[1]=init[1];
for(int i=2;i<=n;i++){
if(temp1[i-1]>0) temp1[i]=temp1[i-1]+init[i];
else temp1[i]=init[i];
if(temp1[i]>maxvalue) maxvalue=temp1[i];
temp2[i]=maxvalue;
}
ans[1]=temp2[1];
maxvalue=ans[1]+temp2[1];
for(int i=2;i<=n;i++){
if((ans[i-1]+temp2[i-1])>maxvalue) maxvalue=ans[i-1]+temp2[i-1];
ans[i]=maxvalue;
}
if(ans[1]<maxvalue) printf("%lld\n",maxvalue%p);
else printf("%lld\n",ans[1]%p);
return 0;
} -
12013-11-18 21:30:56@
测试结果
测试数据 #0: Accepted, time = 0 ms, mem = 12216 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 12216 KiB, score = 10
测试数据 #2: Accepted, time = 187 ms, mem = 12216 KiB, score = 10
测试数据 #3: Accepted, time = 187 ms, mem = 12216 KiB, score = 10
测试数据 #4: WrongAnswer, time = 187 ms, mem = 12216 KiB, score = 0
测试数据 #5: TimeLimitExceeded, time = 1014 ms, mem = 12216 KiB, score = 0
测试数据 #6: TimeLimitExceeded, time = 1014 ms, mem = 12208 KiB, score = 0
测试数据 #7: TimeLimitExceeded, time = 1014 ms, mem = 12208 KiB, score = 0
测试数据 #8: TimeLimitExceeded, time = 1014 ms, mem = 12212 KiB, score = 0
测试数据 #9: TimeLimitExceeded, time = 1014 ms, mem = 12208 KiB, score = 0
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
int a[1000001],b[1000001],c[1000001];
int n,p;
int maxbefore(int n)
{
int s,maxvalue=-2147483647;
for(int i=1;i<=n;i++){
s=0;
for(int j=i;j<=n;j++){
s+=a[j];
if(s>maxvalue) maxvalue=s;
}
}
return maxvalue;
}
int maxscore(int x)
{
int maxvalue=-2147483647;
for(int i=1;i<=x-1;i++) if(((b[i]+c[i])%p)>maxvalue) maxvalue=(b[i]+c[i])%p;
return maxvalue;
}
int main()
{
scanf("%d%d",&n,&p);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
b[i]=maxbefore(i);
}
c[1]=b[1];
int maxvalue=c[1];
for(int i=2;i<=n;i++){
c[i]=maxscore(i);
if(c[i]>maxvalue) maxvalue=c[i];
}
printf("%d\n",maxvalue);
return 0;
}
这道题我使用纯模拟做的,不知道正确的算法该怎么做! -
02017-11-05 15:18:01@
#include<cstdio> #include <iostream> #include<cstring> #include<algorithm> using namespace std; long long d[1000002],a[1000002],max1[1000002],maxf; int main(void) { long long n,p; cin>>n>>p; for(int i=0;i<n;i++) scanf("%lld",&a[i]); max1[0]=d[0]=a[0]; maxf=a[0]*2; bool ok=0; for(int i=1;i<n;i++){ d[i]=max(a[i],d[i-1]+a[i]); max1[i]=max(d[i],max1[i-1]); if(i!=1)maxf=(max((long long)0,max1[i-1])+maxf); if(maxf>=1000000000) { maxf%=p;ok=1; } } if(ok) printf("%lld\n",maxf%p); else printf("%lld\n",max(a[0],maxf)%p); return 0; }
-
02017-11-05 15:13:45@
急急急
-
02017-11-05 15:13:34@
-
02016-08-13 11:12:24@
坑啊!
```
#include <bits/stdc++.h>
using namespace std;inline int read()
{
int a = 0;
scanf("%d", &a);
return a;
}#define ll long long
#define L 1000005
int n;
ll p;
ll num[L], spc[L], score[L], Lik[L], maxx;int main()
{
memset(num, -127, sizeof num);
memset(spc, -127, sizeof spc);
memset(score, -127, sizeof score);
memset(Lik, -127, sizeof Lik);
n = read(); p = read();
for (int i = 1; i <= n; i++)
num[i] = read();
Lik[1] = spc[1] = num[1];
ll x = num[1]<<1;
bool mark = 0;
for (int i = 2; i <= n; i++) {
Lik[i] = max(Lik[i-1]+num[i], num[i]);
spc[i] = max(Lik[i], spc[i-1]);
if (!mark && num[i] > 0)
x += num[i];
if (!mark && x > num[1])
mark = 1;
}
maxx = score[1] = spc[1];
score[2] = score[1] + spc[1];
for (int i = 3; i <= n; i++)
score[i] = (score[i-1]+max(spc[i-1], 0ll))%p;
if (mark)
maxx = score[n];
if (maxx >= 0)
printf("%lld\n", maxx%p);
else
printf("-%lld\n", (-maxx)%p);
return 0;
} -
02015-10-14 12:25:00@
VAR
I,J,K,M,N,A,P:LONGINT;
x,y,z:int64;
BEGIN
READLN(N,P);
READ(A);
X:=A;//lian xu zui da
Y:=A;//te zheng zui da
IF A<0 THEN Z:=A ELSE Z:=2*A;//hou yi wei fen shu zui da
FOR I:=2 TO N-1 DO
BEGIN
READ(A);
IF X<0 THEN X:=A
ELSE X:=(X+A);
IF X>Y THEN Y:=X;
IF Y>0 THEN Z:=z+y;
END;
writeln(Z mod p);
END. -
02015-08-20 11:35:04@
AC了。好激动。
foo.cpp: In function 'int main()':
foo.cpp:15:148: warning: unknown conversion type character 'l' in format [-Wformat=]
if(ans<now) ans=now; if(now<0) now=0; f=ans; if(i==1) { if(f<0) _max=f,flag=true; max=2*f; max%=mod; } else if(i==n) printf("%lld\n",flag?_max:max); else if(f>0)
^
foo.cpp:15:148: warning: too many arguments for format [-Wformat-extra-args]测试数据 #0: Accepted, time = 0 ms, mem = 484 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 484 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 484 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 488 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 488 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 488 KiB, score = 10
测试数据 #6: Accepted, time = 72 ms, mem = 488 KiB, score = 10
测试数据 #7: Accepted, time = 93 ms, mem = 488 KiB, score = 10
测试数据 #8: Accepted, time = 234 ms, mem = 488 KiB, score = 10
测试数据 #9: Accepted, time = 468 ms, mem = 492 KiB, score = 10
Accepted, time = 897 ms, mem = 492 KiB, score = 100
-
02014-10-08 17:05:29@
唯一的亮点是O(1)的空间......2333 //纪念爆0
#include<cstdio>
int n,mod;
long long f,ans=-0x7fffffff;
int main()
{
long long now=0,_max=0,max=0,_plus=0;
bool flag=false;
scanf("%d%d",&n,&mod);
for(int i=1;i<=n;i++)
{
int tmp;
scanf("%d",&tmp);
now+=tmp;
if(ans<now) ans=now;
if(now<0) now=0;
f=ans;
if(i==1)
{
if(f<0) _max=f,flag=true;
max=2*f;
max%=mod;
}
else if(i==n)
printf("%lld\n",flag?_max:max);
else if(f>0)
{
if(flag) {_plus+=f;if(_plus>-_max) flag=false;}
max+=f;
max%=mod;
}
}
return 0;
} -
02014-08-01 17:35:43@
诚心佩服vijos的速度,要知道smartoj最多wa80...可这儿就ac了
var b,f:array[1..1000000] of int64;
a,i,n,p:longint; j:int64;
begin
read(n,p); read(f[1]); j:=f[1]; b[1]:=f[1];
for i:=2 to n do begin read(f[i]);
if f[i-1]>0 then inc(f[i],f[i-1]);
if f[i]>j then j:=f[i];
b[i]:=j mod p;
end;
j:=b[1]*2;
for i:=2 to n-1 do if b[i]+j>j then j:=b[i]+j;
if j<b[1] then j:=b[1];
write(j mod p);
end. -
02014-05-24 21:22:20@
注意,大多数人可能WA80:
因为,大多数人有可能因数太大的原故,所以导致后面两个极大的数据会出错。所以,应当边做边取余。
所以我们应当把其中的:
for(i=3;i<=n;i++)c[i]=c[i-1]+maxx(b[i-1],0ll);
更改为:
for(i=3;i<=n;i++)c[i]=(c[i-1]+maxx(b[i-1],0ll))%p;
这样就成了。下面是我的AC代码:#include<cstdio>
#include<cstring>
#include<cstdlib>
#define LL long long
using namespace std;
LL maxx(LL x,LL y){return x>y?x:y;}
LL n,p,a[1100000];
LL b[1100000],c[1100000];
int main()
{
int i,j;
scanf("%lld%lld",&n,&p);
for(i=1;i<=n;i++)scanf("%lld",&a[i]);
b[1]=a[1];
LL now=maxx(a[1],0);
for(i=2;i<=n;i++)
{
b[i]=b[i-1];
now+=a[i];
b[i]=maxx(now,b[i]);
if(now<0)now=0;
}
c[1]=b[1],c[2]=c[1]+b[1];
int ok=0;
LL tmp=c[1];
for(i=2;i<n;i++)
{
tmp+=maxx(b[i],0ll);
if(tmp>=0)
{
ok=1;
break;
}
}
for(i=3;i<=n;i++)c[i]=(c[i-1]+maxx(b[i-1],0ll))%p;
if(ok)printf("%d\n",int(c[n]));
else printf("%d\n",int(c[1]%p));
return 0;
}
测试数据 #0: Accepted, time = 0 ms, mem = 26080 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 26076 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 26080 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 26080 KiB, score = 10
测试数据 #4: Accepted, time = 7 ms, mem = 26076 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 26080 KiB, score = 10
测试数据 #6: Accepted, time = 62 ms, mem = 26076 KiB, score = 10
测试数据 #7: Accepted, time = 109 ms, mem = 26080 KiB, score = 10
测试数据 #8: Accepted, time = 343 ms, mem = 26084 KiB, score = 10
测试数据 #9: Accepted, time = 608 ms, mem = 26084 KiB, score = 10
Accepted, time = 1144 ms, mem = 26084 KiB, score = 100 -
02014-04-06 17:11:44@
vijos坑人的!!!
我加了几句注释 就超时
坑坑坑var ans,temp,n,p,max,mm,md:int64;i:longint;
a,b:array[0..1000000]of int64;
begin
readln(n,p);for i:=1 to n do read(a[i]);
ans:=a[1];b[1]:=a[1];max:=(b[1]*2)mod p;
temp:=a[1];mm:=b[1];md:=(b[1]*2) div p;
for i:=2 to n do
begin
if temp<0 then temp:=0;
temp:=(temp+a[i]);
if temp>ans then ans:=temp;
b[i]:=ans;
end;
for i:=2 to n do
if (i<>n)then
if b[i]>0 then
begin
max:=max+b[i];md:=md+max div p;max:=max mod p;
end;
if(mm div p>md)or((mm div p=md)and(mm mod p>max))then max:=mm mod p;if max>=0 then writeln(max)
else begin write('-');writeln(abs(max));end;
end.
-
02014-03-29 15:29:10@
var
i, n, p, x, f1: longint;
t, maxt, f: int64;
mark: boolean;
begin
readln(n, p);
read(maxt);
f1 := maxt;
f := f1;
f := f1 + f1;
mark := f > f1;
if mark then
f := f mod p;
t := f1;
for i := 2 to n - 1 do
begin
Read(x);
if t < 0 then
t := 0;
t := t + x;
if t > maxT then
maxT := t;
if maxT > 0 then
if mark then
f := (f + maxT) mod p
else
begin
f := f + maxt;
mark := f > f1;
if mark then
f := f mod p;
end;
end;
if mark then
begin
if f < 0 then
Write('-');
writeln(abs(f) mod p);
end
else
begin
if f1 < 0 then
Write('-');
writeln(abs(f1) mod p);
end;
end. -
02014-02-17 21:27:46@
补充一下,别被下面发的C++代码坑了,只有80分程序,int64回WA,千万别信那个wuyifan
-
02014-02-17 21:25:55@
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN 1000001
using namespace std;
long long init[1000001],temp1[MAXN],temp2[MAXN],ans[MAXN];
int main()
{
memset(temp1,0,sizeof(temp1));
int n,p;
long long maxvalue;
scanf("%d%d",&n,&p);
for(int i=1;i<=n;i++) scanf("%lld",&init[i]);
maxvalue=init[1]; temp1[1]=init[1]; temp2[1]=init[1];
for(int i=2;i<=n;i++){
if(temp1[i-1]>0) temp1[i]=temp1[i-1]+init[i];
else temp1[i]=init[i];
if(temp1[i]>maxvalue) maxvalue=temp1[i];
temp2[i]=maxvalue;
}
ans[1]=temp2[1];
maxvalue=ans[1]+temp2[1];
for(int i=2;i<=n;i++){
if((ans[i-1]+temp2[i-1])>maxvalue) maxvalue=ans[i-1]+temp2[i-1];
ans[i]=maxvalue;
}
if(ans[1]<maxvalue) printf("%lld\n",maxvalue%p);
else printf("%lld\n",ans[1]%p);
return 0;
} -
02014-01-26 11:06:12@
program number;
var
i, n, p, x, f1: longint;
t, maxt, f: int64;
mark: boolean;
begin
readln(n, p);
read(maxt);
f1 := maxt;
f := f1;
f := f1 + f1;
mark := f > f1;
if mark then
f := f mod p;
t := f1;
for i := 2 to n - 1 do
begin
Read(x);
if t < 0 then
t := 0;
t := t + x;
if t > maxT then
maxT := t;
if maxT > 0 then
if mark then
f := (f + maxT) mod p
else
begin
f := f + maxt;
mark := f > f1;
if mark then
f := f mod p;
end;
end;
if mark then
begin
if f < 0 then
Write('-');
writeln(abs(f) mod p);
end
else
begin
if f1 < 0 then
Write('-');
writeln(abs(f1) mod p);
end;
end.
信息
- ID
- 1850
- 难度
- 8
- 分类
- (无)
- 标签
- 递交数
- 3348
- 已通过
- 392
- 通过率
- 12%
- 被复制
- 14
- 上传者