题解：P13830 【MX-X18-T2】「FAOI-R6」二进制与一 III（bit）

ylch · 2025-08-24 18:36:57 · 题解

题目的特殊性质很有帮助。发现 3 是大于等于 2 中最小的二进制全为 1 的数，所以考虑把 n 尽可能拆出更多的 3 一定是最优的。

考虑对余数分类讨论：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve()
{
    ll n; cin >> n;
    ll ans;
    if(n % 3 == 0) ans = (n / 3) * 2;
    else if(n % 3 == 1) ans = (n / 3 - 1) * 2 + 2;
    else ans = (n / 3) * 2 + 1;
    cout << ans << '\n';
}

signed main()
{
    ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int T; cin >> T;
    while(T --) solve();
    return 0;
}