11.25 模拟赛

早上三个小时，大战T1，推翻了无数个结论

然后写了一个单调队列+滑动窗口终于A掉了

然后考完发现之前的一个裸滑动窗口是对的感觉自己被骗了

T1：

一盒魔法饼干，这些饼干共有n 块其中从左到右第i 块魔法饼干的魔力值为 mi=(A*m_i-1+B )%C，其中i>1

每吃一块饼干，他就会获得mi-D 的魔力，吃一块饼干获得的魔力可以为负开始有k点魔力，当他的魔力小于 0 时，他就会因为魔力不足而晕倒

现在选择一块饼干开始吃，由于一吃饼干就停不下来了，所以从这块饼干开始向右一直吃直到吃掉第n 块饼干或者晕倒

吃饼干不是为了魔力而是为了好吃，所以他想一次吃掉尽可能多的饼干，找到最优的方案

思路：

正常来说直接用一个滑动窗口搞就好了

但是我以为是错的

然后就在滑动窗口里搞了一个单调队列记录最小值来确定合法性

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstdlib>
 5 #include<cstring>
 6 #include<algorithm>
 7 #include<map>
 8 #include<vector>
 9 #include<queue>
10 #define inf 2147483611
11 #define ll long long
12 #define MAXN 10010000
13 #define MOD
14 using namespace std;
15 inline ll read()
16 {
17     int x=0,f=1;char ch=getchar();
18     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
19     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
20     return x*f;
21 }
22 ll n,l,r,al,A,B,C,D,ans,sum,k,st,s[MAXN];
23 int hd,tl,q[MAXN];
24 int main()
25 {
26     freopen("cookie.in","r",stdin);
27     freopen("cookie.out","w",stdout);
28     n=read(),s[1]=read(),k=read(),A=read(),B=read(),C=read(),D=read();s[1]-=D;
29     for(int i=2;i<=n;i++) s[i]=s[i-1]+((s[i-1]-s[i-2]+D)*A+B)%C-D;
30     r=1;
31     while(s[r]-s[r-1]<-k) r++;st=l=r;
32     hd=1,tl=0;
33     while(r<=n)
34     {
35         while(s[q[tl]]-s[q[tl]-1]>=s[r]&&hd<=tl) tl--;
36         q[++tl]=r;
37         while(s[q[hd]]-s[l-1]<-k&&hd<=tl)
38         {
39             l++;
40             if(l>q[hd]) hd++;
41         }
42         if(ans<r-l+2&&r!=n) ans=r-l+2,st=l;
43         if(ans<r-l+1&&r==n) ans=r-l+1,st=l;r++;
44     }
45     printf("%lld %lld",ans,st); 
46 }

View Code

这个是正常不麻烦的解法

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstdlib>
 5 #include<cstring>
 6 #include<algorithm>
 7 #include<map>
 8 #include<vector>
 9 #include<queue>
10 #define inf 2147483611
11 #define ll long long
12 #define MAXN 10010000
13 #define MOD
14 using namespace std;
15 inline ll read()
16 {
17     int x=0,f=1;char ch=getchar();
18     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
19     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
20     return x*f;
21 }
22 ll a[MAXN],n,m,k,A,B,C,D,hd,tl,sum;
23 int ans,st;
24 int main()
25 {
26     freopen("cookie.in","r",stdin);
27     freopen("cookie.out","w",stdout);
28     ans=st=1;
29     n=read(),a[1]=r(),D=read();
30     for(int i=2;i<=n;i++) m[i]=ead(),k=read(),A=read(),B=read(),C=read(1LL*A*m[i-1]+B)%C;
31     for(int i=1,j=1;i<=n;i++)
32     {
33         while(j<=n&&k>=0) k+=m[j++]-D;
34         if(j-i>ans) ans=j-i,st=i;
35         k-=m[i]-D;
36     }
37     printf("%d %d",ans,st);
38 }

View Code