当前位置： ag凯发k8国际 > 编程资源 > 编程问答 >内容正文

编程问答

2013noip普级组－－小朋友的数字 -ag凯发k8国际

发布时间：2024/10/14 编程问答 6 豆豆

ag凯发k8国际收集整理的这篇文章主要介绍了 2013noip普级组－－小朋友的数字小编觉得挺不错的,现在分享给大家,帮大家做个参考.

题目链接：

https://www.luogu.org/problemnew/show/p1982

很显然，这是一个最大字段和问题，但是要注意的是在算每个小朋友的分数的时候是会爆longlong的，我们注意到小朋友的特征值和分数是递增的，手动进行模拟特征值和分数可以得出：

如果要求的小朋友的分数的上一个小朋友的特征值是大于等于零的，那么往后的时候每一个小朋友的分数都为他上一个小朋友的分数加上特征值。否则的话，这个小朋友的分数为第一个小朋友的分数加上特征值。

所以答案要么是第一个小朋友的分数，要么是最后一个小朋友的分数，我们最后只要对比第一个小朋友的分数和最后一个小朋友的分数就行，但是问题来了，因为分数的大小有可能会爆longlong，所以我们在计算的时候会一边取模一边计算，如此这般的话就无法比较取模之前的分数和第一个分数的大小了，但是我们注意到第一个分数的大小是不会超过1e9的，所以每当第i个小朋友的分数大于1e9的时候就说明答案是最后一个的分数。

代码：

#include #include #include #include using namespace std; const int inf=1e6 7; typedef long long ll; ll arr[inf]; ll special[inf]; ll score[inf];ll max(ll a,ll b) //先尝试不用取余函数。 {if(a>b)return a;elsereturn b; }int main() {ll n,q;scanf("%lld %lld",&n,&q);for(int i=0;i=0)flag=1;for(int i=1;i0){sum =arr[i];}else{sum=arr[i];}themax=max(themax,sum);special[i]=themax; //特征值。还不至于爆longlong,if(special[i-1]>=0) //就是这里。重点重点！！！！！！！！！{flag=1;}ll temptemp=score[i-1] special[i-1];if(flag==0){score[i]=special[0] score[0];}else{if(temptemp>=score[0])lastflag=1;if(temptemp>1000000000){lastflag=1;temptemp%=q;}score[i]=temptemp;}}if(flag==0||lastflag==0){if(score[0]<0){if(score[0]%q!=0)printf("-");score[0]*=(-1);}printf("%lld\n",score[0]%q);}else{if(score[n-1]<0){if(score[n-1]%q!=0)printf("-");score[n-1]*=-1;}printf("%lld\n",score[n-1]%q);}return 0; }

总结

以上是ag凯发k8国际为你收集整理的2013noip普级组－－小朋友的数字的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得ag凯发k8国际网站内容还不错，欢迎将ag凯发k8国际推荐给好友。

普级组

编程问答

2013noip普级组－－ 小朋友的数字 -ag凯发k8国际

总结

2013noip普级组－－小朋友的数字 -ag凯发k8国际