朝田诗乃 的博客

朝田诗乃 的博客

题解 P1582 【倒水】

posted on 2016-11-16 18:36:12 | under 题解 |

这个题解写得很详细给蒟蒻看的,大神看下面的。

依题意可得,每2^x个瓶子可以合成一个瓶子。

以样例13 5来说,

13=8+4+1.

也就是说13个瓶子可以合并成3个瓶子,但此时不满足“小于k个”条件,所以需要购买空瓶子。

买1个,14=8+4+2,没有什么卵用。

买2个,15=8+4+2+1,好像更糟。

买3个,16=16,搞定。

根据上述过程可以得出初步思路:算出n可以分成几个2^x相加,也就是可以合成几个瓶子。如果结果>k那么买一个空瓶重复上述过程。

但是这里需要一个小技巧,如果你分解数的时候暴力枚举,时间肯定爆炸。

由于是2^x,所以我们很容易地想到2进制。所有2的倍数的二进制都是100000……(好多好多的0)

观察样例13的二进制: 1101.相当于二进制1000+100+1即十进制8+4+1.

得出结论,要统计有多少个因子(好像不叫因子,反正就那意思),只需要数数当前瓶子数的2进制下有多少个1即可。

那么我们需要一位位比较。如果把整个数转成二进制时间不说了。

如何快速的获得此数二进制数下的某一位呢?

我们只需要构造一个数,这个的二进制数是0000000000000000000100000000(1<<N)

然后再把当前数与该数按位与,就可以得出当前数二进制下某一位。(啥?你不知道啥叫按位与?)

交上去发现悲伤的超时了一个点。

所以我们需要优化。其实每一次加1的目的就是为了让数中的0变少。就是需要进位。

此时我们把瓶子数量的二进制取反再加一,进位就变得容易多了(好像只快一点点)

稍有常识的人都会知道,n的二进制取反再加一就是-n。

好了看代码吧。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <bitset>
using namespace std;
int main()
{
    long long n,k,ping=0,count1;
    scanf("%lld%lld",&n,&k);
    while(1)
    {
        count1=0;
        for(int i=0;i<64;i++)
        if((n&((long long)1<<i))>0)count1++;
        if(count1<=k)break;
        //cout<<count1<<" "<<n<<endl;
        ping+=n&(-n);
        n+=n&(-n);
        //system("pause");
    }
    printf("%d\n",ping);
}