宝石街

在 $\text D$ 国 $\text S$ 市 $\text T$ 镇，坐落着一条长度为 $\mathop n$ 的宝石街。

把起点定为原点，以终点方向作为正方向建立数轴，那么对于每个整数 $i(1\le i \le n)$ ，在点 $\mathop i$ 处有 $a_i$ 块宝石。

身无分文的小 $\text D$ 此时就站在原点，径直向终点走去。在且仅在行走的过程中经过每一个整数点，他可以选择捡起或扔掉任意块的宝石，也可以既不捡又不扔。设他在某一点拥有的宝石数为 $\mathop k$ ，那么他走到下一个点需要的时间也为 $\mathop k$ 。

现在，小 $\text D$ 想知道，在行走时间不超过 $\mathop t$ （不需要到达终点）时，他最多可以拥有多少块宝石？

由于本题数据范围较大，部分测试点的 $a_i$ 将在程序内生成。
输入共 $\text{2}$ 行。
第 $\text 1$ 行包含 $\text 3$ 个正整数 $n,t,type\big (1\le n \le 6\cdot 10^7，1\le t\le 10^{18}，type\in\{1,2\}\big)$ 。
若 $type=\text 1$ ，保证 $n\le 10^5$ 。第 $\text 2$ 行包含 $\mathop n$ 个正整数，其中第 $\mathop i$ 个数表示 $a_i(1\le a_i\le 10^9)$ 。

若 $type=\text 2$ ，第 $\text 2$ 行包含 $\text 2$ 个正整数 $a_1$ 和 $p(1\le a_1,p\le 10^9)$ 。对于每个整数 $i(2\le i\le n)$ ，设 $x_i=a_{i-1}\ \text{xor} \ (a_{i-1}<<13),y_i=x_i\ \text{xor} (x_i>>17)$ ，则 $a_i=\big(y_i \ \text{xor}\ (y_i<<5)\big)\bmod p+1$ （其中 $\text{xor}$ 是按位异或运算）。

注意，本题的标准解法并不依赖于此数据生成方法。

#include<bits/stdc++.h> using namespace std; int a[60000005]; int main() { int i,l,r,n,op,p; long long x,y,t,s=0,S=0,ans=0; scanf("%d%lld%d",&n,&t,&op); if(op==1)for(i=1;i<=n;i++)scanf("%d",&a[i]); else { scanf("%d%d",&a[1],&p); for(i=2;i<=n;i++) { x=a[i-1]; x=x^(x<<13); y=x^(x>>17); a[i]=(y^(y<<5))%p+1; } } for(l=r=1;r<=n;r++,S+=s) { s+=a[r]; while(S>t)s-=a[l],S-=(long long)(r-l)*a[l],l++; ans=max(ans,s+(l>1?(t-S)/(r-l+1):0)); } printf("%lld\n",ans); return 0; }

详情