题解 P1982 【小朋友的数字】

· · 题解

本蒟蒻居然能在机房里打出绿题正解当然要纪念一下

首先读题，这题题面极其凌乱(莫非是考个语文舒缓一下选手心情??)我连样例都看了好几遍才懂

特征值就是排在某个小朋友（包括他自己）之前所有小朋友中连续一段的数字总和的最大值，等于求在某个数之前(包含自己)的最大连续子段和，则可以先DP求出这些小朋友的特征值，然后跑一遍求出分数最后%即可

但是就这样跑只能拿80分？？？第一遍交的代码如下

#include<bits/stdc++.h>
using namespace std;
long long maxn=0xcf,n,m,i,p,ans=0,b[1000001],dp[1000001],f[1000001],a[1000001];
bool tag=0,bj=0;
int main(){
    memset(f,0xcf,sizeof(f));
    scanf("%lld%lld",&n,&p);
    for(i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        maxn=max(maxn,a[i]);
    }
    if(maxn<0){
        cout<<"-"<<abs(maxn)%p;
        return 0;
    }
    if(maxn==0){
        cout<<"0";
        return 0;
    }
    f[1]=a[1];
    dp[1]=f[1];
    maxn=a[1];
    m=1;
    for(i=2;i<=n;i++) f[i]=max(f[i-1]+a[i],a[i]),dp[i]=max(dp[i-1],f[i]);
    for(i=1;i<=n;i++) b[i]=a[i];
    ans=f[1];
    b[2]=a[1]+f[1];
    if(b[2]>b[1]) maxn=b[2],m=2;
    for(i=3;i<=n;i++){
        b[i]=max(b[m]+dp[m],b[i-1]+dp[i-1]);
        if(b[i]>maxn) maxn=b[i],m=i;
    }
    for(i=1;i<=n;i++) ans=max(ans,b[i]);
    if(ans<0){
        cout<<"-"<<abs(ans)%p;
        return 0;
    }
    cout<<ans%p;
    return 0;
}

因为分数加到最后可能很大，中间又是max计算，取模了最大值就出了问题，那怎么办嘞?

再仔细想想(胡乱猜测)，分数序列要么是单调递减的，要么是单调递增的，要么先递减后递增，所以答案应该在分数序列首或尾(需要打个标记记录是否有递增序列，如果有，那分数应出现在最后，如果单调递减，那分数最大值就为b[1])

AC代码如下：

#include<bits/stdc++.h>
using namespace std;
long long n,i,p;
long long ans=0; 
long long maxn=0xcf;
//b数组是最终分数，f是以i为末尾的最大连续子段和，dp是i之前的最大连续子段和(即题目中的特征值)，a是小朋友手上的数字
long long b[1000001],dp[1000001],f[1000001],a[1000001];
bool tag=0;  //标记
inline long long read(){  //快读优化(机房老爷机不加快读优化就T了一个点....)
    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(){
    memset(f,0xcf,sizeof(f)); //先将f数组赋为无限小
    n=read(),p=read(),a[1]=read();
    f[1]=a[1];
    dp[1]=f[1];
    b[1]=a[1];
    ans=f[1];
    for(i=2;i<=n;i++){  //dp
        a[i]=read();
        f[i]=max(f[i-1]+a[i],a[i]); 
        dp[i]=max(dp[i-1],f[i]);
    }
    b[2]=a[1]+f[1];
    if(b[2]>b[1]) ans=b[2],tag=1; //比较b[2]和b[1]是否出现递增序列，若出现tag=true;
    for(i=3;i<=n;i++){
        if(dp[i-1]<0){ //如果i-1的特征值小于0，那加上会使答案变小不如不加
            b[i]=b[i-1];
            continue;
        }
        b[i]=b[i-1]+dp[i-1];
        if(b[i]>b[1]) tag=1;  //同上
        if(tag==1) b[i]%=p;  //重点:由于序列递增，那么b[i]>=b[i-1]所以不需要max比较，直接更新取模即可
        ans=b[i];
    }
    if(tag==0){  //若序列单调递减，则b[1]就是最大值
        printf("%lld",b[1]);
        return 0;
    }
    printf("%lld",ans); //若序列存在递增，那么输出ans即可
    return 0;  //完结撒花
}

唔，又要开学了，又要面对语数外物化生...