Articles12
Tags2
Categories0

CF1271E-Common Number


这道题,一开始以为是什么牛逼的数学题 后来发现好像答案满足单调性??

于是二分check就完事了 稳妥一点就分奇偶分别check 像我就喜欢骚一点 直接一遍check

复杂度O(logn^2) 快的一批

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+50;
ll n,k;
int ok(ll x){
    ll cnt=1;ll l=x,r=x;
    if(x%2==0&&x<n){
        cnt++;r++;
    }
    while(1){
        ll l1=l*2,r1=r*2+1;
        if(r1>n){
            if(l1>n){
                return cnt>=k;
            }
            return (cnt+n-l1+1)>=k;
        }
        cnt+=r1-l1+1;r=r1;l=l1;
    }

}
ll bs(ll l,ll r){
    ll ans=l;
    while(l<=r){
        ll mid=(l+r)/2;
        if(mid%2&&mid+1<=r){
            mid+=1;
        }
        if(ok(mid)){
            ans=mid;
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    return ans;
}
int main(){
    scanf("%lld%lld",&n,&k);
    printf("%lld\n",bs(1,n));
}
Author:西瓜喵喵.
Link:https//:ForgGYLH.github.io/2019/12/17/CF1271E-Common%20Number/
版权声明:本文采用 CC BY-NC-SA 3.0 CN 协议进行许可