AtCoder - arc086_d Shift and Decrement分析与实现

分析与思路

可以把操作流程表示成下图

以进行四次除法操作为例：

这里有一个关键点：对于每个p_i (0<= i <=x-1) ，x是除法操作的次数，如果p_i>=2，可以将2个p_i的减法操作去掉，在p_(i+1)中增加一个减法操作，这样可以用更少的减法操作次数达到同样的效果，所以最终，每个p_i (0<= i <=x-1)，p_i要么是0，要么是1，p_x中保存了自底向上累计的减法，所以p_x取值任意

还可以继续简化操作，p_i (0<=i<=x-1)如果是1的话，可以将其去除，并让p_0增加2的 i 次方，此时虽然简化了操作，但是会增加操作次数

如果现在把操作次数统计为p_0+x+p_x，这样会用更多的次数完成相同的操作，这里有一个关键点，根据上面的p_0被累加的方式，p_0的二进制表达中1的个数是真实的p_0到p_(x-1)的操作次数的和，例如p_0 = 11011010，这代表着在p_0被增加前，p_0=0 p_1=1 p_2=0 p_3=1等等

这样，操作被简化为：

第一步：先进行p_0次减法操作，这里令y=p_0

第二步：再进行x次除法操作，

第三步：最后再进行p_x次减法操作，这里令z=p_x

操作次数为：y的二进制表达中1的出现次数+x+z

然后这里有一个关键观察，y的值不会超过2^x，就算y的二进制表达每一位都是1，也比2^x小1，于是可以将a_i表示成 a_i = b_i * 2^x + c_i，其中 0<=c_i<2^x，因为这样表示之后，

如果c_i>=y 则 经过前两步的操作，a_i变成b_i

如果c_i<y，则经过前两步的操作 a_i变成b_i - 1

将所有的c_i排序，去重，则当y处于以下的某一区间时，得到的前两步操作后的结果序列是相同的

[0,c1]

[c1+1,c2]

[c2+1,c3]

... ...

[c_(t-1) + 1, c_t] 其中 t 是c_i排序去重后的数的个数

当p处于某一区间时，为让所需操作次数减少，应该让p的二进制表达中1的个数尽量少（求一个区间[a,b]中的数的二进制表达中1的数目最少的数的方法见后）

现在，思路可以是，枚举x，因为指数爆炸，x的范围是[0,60]，然后枚举y，具体方式是对每个区间求二进制表达中1的个数最少的数就是这个区间的y，然后计算经过前两步操作后得到的数的序列，同时也根据k和前两步操作的次数，计算出第三步操作可以实施的次数，第三步操作其实是在整体移动这个数列
 

这里有一个关键点，用一个数组可以描述一个数列（长度为n）的形状，这个数组中的每个元素依次是：
a[1]-a[1] a[2]-a[1] a[3]-a[1] ... a[n]-a[1]

当数列的形状相同时，只要看a[1]有多少个不同的取值，就知道这个数列有多少不同的取值情况

记录每个数列的形状下，a[1]有多少个不同取值就可以

我们的算法在枚举前两步后，可以得到第三步的一个操作数量范围，这对应着某个形状下，一个a[1]的取值范围，a[1]的取值范围们的并集就是能取到的a[1]的值，这个并集中元素的数量就是这种形状下不同序列的数量

求区间[a,b]中二进制表达中1的数目最小的数的方法

设一个数p的二进制表达中1的数目为popcount(p) 

求(a , b]中的答案可以用这样的方法，从高位到低位一位一位对比a和b，如果该位相同，则结果的该位和该位上的值相同，如果该位不同，则说明a的该位上是0，b的该位上是1，那么让结果的该位为1，后面的所有位置置0就可以

将[a,b]转化为(a-1,b]使用上述算法即可，但是有一个特殊情况，如果[a,b]中a是0，那么不能用上面的方法，应该直接返回结果0

合并区间的方法

记每个区间[l,r]

将区间按照左端点大小进行排序，记录当前已经处理到的位置的下一个位置为L，

分类讨论：如果一个区间的右端点小于L，那么不处理这个区间，否则，如果这个区间的左端点小于等于L，则区间带来的贡献是r-L+1，之后L=r+1，如果这个区间的左端点大于L，则区间带来的贡献是r-l+1，之后L=r+1

实现中的注意点

如果1<<60，会导致溢出，要写成1LL<<60

可以用map<vector<ll>,ll> 来表示某一种形状的序号，用tot表示当前形状的总数，如果当前形状的序号是0，那么当前形状的序号被编为tot+1

复杂度分析略

#include<bits/stdc++.h>
using namespace std;#define ll long longconst ll maxn=200+5,mod=1000000007;
ll power[maxn],a[maxn],b[maxn],c[maxn],fnal[maxn],c1[maxn];
ll k,n,tot;map<vector<ll>,ll> mp;vector<pair<ll,ll>> range[maxn*100];ll find_minpopcount(ll x,ll y){if(x==-1) return 0;ll ans=0;for(ll i=60;i>=0;i--){if((x&(1LL<<i))==0 && (y&(1LL<<i))){ans+=(1LL<<i);break;}if(x&(1LL<<i)) ans+=(1LL<<i);}return ans;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);//预处理2的x次方power[0]=1;for(ll i=1;i<=60;i++) power[i]=power[i-1]*2;//cout<<power[59]<<"\n";//cout<<power[60]<<"\n";//cout<<find_minpopcount(4,6)<<"\n";cin>>n>>k;for(ll i=1;i<=n;i++) cin>>a[i];for(ll x=0;x<=60;x++){for(ll i=1;i<=n;i++){b[i]=a[i]/power[x];c[i]=a[i]%power[x];c1[i]=c[i];}stable_sort(c1+1,c1+1+n);ll t=unique(c1+1,c1+1+n)-(c1+1);c1[0]=-1;for(ll i=1;i<=t;i++){ll y=find_minpopcount(c1[i-1],c1[i]);ll cnt=__builtin_popcountll(y);ll flag=1;for(ll j=1;j<=n;j++){fnal[j]=b[j];if(c[j]<y) fnal[j]--;if(fnal[j]<0) {flag=0;break;}}if(flag==0) continue;ll z=k-x-cnt;if(z<0) {continue;}/*cout<<"发现合法结果："<<"\n";printf("x=%d cnt=%d\n",x,cnt);for(ll i=1;i<=n;i++) cout<<fnal[i]<<" ";cout<<"\n";*/ll minfnal=*min_element(fnal+1,fnal+1+n);ll max_decrease_times=min(minfnal,z);pair<ll,ll> p={max(fnal[1]-max_decrease_times,0LL),fnal[1]};//求差分模式vector<ll> vec;for(ll j=1;j<=n;j++){vec.push_back(fnal[j]-fnal[1]);}if(mp[vec]==0) {mp[vec]=++tot;}range[mp[vec]].push_back(p);}}ll ans=0;for(ll i=1;i<=tot;i++){//printf("第%lld种差分模式：\n",i);stable_sort(range[i].begin(),range[i].end());ll L=0;for(ll j=0;j<range[i].size();j++){pair<ll,ll> tmp=range[i][j];ll l=tmp.first,r=tmp.second;//printf("区间：[%lld , %lld]\n",l,r);if(r<L) continue;if(l<=L) ans=(ans+(r-L+1))%mod;else ans=(ans+(r-l+1))%mod;L=r+1;}}cout<<(ans+mod)%mod<<"\n";return 0;
}