题目连接：Neko's loop
题意：给一个长度为n的环,下标从0~n-1，环上每个点有个值表示到这个点会得到的快乐值。，然后每次可以花费1能量往后跳k步。你可以选择任意点开始跳，可以任意点结束，最多跳m次问得到至少s的快乐值最初要拥有多少。
题解：先把循环节挑出来，,然后在循环节上找最大字段和。循环节长度为cnt,然后就是枚举起点用线段树维护前缀和，然后取最大值。
#include<bits/stdc++.h> #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define ll long long using namespace std; const int N=1e4+5; int n,m,k; ll ans,s; bool vis[N]; int a[N]; int b[N*3]; ll tr[3*N<<2],laz[3*N<<2]; void built(int l,int r,int rt) { tr[rt]=laz[rt]=0; if(l==r)return ; int m=l+r>>1; built(ls);built(rs); } void push_down(int rt) { if(!laz[rt])return ; laz[rt<<1]+=laz[rt]; laz[rt<<1|1]+=laz[rt]; tr[rt<<1]+=laz[rt]; tr[rt<<1|1]+=laz[rt]; laz[rt]=0; } void push_up(int rt) { tr[rt]=max(tr[rt<<1],tr[rt<<1|1]); } void update(int L,int R,int val,int l,int r,int rt) { if(L<=l&&r<=R) { laz[rt]+=val; tr[rt]+=val;return; } push_down(rt); int m=l+r>>1; if(L<=m)update(L,R,val,ls); if(R>m)update(L,R,val,rs); push_up(rt); } ll query(int L,int R,int l,int r,int rt) { if(L<=l&&r<=R) { return tr[rt]; } push_down(rt); int m=l+r>>1; ll ans=-1e18; if(L<=m)ans=max(ans,query(L,R,ls)); if(R>m)ans=max(ans,query(L,R,rs)); return ans; } ll slo(int x) { int tt =x; int cnt=0; while(vis[tt]==false){ vis[tt] = true; b[++cnt] = a[tt]; tt = (tt+k)%n; //cout << tt << ' '<<(tt+k)%n<<' '<< a[tt] << endl; } ll sum=0; for(int i=1;i<=cnt;i++) { sum+=b[i]; b[cnt+i]=b[cnt*2+i]=b[i]; } int len=m%cnt; int mm = m; if(m/cnt) len += cnt,mm-=cnt; ll an=-1e18; built(1,cnt*3,1); for(int i=3*cnt;i>=1;i--) { int r=min(i+len-1,3*cnt); update(i,r,b[i],1,3*cnt,1); an=max(an,query(i,r,1,3*cnt,1)); //cout <<i << ' '<<an << ' '<<b[i] << endl; } return sum>0?an+mm/cnt*sum:an; } int main() { int T,cas=0; scanf("%d",&T); while(T--) { memset(vis,false,sizeof(vis)); ans=-1e18; scanf("%d %lld %d %d",&n,&s,&m,&k); for(int i=0;i<n;i++) { scanf("%d",&a[i]); } for(int i=0;i<n;i++) { if(!vis[i]) { ans=max(ans,slo(i)); } } //zcout <<ans << endl; printf("Case #%d: %lld ",++cas,(ans>=s?0:s-ans)); } return 0; }