Codeforces Round #608 (Div. 2) E. Common Number (二分,构造)

题意:对于一个数\(x\),有函数\(f(x)\),如果它是偶数,则\(x/=2\),否则\(x-=1\),不断重复这个过程,直到\(x-1\),我们记\(x\)到\(1\)的这个过程为\(path(x)\),它表示这个过程中所有\(x\)的值,现在给你一个数\(n\)和\(k\),要你找出最大的数\(x\),并且\(x\)在\(path[1,n]\)中出现的次数不小于\(k\).
题解:我们对于\(x\)可以选择分奇偶来讨论.

1.假如\(x\)为奇数,那么根据题意,我们知道\(x,2x,2x+1,4x,4x+1,4x+2,8x,8x+1,8x+2,8x+3,8x+4....\)这些数包含且只有这些数包含\(x\).

2.假如\(x\)为偶数,那么\(x,x+1,2x,2x+1,2x+2,2x+3,4x,4x+1,4x+2,4x+3,4x+4,4x+5,4x+6,4x+7,...\)这些数包含且只有这些数包含\(x\).

那么我们就可以分奇偶数来二分求答案.
代码:

#include <bits/stdc++.h>

#define ll long long

#define fi first

#define se second

#define pb push_back

#define me memset

#define rep(a,b,c) for(int a=b;a<=c;++a)

#define per(a,b,c) for(int a=b;a>=c;--a)

const int N = 1e6 + 10;

const int mod = 1e9 + 7;

const int INF = 0x3f3f3f3f;

using namespace std;

typedef pair<int,int> PII;

typedef pair<ll,ll> PLL;

ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}

ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}

ll n,k;

bool check(ll x){

	ll tmp=x;

	ll cnt=0;

	ll cur;

	if(x&1) cur=1;

	else cur=2;

	while(x<=n){

		cnt+=min(cur,n-x+1);

		x<<=1;

		cur<<=1;

	}

	if(cnt>=k) return true;

	return false;

}

int main() {

    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	cin>>n>>k;

	ll l=0,r=n;

	ll ans=1;

	//odd:

	while(l<r){

		ll mid=(l+r+1)>>1;

		ll x=mid*2+1;

		if(check(x)) l=mid;

		else r=mid-1;

	}

	ans=max(ans,2*l+1);

	l=0,r=n;

	//even

	while(l<r){

		ll mid=(l+r+1)>>1;

		ll x=mid*2;

		if(check(x)) l=mid;

		else r=mid-1;

	}

	ans=max(ans,2*l);

	cout<<ans<<'\n';

    return 0;

}

巴特西

Codeforces Round #608 (Div. 2) E. Common Number (二分,构造)

最新文章

热门文章