【题解】小朋友的数字
题目链接
解题思路
我们先看数据范围,是 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;
}