1 条题解

  • 1
    @ 2021-05-27 23:26:18

    F题题解:
    可以看出
    ①奇数x出现次数一定没有偶数x+1多(1是唯一的特例)。这样看来,答案只会是偶数或1.
    ②我们这样来计算x在Path[1..n]的出现次数,且设x是偶数,则
    x-1,x
    2x-3 2x-2 2x-1 2x
    4x-7 4x-6 ... 4x
    ...
    它们的路径列表都包含了x。
    并且从这里我们还可以明显看出,x的出现次数一定比x+2多。所以,我们只需要在范围内对于所有偶数进行二分查找即可。
    Code:

    #include<bits/stdc++.h>
    using namespace std;
    #define ll long long int
    
    ll solve(ll x,ll y)//在1~x中假设答案是y,返回出现次数
    {
        if(x == y - 1 && x % 2) return 1;
        if(x < y)return 0;
        if (y == 1) return x; if(y == 2) return x - 1;
        
        ll ans,p = 2;
        if (y % 2) p = 1; //对于奇数(虽然本题并不需要考虑)
        ans = p;
        while(1) 
        {
            y *= 2; p *= 2;
            if(y - p + 1 > x) return ans;
            ans += min(y, x) - (y - p + 1) + 1;
        }
    } 
     
    int main()
    {
        ll n, k;cin>>n>>k;
        if(n == k) {cout<<1<<endl; return 0;}
        ll l = 1,r = n / 2 + 1, ans = 0;
        while(l <= r){
            ll mid = (l + r) / 2 ;
            if(solve(n, mid*2) >= k){
                ans = max(ans, mid * 2);
                l = mid + 1; 
            }
            else r = mid - 1;
        }
        cout<<ans;
        return 0;
    }
    
    • @ 2021-06-02 18:34:06

      太强啦

  • 1

信息

ID
1256
难度
8
分类
二分查找 点击显示
标签
递交数
39
已通过
6
通过率
15%
被复制
4
上传者