洛谷【P2431】正妹吃月饼

二进制前置技能：https://www.cnblogs.com/AKMer/p/9698694.html

题目传送门：https://www.luogu.org/problemnew/show/P2431

表示比起正妹更喜欢软妹

我们把\(a\)和\(b\)全部转换成二进制，就会得到两个长度为\(62\)的二进制串。这两个二进制串的第\(i\)位可能为\(0\)或\(1\)，分别表示\(a\)和\(b\)的二进制表示下的第\(i\)位（从\(0\)开始）。

对于\(a,b\)相等，只有一种情况，我们就不考虑了。

然后，因为\(b>a\)，所以必定有一位\(pos\)，使得\(b\)二进制下第\(pos\)位为\(1\)，\(a\)二进制下第\(pos\)位为\(0\)。即：

在\(a,b\)的二进制表示下，第\(62\)位到第\(pos+1\)位是一模一样的，后面的就不一样了。对于一样的，我们不予考虑。

我们设\(pos\)到\(1\)那一段的，\(b\)的为\(bob\)，\(a\)的为\(boa\)。那么\(bob\)肯定是\(1.......\)，\(boa\)肯定是\(0........\)。

显然，\(0111111...1111111\)肯定大于\(boa\)并且肯定小于\(bob\)。所以如果\(bob\)不是\(111111....111111\)，那么答案就是\(011111....1111111\)。

时间复杂度：\(O(logn)\)

空间复杂度：\(O(logn)\)

代码如下：

#include <cstdio>

#include <algorithm>

using namespace std;

#define ll long long

ll a,b,pos,ans,res;

bool boa[63],bob[63];

ll read() {

	ll x=0,f=1;char ch=getchar();

	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

	return x*f;

}

int main() {

	a=read(),b=read();

	for(int i=0;i<63;i++)

		boa[i]=a&1,a>>=1;

	for(int i=0;i<63;i++)

		bob[i]=b&1,b>>=1;//转化二进制

	for(pos=62;~pos;pos--)

		if(bob[pos]>boa[pos])break;//找pos

	for(int i=62;i>pos;i--)ans+=bob[i];//统计两个串一样部分1的个数

	for(int i=pos;~i;i--)res+=bob[i];//统计bob后面1的个数

	ans+=max(pos,res);//bob后面1的个数与一个0后全是1取max

    printf("%lld\n",ans);

	return 0;

}

巴特西

洛谷【P2431】正妹吃月饼

最新文章

热门文章