将$A$操作看作直接除以2(保留小数),最终再将$a_{i}$取整
记$k$表示$A$操作的次数,$p_{i}$表示第$i$次$A$和第$i+1$次$A$之间$B$操作的次数(特别的,$p_{0}$为第1次$A$操作前,$p_{k}$为最后一次$A$操作后),则有$a'_{i}=\lfloor\frac{a_{i}-\sum_{i=0}^{k}p_{i}2^{i}}{2^{k}}\rfloor$,然后要保证$\sum_{i=0}^{k}p_{i}+k\le K$
考虑$\forall 0\le i<k$,若$p_{i}>1$,可以令$p_{i}-=2$且$p_{i+1}+=1$,则$a'_{i}$的值不改变但操作次数减小,因此可以被其所替代,不妨假设$p_{i}=0或1$
然后考虑$p_{k}$,令$\Delta_{i}=a_{i+1}-a_{i}$,$a_{i}$可以用$(a_{min},\Delta_{i})$来描述,而$p_{k}$不会改变$\Delta_{i}$,因此只需要对于每一组$\Delta_{i}$求出$a_{min}$的范围,即对所有$[\max(a_{min}-(K-k-cnt(C),0),a_{min}]$求并(其中$cnt(C)$表示$C$中1的个数)
换言之,即可得到一个暴力的做法:枚举$k$和$C$,然后对$\Delta_{i}$哈希,对哈希处维护所有区间的并,最后答案即为所有哈希位置上区间长度之和
再考虑$a'_{i}$,由于$C=\sum_{i=0}^{k-1}p_{i}2^{i}<2^{k}$,即可得$a'_{i}=\lfloor\frac{a_{i}-C}{2^{k}}\rfloor=\lfloor \frac{a_{i}}{2^{k}}\rfloor-[a_{i}\ mod\ 2^{k}<C]$
先枚举$k$,然后将$a_{i}$按$a_{i}\ mod\ 2^{k}$排序,对于$C$在相邻两个$a_{i}\ mod\ 2^{k}$区间内部,$\Delta_{i}$和$a_{min}$都是相同的,所不同的仅仅是$cnt(C)$,求出这个区间内$cnt(C)$最小的位置即可
如何求区间$[l,r]$中$cnt(C)$最小的位置,从高到低枚举$l$和$r$的二进制位,若相同必然填相同的数,否则(必然是$l$为0且$r$为1),再分两类讨论:
1.对于之后的位数,若可以做大$cnt(C)=0$(即$l$剩下的部分都为0),必然达到该下限;
2.否则必然有$cnt(C)\ge 1$,同时令$C=100...$可以达到此下限,取这个即可
因此求$cnt(C)$最小的位置,时间复杂度为$o(\log_{2}a_{i})$
$k$枚举范围为$\log_{2}a_{i}$,然后排序为$o(n\log_{2}n)$,再枚举一个区间,求$cnt(C)$最小值为$o(\log_{2}a_{i})$,对$\Delta_{i}$哈希以及区间求并需要$o(n)$,总复杂度即为$o(n^{2}\log_{2}a_{i})$
然后由于复杂度允许,我们还可以避免哈希,而是将所有序列以及对应的区间记录下来,按照序列排序,然后对于一个子区间中所有区间求并即可,时间复杂度为$o(n^{2}\log_{2}a_{i}\log_{2}na_{i})$
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 205 4 #define ll long long 5 #define mod 1000000007 6 #define fi first 7 #define se second 8 struct ji{ 9 ll l,r,a[N]; 10 }o; 11 vector<ji>v; 12 vector<pair<ll,ll> >vv; 13 pair<ll,int>b[N]; 14 int n,ans; 15 ll m,a[N],p[N]; 16 int check(ll *a,ll *b){ 17 for(int i=1;i<n;i++) 18 if (a[i]!=b[i])return (a[i]<b[i])*2-1; 19 return 0; 20 } 21 bool cmp(ji x,ji y){ 22 int p=check(x.a,y.a); 23 if (p)return (p==1); 24 return (x.l<y.l)||(x.l==y.l)&&(x.r<y.r); 25 } 26 int min_cnt(ll l,ll r){ 27 int s=0; 28 for(int i=59;i>=0;i--){ 29 if ((l&(1LL<<i))!=(r&(1LL<<i)))return s+((l&((1LL<<i)-1))>0); 30 s+=((l&(1LL<<i))>0); 31 } 32 return s; 33 } 34 void calc(ll k){ 35 if (k<0)return; 36 ll mn=p[1]; 37 for(int i=2;i<=n;i++)mn=min(mn,p[i]); 38 if (mn<0)return; 39 o.l=max(mn-k,0LL); 40 o.r=mn; 41 for(int i=1;i<n;i++)o.a[i]=p[i]-p[i+1]; 42 v.push_back(o); 43 } 44 int main(){ 45 scanf("%d%lld",&n,&m); 46 for(int i=1;i<=n;i++)scanf("%lld",&a[i]); 47 for(int i=0;i<=60;i++){ 48 for(int j=1;j<=n;j++)b[j]=make_pair(a[j]%(1LL<<i),j); 49 sort(b+1,b+n+1); 50 for(int j=1;j<=n;j++)p[j]=a[j]/(1LL<<i); 51 calc(m-i-min_cnt(0,b[1].fi)); 52 for(int j=1;j<n;j++){ 53 p[b[j].se]--; 54 if (b[j].fi<b[j+1].fi)calc(m-i-min_cnt(b[j].fi+1,b[j+1].fi)); 55 } 56 p[b[n].se]--; 57 if (b[n].fi<(1LL<<i)-1)calc(m-i-min_cnt(b[n].fi+1,(1LL<<i)-1)); 58 } 59 sort(v.begin(),v.end(),cmp); 60 for(int i=0,j=0;i<v.size();i=j){ 61 vv.clear(); 62 while ((j<v.size())&&(!check(v[i].a,v[j].a))){ 63 vv.push_back(make_pair(v[j].l,v[j].r)); 64 j++; 65 } 66 sort(vv.begin(),vv.end()); 67 ll mx=-1; 68 for(int k=0;k<vv.size();k++){ 69 if (mx<vv[k].fi)ans=(ans+vv[k].se-vv[k].fi+1)%mod; 70 else ans=(ans+max(vv[k].se-mx,0LL))%mod; 71 mx=max(mx,vv[k].se); 72 } 73 } 74 printf("%d",ans); 75 }View Code