AT_arc161_b题解

code_hyx · 2023-06-29 21:10:08 · 题解

这不是 A 题的难度吗。
显然，N<7 时，无解。
然后，枚举三个二进制位下的 1 的位置，可以使用贪心法，原因也很显然，因为如果高位有 1，那么一定比 1 在低位的数要大。再说得详细一点，2^n=2^m \times 2^{n-m}，在后面补 1，就相当于给 2^{n-m} 加上 2^{n-m-k}（k 为正整数），2^{n-m-k} 一定不如 2^{n-m} 大，所以不可能加出比 2^n 还大的结果。
那么，从高位到低位枚举就行了，优先满足高位的 1。
常数约为 64 \times 3，有点大，但可以稳过这道题。
代码：

#include<bits/stdc++.h>
using namespace std;
long long t,n;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--)
    {
        cin>>n;
        if(n<7)
        {
            cout<<-1<<"\n";
            continue;
        }
        long long maxx=0,maxx1=0,maxx2=0,ans=0;
        for(long long i=62;i>=0;i--)
        {
            if(n-(1LL<<i)>=3)
            {
                maxx=i;
                ans+=(1LL<<i);
                break;
            }
        }
        for(long long i=maxx-1;i>=0;i--)
        {
            if(ans+(1LL<<i)<n)
            {
                maxx1=i;
                ans+=(1LL<<i);
                break;
            }
        }
        for(long long i=maxx1-1;i>=0;i--)
        {
            if(ans+(1LL<<i)<=n)
            {
                maxx2=i;
                ans+=(1LL<<i);
                break;
            }
        }
        cout<<ans<<"\n";
    } 
    return 0;
}