题目链接：https://codeforces.com/contest/1362/problem/C

题意

计算从 $0$ 到 $n$ 相邻的数二进制下共有多少位不同，考虑二进制下的前导 $0$ 。（$1≤n≤10^{18}$）

题解

逐位考虑。因为值是连续的，所以从右至左第 $i$ 位的 $01$ 周期为 $2^i$ 。计算出完整的 $01$ 周期个数 $t$，每个完整的周期内有一对 $01$ 相邻，相邻的完整周期间共有 $t - 1$ 对 $01$ 相邻，然后考虑多余的周期长度，如果之前有完整的 $01$ 周期且有多余的周期，答案 $+1$，如果多余周期长度大于完整周期的一半，答案 $+1$ 。

Tips

移位较多应使用 1LL 。

代码

#include <bits/stdc++.h>

using ll = long long;

using namespace std;

void solve() {

    ll n; cin >> n;

    ++n;

    ll ans = 0;

    for (int i = 1; i < 64; i++) {

        ll len = (1LL << i);

        ll t = n / len;

        ans += t + max(0LL, t - 1) + (t and n % len > 0) + (n % len > len / 2);

        if (len >= n) break;

    }

    cout << ans << "\n";

}

int main() {

    int t; cin >> t;

    while (t--) solve();

}

巴特西

Codeforces Round #647 (Div. 2) C. Johnny and Another Rating Drop（数学）

题意

题解

Tips

代码

最新文章

热门文章