题意：给定n，p，k n个数，然后取连续的一段，让着一段的sum%p<=k,然后求满足条件的最大sum/p
思路：见注释
/* 取一段[L,R]让这个区间和取模后小于等于k 切记，取模操作符合减法的分配定律 条件可以转化为(sum-pre[L]-suf[R])%p<=k ===>(sum%p-pre[L]%p-suf[R]%p<=k 方法就是枚举这个pre[L]%p,然后可以借此确定suf[R]%mod的最右边的位置，更新最大值即可 */ #include<bits/stdc++.h> using namespace std; typedef long long ll; #define pb push_back #define lson root<<1,l,midd #define rson root<<1|1,midd+1,r const int M=1e6+6; ll tree[M<<2],w[M],suf[M],pre[M],prel[M],sufr[M]; void up(int root){ tree[root]=max(tree[root<<1],tree[root<<1|1]); } void build(int root,int l,int r){ if(l==r){ tree[root]=sufr[l]; return ; } int midd=(l+r)>>1; build(lson); build(rson); up(root); } ll query(int L,int R,int root,int l,int r){ if(L<=l&&r<=R){ return tree[root]; } int midd=(l+r)>>1; ll res=-2; if(L<=midd) res=max(res,query(L,R,lson)); if(R>midd) res=max(res,query(L,R,rson)); return res; } ll p; ll mm(ll x){ if(x<0) x+=p; return x%p; } int main(){ int t; scanf("%d",&t); for(int sign=1;sign<=t;sign++){ ll n,k,ans=-1; scanf("%lld%lld%lld",&n,&p,&k); for(int i=0;i<=p;i++) prel[i]=sufr[i]=-1; for(int i=0;i<=2*p;i++) tree[i]=0; for(int i=1;i<=n;i++){ scanf("%lld",&w[i]); pre[i]=pre[i-1]+w[i];///前缀和 ll premod=pre[i]%p; if(prel[premod]==-1)///记录前缀和mod意义下，从左往右第一次出现的位置， prel[premod]=i; if(premod<=k) ans=max(pre[i]/p,ans); } printf("Case %d: ",sign); ll summod=pre[n]%p;///总的前缀和取模 if(summod<=k){///全部加起来满足条件 printf("%lld ",pre[n]/p); continue; } suf[n+1]=0; for(int i=n;i>=1;i--){ suf[i]=suf[i+1]+w[i]; ll sufmod=suf[i]%p; if(sufr[sufmod]==-1) sufr[sufmod]=i; if(sufmod<=k) ans=max(ans,suf[i]/p); } build(1,1,p);///依照sufr来做线段树，下标是后缀和取模，tree存的是位置 for(int i=1;i<p;i++){///枚举从左开始的模p意义下的前缀和 if(prel[i]==-1) continue; int temp=summod-i;///总的减去左边 int r=mm(temp); int l=mm(temp-k); if(l==0||l>r)///查找区间不合法 continue; int pos=query(l,r,1,1,p);//返回满足条件的最大值，即最后的坐标 if(pos<=prel[i]+1)///因为至少要取一个袋子，所以如果pos==prel[i]+1,那么利用下面步骤的处理就会选到0个袋子，所以不可取 continue; ll x=pre[n]-pre[prel[i]]-suf[pos]; ans=max(ans,x/p); } printf("%lld ",ans); } return 0; }