5 981
-409 -401 97 -96 -301 


-409

模拟题(80pts)

• 从前往后预处理子段和最大值(特征值)，根据题目描述处理每个同学的分值

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1000010;
int n,p;
LL f[N]; //f[i]表示特征值 
int main()
{
    cin>>n>>p;
    LL s=0,maxs=-2e18;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        s=max(s,0ll)+x; //连续子段和
        maxs=max(maxs,s); //最大子段和
        f[i]=maxs; //记录前i个数的最大连续子段和
    }
    LL res=f[1]; //第一个小朋友的分数 
	LL score=2*f[1]; //第一个小朋友的分数+第一个小朋友的特征值(第二个小朋友的分数)
    for(int i=2;i<=n;i++) //枚举第i个人的分数
    {
        res=max(res,score); //更新前i个人的分数+特征值的最大值
        score=max(score,f[i]+score); //更新第i+1个人的分数
    }
    cout<<res%p; //输出分数最大值 
    return 0;
}

模拟题+高精度(100pts)

• 由于$f[i]$做大可以到$10^{15}$,那么$f[i]$累加值会超过long long ,我们可以用一个$a[0]$表示第$18$位，$a[1]$表示高$18$位。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1000010;
const LL B=1e15;
int n,p;
LL f[N];
int main()
{
	cin>>n>>p;
	LL s=0,maxs=-2e18; //最大子段和
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		s=max(s,0ll)+x; //更新以当前数结尾的和
		maxs=max(maxs,s); //更新最大子段和
		f[i]=maxs;  //更新1到i的最大子段和
	}
	LL res[2]={f[1]}; //第一个分数
	LL score[2]={f[1]*2}; //第二个人的分数(特征值+分数)
	//因为f[i]的值可能到大10^15,那么f[i]累加会超过long  long,那么我们用 a[0]表示低18位,a[1]表示高18位
	for(int i=2;i<=n;i++)
	{
		if(res[1]<score[1]||res[1]==score[1]&&res[0]<score[0]) //更新前i个人的最大分数
		{
			res[0]=score[0],res[1]=score[1];
		}
		if(f[i]>0) //有特征值可以增加分数
		{
			score[0]+=f[i];
			score[1]+=score[0]/B;
			score[0]%=B;
		}
	}
	cout<<(res[1]*(B%p)+res[0])%p;
	return 0;
}

#include<bits/stdc++.h> using namespace std; long long n,p,f[1000010],s,maxs=-2e18,x,res,sc; int main() { cin>>n>>p; for(int i=1;i<=n;i++) { cin>>x; s=max(s,0ll)+x; maxs=max(s,maxs); f[i]=maxs; } res=f[1],sc=res*2; for(int i=2;i<=n;i++) { res=max(res,sc)%p; sc+=max(0ll,f[i])%p; } cout<<res%p; return 0; }