P1582 倒水

传送门

思路：

　　类似于 袁绍的刁难 ， 一道二进制的模拟题。

　　先将：将原先的瓶子数 n 转换成二进制，二进制中 1 的个数就是合并后剩下的瓶子个数 。

主要利用树状数组的 lowbit 函数：

inline LL lowbit(LL u)

{

    LL res=0;

    for(;u;u-=u&-u)

        res++;

    return res;

}//统计二进制 1 的个数。

　　若二进制 1 的个数 ＞ k ，不断将二进制中最低位的 1 加 1 ，重新统计 1 的个数 ，直到 1 的个数 ≤ k。

Code:

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<string>

#include<cstdlib>

#include<stack>

#include<vector>

#include<queue>

#include<deque>

#include<map>

#include<set>

using namespace std;

#define lck_max(a,b) ((a)>(b)?(a):(b))

#define lck_min(a,b) ((a)<(b)?(a):(b))

typedef long long LL;

LL n,k,ans;

inline LL read()

{

    LL kr=,xs=;

    char ls;

    ls=getchar();

    while(!isdigit(ls))

    {

        if(!(ls^))

            kr=-;

        ls=getchar();

    }

    while(isdigit(ls))

    {

        xs=(xs<<)+(xs<<)+(ls^);

        ls=getchar();

    }

    return xs*kr;

}

inline void out(LL xs)

{

    if(!xs) {putchar(); return;}

    if(xs<) putchar('-'),xs=-xs;

    int kr[],ls=;

    while(xs) kr[++ls]=xs%,xs/=;

    while(ls) putchar(kr[ls]+),ls--;

}

inline LL lowbit(LL u)

{

    LL res=;

    for(;u;u-=u&-u)

        res++;

    return res;

}

int main()

{

    n=read(),k=read();

    while(lowbit(n)>k)

        ans+=n&-n,n+=n&-n;

    out(ans),putchar('\n');

return ;

}