没错,我就是暴力老哥!
大佬 场切这道题,而我还只能看题解😅
发现操作等价于,如果$a_{p+1}-a_p
发现操作后所有数的和不变,并且ap+1和ap的差恰好为lp
然后就是神来之笔了:考虑对于>i的位置都减去li,这样操作就变成了ap=ap+1=ap+ap+12。为什么这样是对的?因为这样当操作p的时候就合上了,而当操作>p的位置时两个数之间的差不会改变,而是整体偏移一个值。可以证明,这样转化 不会改变a1的值
然后,我们并不关心操作的过程,而只关心最后操作的结果。类似的,我们并不关心是否存在这种策略,而只关心能否达成
remark 我们只关心最终
a1的值,其他多余的性质不用去分析
结论:记
x为前缀平均值的最小值,那么最终
a1值就等于
x
证明:注意到每次操作只会让前缀平均值变小。考虑最小值的位置,如果可以分成若干个值相同的段,那么这些段的值一定是递增的,可以很容易的导出矛盾。
那么,我们将每个ai减去x,问题就转化为了求任意前缀≥0的序列数目
前缀和优化之,单次DP复杂度O(n3)
发现有用的x不会超过max(ri−li)个,因此剪枝即可。
复杂度O(n2d2)。
remark 感觉考场上做的比较糟糕的原因还是在于 **没有认真去分析题目想让你干啥** 。。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
| #include<bits/stdc++.h> #define ll long long #define pb push_back #define fi first #define se second #define inf 0x3f3f3f3f3f3f3f3f using namespace std; const int N=205; const int mod=1e9+7; int n,m,b[N],c[N],l[N],r[N],sl[N],sr[N]; ll res[200005],mul; ll now[N*N],nxt[N*N]; ll solve(int x){ for(int i=1;i<=n;i++)sl[i]=sl[i-1]+l[i]-x,sr[i]=sr[i-1]+r[i]-x; for(int i=1;i<=n;i++){ if(sr[i]<0)return 0; }int ok=1; for(int i=1;i<=n;i++){ if(sl[i]<0)ok=0; }if(ok)return mul; now[0]=1; for(int i=1;i<=n;i++){ l[i]-=x,r[i]-=x; for(int j=0;j<=sr[i]-sl[i];j++){ int L=max({0,sl[i-1],j+sl[i]-r[i]}),R=min(j+sl[i]-l[i],sr[i-1]); if(L>R||j+sl[i]<0)nxt[j]=0; else if(L==sl[i-1])nxt[j]=now[R-sl[i-1]]; else nxt[j]=(now[R-sl[i-1]]-now[L-sl[i-1]-1])%mod; }for(int j=0;j<=sr[i]-sl[i];j++){ now[j]=nxt[j];if(j)now[j]=(now[j]+now[j-1])%mod; }l[i]+=x,r[i]+=x; } return (now[sr[n]-sl[n]]+mod)%mod; } int main(){ ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); cin>>n;for(int i=1;i<=n;i++)cin>>r[i],l[i]=0; for(int i=1;i<n;i++){ cin>>b[i]; for(int j=i+1;j<=n;j++)l[j]-=b[i],r[j]-=b[i]; }mul=1;for(int i=1;i<=n;i++)mul=mul*(r[i]-l[i]+1)%mod; memset(res,-1,sizeof res); cin>>m; for(int i=1;i<=m;i++){ int x;cin>>x; if(~res[x+100000]){ cout<<res[x+100000]<<"\n"; } else{ cout<<(res[x+100000]=solve(x))<<"\n"; } } }
|