WC2026 T1

Register_int · 2026-02-09 13:56:05 · 题解

没有人类了。

由于数据量极大，下文讨论中认为 __builtin_popcount 函数的时间复杂度为 \mathcal{O}(\log\log V)。

\mathcal{O}(T\log V\log\log V)

不难发现你给 y 乘二纯粹是闲着没事干。所以我们要干的事情是将 x 一直倍增，使其尽可能贴近 y。分为两种情况：

1. 倍增了 t 次，2^t x>y。此时操作次数为 t+2^tx-y。
2. 倍增了 t 次，2^t x\le y，还需要补上 k=y-2^t。

显然第一类要选尽可能小的 t，第二类要选尽可能大的。这个可以用 __lg 算。问题在于，在第二类操作中，答案并不是简单的 k 中 1 的个数，我们可以搞出一个比 k 大的数再减回去。枚举减了几次可以得到这部分代价为：

直接枚举 i 还是太菜了。这是因为一次次 +1 浪费了太多步数。我们的目标是要减少 popcount，所以可以改成每次加 lowbit，这样只会加 \mathcal{O}(\log\log V) 次，期望得分 96。

\mathcal{O}(\log V\log\log V+T\log\log V)

不妨再将 i 分为两类：

1. 我们的目标比较长远，要把很长一段 1 填平。这个时候把最低 6 位直接填平一定是不劣的。
2. 没那么多 1 让我们消，那么我们只关心最后 6 位内的情况。这部分可以预处理出对应的答案。

第一类直接位运算解决，第二类提取低六位查表即可。期望得分 100。

#include <bits/stdc++.h>
#include "binary.h"

using namespace std;

typedef long long ll;

int f[64], pc[70];

void init(int c, int t) {
    for (int i = 0; i < 70; i++) pc[i] = __builtin_popcount(i);
    for (int i = 0; i < 64; i++) {
        for (int j = 0; j < 6; j++) f[i] = max(f[i], pc[i] - pc[i + j] - j);
    }
}

inline 
int calc(ll x) {
    if (!x) return 0; ll y = (x | 63) + 1;
    return min<int>(__builtin_popcountll(y) + y - x, __builtin_popcountll(x) - f[x & 63]);
}

ll binary(ll x, ll y) {
    int cnt = __lg(y) - __lg(x); x <<= cnt; if (x > y) x >>= 1, cnt--;
    return cnt + min<ll>((x << 1) - y + 1, (y - x >> cnt) + calc(y - x & (1ll << cnt) - 1));
}

Bonus：\mathcal{O}(\sqrt[3]V+\log V\log\log V+T)

额就是你打表一下 popcount，就这样。但是寻址三次和 popcount 哪个快我确实不好说。这个可以做到理论最优就是了。

#include <bits/stdc++.h>
#include "binary.h"

using namespace std;

typedef long long ll;

const int B = 1 << 21;

int f[64], pc[1 << 21];

void init(int c, int t) {
    for (int i = 1; i < B; i++) pc[i] = pc[i & i - 1] + 1;
    for (int i = 0; i < 64; i++) {
        for (int j = 0; j < 6; j++) f[i] = max(f[i], pc[i] - pc[i + j] - j);
    }
}

inline int popcount(ll x) { return pc[x & B - 1] + pc[x >> 21 & B - 1] + pc[x >> 42 & B - 1]; }

inline 
int calc(ll x) {
    if (!x) return 0; ll y = (x | 63) + 1;
    return min<int>(popcount(y) + y - x, popcount(x) - f[x & 63]);
}

ll binary(ll x, ll y) {
    int cnt = __lg(y) - __lg(x); x <<= cnt; if (x > y) x >>= 1, cnt--;
    return cnt + min<ll>((x << 1) - y + 1, (y - x >> cnt) + calc(y - x & (1ll << cnt) - 1));
}