题目链接

解题思路

我们先看数据范围，是1e9。一般人都会反应到：1e61e92=2e15，没有爆long long。但如果测大样例的话会发现这明显不只，不是这样算的，而证明我也懒得不会证了，所以只需知道会爆long long。

先撇开数据范围不看，可以发现这道题其实就是一次其水无比的dp和一点模拟。于是我们可以轻松写出这种代码（不过题目意思要读懂真的太困难了。。。）

#include<bits/stdc++.h>
using namespace std;
const long long inf=1e17+7;
long long a[1000005];
long long te[1000005];
long long score[1000005];
long long s[1000005];
int main(){
    int n,p;
    cin>>n>>p;
    long long sum=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    long long maxn=-inf;
    for(int i=1;i<=n;i++){
        s[i]=max(s[i-1],0ll)+a[i];
        maxn=max(s[i],maxn);
        te[i]=maxn;
    }
    maxn=-inf;
    score[1]=te[1];
    for(int i=2;i<=n;i++){
        maxn=max(maxn,score[i-1]+te[i-1]);
        score[i]=maxn;
    }
    long long ans=-inf;
    for(int i=1;i<=n;i++){
        ans=max(ans,score[i]);
    }
    if(ans<0){
        cout<<"-";
    }
    cout<<abs(ans)%p<<endl;
    return 0;
} 

然后观察数据，目测不会爆1e30，但是除了高精没想到其他办法。
今天下午碰到jyeric，他告诉了我一种自己想出的80变100的做法，也就是用两个longlong存前n位和后n位。这种方法在一些刚好爆long long的地方其实经常用，而且一般用pair来存，但是我觉得对于pair的运用并不熟悉，所以便用数组模拟。

#include<bits/stdc++.h>
using namespace std;
const long long inf=1e17+7;
long long a[1000005];
long long te[1000005];
long long score[1000005][2];
long long s[1000005];
int lmax=1e15;
int main(){
    int n,p;
    cin>>n>>p;
    long long sum=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    long long maxn=-inf;
    for(int i=1;i<=n;i++){
        s[i]=max(s[i-1],0ll)+a[i];
        maxn=max(s[i],maxn);
        te[i]=maxn;
    }
    long long maxm[2]={0,0};
    maxm[1]=-inf;
    score[1][1]=te[1];
    for(int i=2;i<=n;i++){
        long long tmp[2];
        tmp[0]=score[i-1][0];
        tmp[1]=score[i-1][1]+te[i-1];
        tmp[0]+=tmp[1]/lmax;
        tmp[1]%=lmax; 
        if(maxm[0]<tmp[0]){
            maxm[0]=tmp[0],maxm[1]=tmp[1];
        }else if(maxm[0]==tmp[0]&&maxm[1]<tmp[1]){
            maxm[0]=tmp[0],maxm[1]=tmp[1];
        }
        score[i][0]=maxm[0],score[i][1]=maxm[1];
    }
    long long ans[2];
    ans[0]=ans[1]=-inf;
    for(int i=1;i<=n;i++){
        if(ans[0]<score[i][0])
        ans[0]=score[i][0],ans[1]=score[i][1];
        else if(ans[0]==score[i][0]&&ans[1]<score[i][1])
        ans[0]=score[i][0],ans[1]=score[i][1];
    }
    if(ans[1]<0||ans[0]<0){
        cout<<"-";
    }
    cout<<(abs(ans[0])%p*(lmax)%p+abs(ans[1])%p)%p<<endl;
    return 0;
} 

本文链接：http://kaispace.com.cn/index.php/archives/720/

如果未注明出处，复制公开后需将注明本博客链接。
打赏作者