首页 > 其他 > 详细

luogu2431 正妹吃月饼

时间:2018-05-17 23:52:06      阅读:19      评论:0      收藏:0      [点我收藏+]

标签:AS   OS   long long   def   assert   using   大小   ostream   进行   

题目大意

求一个正整数集合\(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\)呢?

  1. \(A,B\)二进制最高位数不同,则结果为\(A\)最高位数-1。如\(A=(10100)_2,B=(101)_2\),则结果为4,因为\((1111)_2\)
  2. 满足情况1时的特殊情况。若\(A\)用二进制表示全是1,则结果为情况1的结果加1.如\(A=(11111)_2,B=(101)_2\),则结果为5,因为\((11111)_2\)
  3. 若最高位数相同,则把两个数的最高位去掉,转化为子问题,再在此基础上+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 正妹吃月饼

标签:AS   OS   long long   def   assert   using   大小   ostream   进行   

原文:https://www.cnblogs.com/headboy2002/p/9053958.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号