22 条题解

  • 3
    @ 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;
    }

  • 3
    @ 2016-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;
    }

  • 1
    @ 2016-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.
    ```

  • 1
    @ 2013-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.

  • 1
    @ 2013-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;
    }

  • 1
    @ 2013-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;
    }
    这道题我使用纯模拟做的,不知道正确的算法该怎么做!

  • 0
    @ 2017-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;
    }
    
  • 0
    @ 2017-11-05 15:13:45
    急急急
    
  • 0
    @ 2017-11-05 15:13:34
    
    
  • 0
    @ 2016-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;
    }

  • 0
    @ 2015-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.

  • 0
    @ 2015-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

  • 0
    @ 2014-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;
    }

  • 0
    @ 2014-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.

  • 0
    @ 2014-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

  • 0
    @ 2014-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.

  • 0
    @ 2014-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.

  • 0
    @ 2014-02-17 21:27:46

    补充一下,别被下面发的C++代码坑了,只有80分程序,int64回WA,千万别信那个wuyifan

  • 0
    @ 2014-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;
    }

  • 0
    @ 2014-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
上传者