在线时间:8:00-16:00
迪恩网络APP
随时随地掌握行业动态
扫描二维码
关注迪恩网络微信公众号
去博客园看该题解题目传送门 - 51Nod1952题意概括有一个栈,有3种操作: Ο 从栈顶加入一个元素 Ο 从栈底加入一个元素 Ο 从栈顶弹出一个元素 现在,求每次操作后栈内元素的最大值和mod (1e9+7) n次操作,n<=1e7
题解这题对于博主这样的蒟蒻,做出来了,万分欣喜。 我们在搞一个栈的同时,维护一个单调不降的队列。 然后在弹出栈的时候,如果队尾元素等于当前弹出的元素,那么队尾出队。 至于两种进队,都是最基础的维护队列的方法。 每次,最大值就是队尾元素值。
代码#include <cstring> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cmath> using namespace std; typedef long long LL; const int N=1e7+5; const int mod=1e9+7; int n,a[N],b[N]; int q[N*2],head,tail,st[N*2],first,last; LL A,B,C,x,aa,bb,MOD; int main(){ scanf("%d%lld%lld%lld%lld%lld%lld%lld",&n,&A,&B,&C,&x,&aa,&bb,&MOD); for (int i=1,tot=0;i<=n;i++){ x=(x*aa+bb)%MOD; LL xx=x%(A+B+C); if (tot<=1||xx<A) a[i]=0,b[i]=x,tot++; else if (A<=xx&&xx<A+B) a[i]=1,b[i]=x,tot++; else a[i]=2,tot--; } head=1e7+2,tail=head; first=head,last=tail; int ans=0; for (int i=1;i<=n;i++){ if (a[i]==0){ st[++last]=b[i]; if (q[tail]<=b[i]) q[++tail]=b[i]; } else if (a[i]==1){ st[first--]=b[i]; while (head<tail&&q[head+1]<b[i]) head++; q[head--]=b[i]; } else { if (q[tail]==st[last]) tail--; last--; } ans=(ans+q[tail])%mod; } printf("%d",ans); return 0; }
|
2023-10-27
2022-08-15
2022-08-17
2022-09-23
2022-08-13
请发表评论