【正经题解】小朋友的数字
2024-03-15 10:29:43
发布于:浙江
2阅读
0回复
0点赞
题目总体意思就是找到没一个小朋友的特征值,这个特征值就是包括这第 小朋友在内的 中的一段连续的小朋友手上拿的卡片 的最大值
也就是一个最大子段和.然后这个分数则是第 个小朋友之前不包括第 个小朋友在内的 ( )的小朋友的分数加上特征值的最大值
题目让我们求所有小朋友中的最大分数
其实挺好理解的
最大子段和我们可以从 直接扫过去,设 为当前某一段子段和.然后从 开始一个个加到 里,然后最大值 (最大值, )
然后我们用一个数组,分别存下每一个小朋友所对应的特征值(最大子段和), [ ] 当前最大值
然后如果 ,这个时候前面这个子段肯定没用了,所以 ;
求出所有小朋友的特征值后,去算分数
然而这里的 是小于 ,其他数字不超过 .相信正常人都知道应该写高精了.
但是高精一般会让我们直接输出解,而这里没有,所以不是高精.
第一个小朋友的分数 特征值,第二个小朋友的分数 第一个小朋友的分数 第一个小朋友的最大值
第三个小朋友 前面两个小朋友分数与特征值的最大. 第四个 前面三个
从这里我们可以看出这个小朋友的分数是从前面取最大值,所以说分数一定是大于或者是等于前面的分数
这样就可以免掉高精比较了
因为这里的第一个数是肯定不会大于 的,所以如果有数字是大于 的就可以直接 了(这里我还是不懂,半懂不懂的)
这里可以判断一个数是否大于第一个数,如果没有 的的话直接输出 [ ],有的话要 ( [ ], [ ]),因为取余了
然后这样子就可以避免高精加了
开
#include <bits/stdc++.h>
using namespace std;
long long a[1000001]={0};
long long tzz[1000001]={0};
long long fs[1000001]={0};
int main(){
//freopen("number.in","r",stdin);
//freopen("number.out","w",stdout);
long long n,p;
long long maxx=0,max1=0,ans=-0x3f3f3f3f;
cin>>n>>p;//输入
for(long long i=1;i<=n;++i)
cin>>a[i];
long long area=0,area1=0;
fs[1]=a[1];//由题意得,第一个小朋友的分数等于手上牌的数字
for(long long i=1;i<=n;++i){//这一是判断最大子段和的
area+=a[i];
ans=max(area,ans);
if(area<0)
area=0;
tzz[i]=ans;
}
/*for(int i=1;i<=n;++i)
cout<<tzz[i]<<" ";
cout<<endl;*/
area=0;
ans=fs[1];
long long sum=fs[1]+tzz[1];//第二个人的分数=第一个的分数+第一个的特征值
long long bj=0;//特判
for(long long i=2;i<=n;++i){
fs[i]=sum;//当前人的分数
if(fs[i]+tzz[i]>sum)sum=fs[i]+tzz[i];//下一个人的分数,因为分数满足不下降序列,所以不用判断小与的情况,因为不可能
if(sum>1000000000){//特判,判断如果大于 1000000000,mod ,将标记设为1
bj=1;
sum%=p;
}
//ans=max(fs[i],ans);
//cout<<ans<<" ";
//sum=max(ans,fs[i]+tzz[i]);
}
if(bj==0)ans=max(fs[n],fs[1]);//如果标记为0,则判断一下
else
ans=fs[n];//否则直接将ans=fs[n]
cout<<ans%p;//输出答案
return 0;
}
这里空空如也
有帮助,赞一个