P1982 [NOIP2013 普及组] 小朋友的数字 题解

题目链接：P1982 [NOIP2013 普及组] 小朋友的数字 这道题分为两个小问，第一问是求最大连续子序列和 有了特征值，求分数就很简单了！

#include<bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
const int N=1000005;
ll a[N],b[N];
int main()
{
    int n,i;
    ll x,ans,k=-1e9,l=-1e9,mod;
    scanf("%d%lld",&n,&mod);
    for(i=1;i<=n;i++)
    {
        scanf("%lld",&x);
        if(l>0)
        {
            l+=x;
        }
        else
        {
            l=x;
        }
        k=max(k,l);
        a[i]=k%mod;
    }
    k=-1e9;
    b[1]=a[1];
    ans=a[1];
    for(i=2;i<=n;i++)
    {
        k=max(k,a[i-1]+b[i-1]);
        b[i]=k;
        if(ans<k)
        {
            ans=k%mod;
        }
    }
    printf("%lld",ans);
    return 0;
}

这个时候我们发现b数组本质上其实只关系到b[i-1]，所以我们不妨定义变量，节省空间：

#include<bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
const int N=1000005;
ll a[N];
int main()
{
    int n,i;
    ll x,ans=-1e9,k=-1e9,l=-1e9,mod;
    scanf("%d%lld",&n,&mod);
    for(i=1;i<=n;i++)
    {
        scanf("%lld",&x);
        if(l>0)
        {
            l+=x;
        }
        else
        {
            l=x;
        }
        k=max(k,l);
        a[i]=k%mod;
    }
    k=-1e9;
    l=a[1];
    ans=a[1];
    for(i=2;i<=n;i++)
    {
        k=max(k,a[i-1]+l);
        l=k;
        if(ans<k)
        {
            ans=k%mod;
        }
    }
    printf("%lld",ans);
    return 0;
}

我们再次观察，第一个for循环是求出a[i]，而后面关系到a[i-1]，我们不妨将这两个for循环综合起来：

#include<bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
const int N=1000005;
int main()
{
    int n,i;
    ll x,ans,k=-1e9,l,mod,p,q;
    scanf("%d%lld%lld",&n,&mod,&x);
    ans=x;
    l=x;
    k=x;
    p=x;
    q=-1e9;
    for(i=2;i<=n;i++)
    {
        scanf("%lld",&x);
        if(l>0)
        {
            l+=x;
        }
        else
        {
            l=x;
        }
        q=max(q,k%mod+p);
        p=q;
        k=max(k,l);
        a[i]=k%mod;
        if(ans<q)
        {
            ans=q%mod;
        }
    }
    printf("%lld",ans);
    return 0;
}

变量有点多，建议大家对照前后几个程序一起看，这样清晰一点