题目大意

求一个正整数集合\(K\)，使得\(\sum_{k\in K}2^k\in[A,B]\)，且\(|K|\)最大。\(A,B\)大小在long long范围内。

思路

\(\sum_{k\in K}2^k\)？这不就是一个二进制数，对于该数上的每一个数位\(k\)，若\(k\in K\)，则该数位上的数为1，否则为0么？

所以原题就变成了：求一个整数\(x\)，使得\(x\in[A,B]\)，且其用二进制表示的1的个数最多。

怎么求这个\(x\)呢？

若\(A,B\)二进制最高位数不同，则结果为\(A\)最高位数-1。如\(A=(10100)_2,B=(101)_2\)，则结果为4，因为\((1111)_2\)。
满足情况1时的特殊情况。若\(A\)用二进制表示全是1，则结果为情况1的结果加1.如\(A=(11111)_2,B=(101)_2\)，则结果为5，因为\((11111)_2\)。
若最高位数相同，则把两个数的最高位去掉，转化为子问题，再在此基础上+1.如：\(A=(110100)_2,B=(100101)_2\)，则结果为5，因为把两个数最高位的1去掉就成了情况1的例子，再在此基础上+1便是。

注意

因为A、B是long long，所以不能直接用1进行左移操作（因为默认的结果是int）。
递归时，当A、B都是0时要提前跳出。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <cassert>

using namespace std;

#define ll long long

int GetHighbitPos(ll x)

{

	int ans = -1;

	while (x)

	{

		ans++;

		x >>= 1;

	}

	return ans;

}

ll All(int n)

{

	ll x = 1;

	return (x << n + 1) - 1;

}

ll Erase(ll x, int pos)

{

	ll t = 1;

	return x & ~(t << pos);

}

int Dfs(ll below, ll above)

{

	if (above == 0)

		return 0;

	int pa = GetHighbitPos(above), pb = GetHighbitPos(below), ans;

	assert(pa >= pb);

	if (pa > pb)

	{

		ans = pa;

		if (above == All(pa))

			ans++;

		return ans;

	}

	else

		return 1 + Dfs(Erase(below, pb), Erase(above, pa));

}

int main()

{

	ll below, above;

	cin >> below >> above;

	cout << Dfs(below, above) << endl;

}

巴特西

luogu2431 正妹吃月饼

题目大意

思路

注意

最新文章

热门文章