P1982 [NOIP2013 普及组] 小朋友的数字 题解
小邱
2022-03-26 09:46:16
题目链接：[P1982 [NOIP2013 普及组] 小朋友的数字](https://www.luogu.com.cn/problem/P1982)
这道题分为两个小问，第一问是求最大连续子序列和
有了特征值，求分数就很简单了！
```cpp
#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]，所以我们不妨定义变量，节省空间：
```cpp
#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循环综合起来：
```cpp
#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;
}
```
变量有点多，建议大家对照前后几个程序一起看，这样清晰一点