【P15245 [WC2026] 二进制】题解

wanglexi · 2026-02-13 19:19:37 · 题解

前言

84+0+0 严肃打铁。反思。

解法

规定 V=10^{18}，\textup{popcount}(x) 表示 x 在二进制下 1 的位数个数。

由于 y>x，那么无论何时对 y 做 \times 2 显然不优。

::::info[证明]

• 性质 1：两个数的最后一次操作不可能相同
• 性质 2：一次 \times 2 操作后面不可能有两个连续的 +1。

反证法，不妨两个数都经历过 \times2 操作，考虑两个数各自最后一次 \times2。由性质 2，对于两个数的任何一个，最后一次 \times2 操作之后要么不动了，要么只经过一次 +1。由性质一，两个数一定是一个最后一次 \times2 操作之后要么不动了，一个最后一次 \times2 操作之后只经过一次 +1。但是这样两个数最终的奇偶性不同，矛盾。 ::::

那么操作的形式肯定是 x 做若干次（可以为 0，下同） \times 2 和若干次 +1 是得他 \ge y，在对 y 做若干次 +1。

设 x 一共做了 z 次 \times2 操作，那么 z 一定满足这两种之一：

对于上面的第一种情况，无论 x 在何时 +1 必然不会更优，所以一定是 x 进行 z 次 \times 2，y 进行 x\times 2^z-y 次 +1。总共操作步数为 z+y-x\times 2^z。

对于第二种情况，容易想到的一种可能的操作是让 x 通过 \times2 和 +1 两种操作变成 y。一共 z 次 \times2，如果在第一次之前做 +1，则经过 z 次 \times2 后相当于 +2^z；在第一次 \times2 后 +1，再经过 z-1 次 \times2 后相当于 +2^{z-1}......在 z 次 \times2 后 +1，就相当于 +1。因此，+1 的操作次数为 \textup{popcount}\large(\normalsize(y-x\times2^z)\mod2^z\large)\normalsize+\lfloor\frac{y-x\times2^z}{2^z}\rfloor，加上 \times2 的操作次数 z 便是答案。

不过这么做不一定是最优的，例如当 x=5,y=47 时，最优的方案应该是 (5+1)\times2\times2\times2=48=47+1，总共 5 步解决，优于完全不对 y 操作的方案：\large(\normalsize(5\times2+1)\times2+1\large)\times2+1 的 6 步。

观察这个最优的方案，相当于让 x 通过 \times2 和 +1 两种操作变成 y+i 而不是 y。定量计算发现这么做操作总步数为 z+i+\textup{popcount}\large(\normalsize(y-x\times2^z+i)\mod2^z\large)\normalsize+\lfloor\frac{y-x\times2^z+i}{2^z}\rfloor（还要多加 i，这是用于使 y 变成 y+i 的 i 步 +1）。

于是考虑送有可能后第二种情况的答案就是 \min_{i=0}^{\infty}z+i+\textup{popcount}\large(\normalsize(y-x+i)\mod2^z\large)\normalsize+\lfloor\frac{y-x+i}{2^z}\rfloor。然而，i>\log V\ge\textup{popcount}(y-x)\ge\textup{popcount}\large(\normalsize(y-x)\mod2^z\large) 时，有：

故 i>\log V 没有 i=0 的情况优。所以情况二的答案 \min_{i=0}^{\infty}z+i+\textup{popcount}\large(\normalsize(y-x\times2^z+i)\mod2^z\large)\normalsize+\lfloor\frac{y-x\times2^z+i}{2^z}\rfloor=\min_{i=0}^{\lfloor\log V\rfloor}z+i+\textup{popcount}\large(\normalsize(y-x\times2^z+i)\mod2^z\large)\normalsize+\lfloor\frac{y-x\times2^z+i}{2^z}\rfloor。

写出代码，复杂度为 O(T\log V)，可以拿到 84 分。

::::info[84 分代码]

#include<bits/stdc++.h>
#define ll long long 
#define pb emplace_back
#define pii pair<int,int>
#define mkp make_pair
#define fir first
#define sec second
#define mod (998244353ll)
#define inf (1000000000000000000ll)
#define ppc __builtin_popcountll
using namespace std;
int t;
void init(int x,int t){return;}
ll binary(ll x,ll y){
    ll ans=inf,z=0;
    while((x<<1)<y){
        z++;
        x<<=1;
    }
    //情况1
    for(ll i=0;i<=63;i++)
        ans=min(ans,z+i+((y-x+i)>>z)+ppc((y-x+i)&((1ll<<z)-1)));
    //情况2
    z++;
    x<<=1;
    ans=min(ans,z+x-y);
    return ans;
}
// signed main(){
//  ios::sync_with_stdio(0);
//  cin.tie(0),cout.tie(0);
//  int c,t;
//  cin>>c>>t;
//  init(c,t);
//  while(t--){
//      ll x,y;cin>>x>>y;
//      cout<<binary(x,y)<<"\n";
//  }
//  return 0;
// }

::::

优化

复杂度瓶颈有两个地方：

1. 求 z；
2. 从 0 到 64 枚举 i。

求 z 的部分为：

z=0;
    while((x<<1)<y){
        z++;
        x<<=1;
    }

这部分简单推导公式可以转换为 \large\lfloor\normalsize\log_2{\lfloor\frac{y-1}x\rfloor}\large\rfloor。不过直接使用 C++ 中的 log2 函数比较慢，可以用 63 减去二进制下的前导 0 个数替代 log2，实现如下：

int log2_fast(uint64_t x) {
    return 63-__builtin_clzll(x);
}

对于从 0 到 63 枚举 i，目的是求 \min_{i=0}^{\lfloor\log V\rfloor}z+i+\textup{popcount}\large(\normalsize(y-x+i)\mod2^z\large)\normalsize+\lfloor\frac{y-x+i}{2^z}\rfloor，扔掉 z 以后进行观察，只要能够知道 \textup{popcount}\large(\normalsize(y-x+i)\mod2^z\large)\normalsize+\lfloor\frac{y-x+i}{2^z}\rfloor 和 \textup{popcount}\large(\normalsize(y-x)\mod2^z\large)\normalsize+\lfloor\frac{y-x+i}{2^z}\rfloor 的差，就能确定最优的 i。要确定这个，只需要确定：

2. 因为 i\le 63 所以需要 y-x\times2^z 二进制下后六位；

只需要预处理出这三个数值确定后令操作步数最优的 i，并且能 O(1) 求出上面三个要素，就可以 O(1) 得到情况 1 的答案。

唯一的难点在于确定上面的 2，可以先 +1，用 __builtin_ctzll 求出二进制末尾连续 0 的个数，就可以得到末尾连续 1 的个数。替换上面的 84 分代码，即可获得 100 分。（注：我们认为 __builtin_popcountll，__builtin_clzll 与 __builtin_ctzll 三个函数的时间复杂度均为 O(1)）

::::info[100 分代码]

#include<bits/stdc++.h>
#define ll long long 
#define pb emplace_back
#define pii pair<int,int>
#define mkp make_pair
#define fir first
#define sec second
#define mod (998244353ll)
#define inf (1000000000000000000ll)
#define ppc __builtin_popcountll
using namespace std;
int t;
ll pre[75][75][64];//第一维：相当于z；第二维：y-x扔掉后六位以后，末尾连续1的个数；第三维：后六位
void init(int x,int t){
    for(int zip=0;zip<=64;zip++){//z
        for(int prefix=0;prefix<=58;prefix++){//二进制下排除后六位后末尾连续1的个数
            for(int aft=0;aft<64;aft++){//二进制下后六位
                ll ans=inf;
                ll yx=(((1ll<<prefix)-1)<<6)+aft;
                for(ll i=0;i<=64;i++){
                    if(zip+i+((yx+i)>>zip)+ppc((yx+i)&((1ll<<zip)-1))<ans){
                        ans=zip+i+((yx+i)>>zip)+ppc((yx+i)&((1ll<<zip)-1));
                        pre[zip][prefix][aft]=i;
                    }
                }
            }
        }
    }
    return;
}
int log2_fast(uint64_t x) {
    return 63-__builtin_clzll(x);
}
ll binary(ll x,ll y){
    ll z=log2_fast((y-1)/x);
    x<<=z;
    int cnt=__builtin_ctzll(((y-x)>>6)+1);
    ll i=pre[z][cnt][(y-x)&63];
    return min(z+i+((y-x+i)>>z)+ppc((y-x+i)&((1ll<<z)-1)),z+1+(x<<1)-y);
}
//signed main(){
//  freopen("txt.txt","r",stdin);
//  ios::sync_with_stdio(0);
//  cin.tie(0),cout.tie(0);
//  int c,t;
//  cin>>c>>t;
//  while(t--){
//      ll x,y;cin>>x>>y;
//      cout<<binary(x,y)<<"\n";
//  }
//  return 0;
//}

::::