P1582倒水

推了一个多小时的式子，ac后一看题解，7行代码搞定

emmmm我还是太菜了

传送

蒟蒻解法：

不管怎么倒水，最终所有瓶子里面的水的数量一定可以用2^k表示出来。

n最终可以合并成几个瓶子呢？

我们可以把n分解为多个2^k相加的形式，例如：13=2³+2²+2⁰，所以13最少合并到3个瓶子里面

求n最少能合并到几个瓶子里面，正是看n的二进制表示里面有多少个1

如果1的数量cnt小于等于k,则直接输出0。

否则：从第一个是1的位置+1开始，扫到cnt-k+1个1的位置，中间如果是0，ans就加上2^{是0的位置},最后ans+2^{第一个是1的位置}

粗略的解释一下

假设某个数的二进制表示是1000101001000，k=2

加上2³:1000101010000

加上2⁴:1000101100000

加上2⁵:1000110000000

加上2⁷:1001000000000

对比刚开始的n:100101001000

标0的是加完后最后一个1所在的位置。

我们发现在原始的n的第一个1开始，一直到cnt-k+1的1的位置，中间是0的地方都要在答案上加2^k(当然第一个是1的地方除外)

maybe代码会好懂一些

#include<bits/stdc++.h>

using namespace std;

int n,a[],b[],cnt,k,now,ans;//a[i]记录n的二进制表示中，2^i所对应的位上是0还是1，b[i]记录第i个1的位置

long long mi[];//mi[i]为2^i

int read()

{

   char ch=getchar();

   int x=;    bool f=;

   while(ch<''||ch>'')

   {

        if(ch=='-')

         f=;

        ch=getchar();

   }

   while(ch>=''&&ch<='')

   {

       x=(x<<)+(x<<)+(ch^);

       ch=getchar();

   }

   return f?-x:x;

}

void init()

{

    mi[]=;

    for(int i=;;i++)

    {

        mi[i]=mi[i-]*;

        if(mi[i]>n)break;//mi不开long long见祖宗

    }

}

int main()

{

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

    init();

    while(n)

    {

        a[now]=n&;//now代表当前是2^now所代表的位置

        if(n&)

        {

            b[++cnt]=now;

        }

        now++;

        n>>=;

    }

    if(cnt<=k)//特判

    {

        printf("");return ;

    }

    int m=cnt-k+;

    ans+=mi[b[]];

    for(int i=b[]+;i<=b[m];i++)

    {

        if(a[i]==)ans+=mi[i];

    }

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

}

大佬做法：

因为所有的水都是由两份相同的水合并而成的，因此每瓶水的体积一定是2^i,(i\in N)2i,(i∈N)升。

最后保留k个瓶子，那么最后总的升数的二进制表示中，1的个数一定<=k。

那么我们只要贪心地往n上加上lowbit(n)即可。

这个lowbit就是树状数组那个lowbit啦

简化代码的trick：

使用内置函数\_\_builtin\_popcount()来计算一个数的二进制表示中1的数量。

这样下来，代码简化到仅剩7行。

惊不惊喜，意不意外？

------------------------摘自洛谷第一篇题解

#include <cstdio>

int n, k, ans;

int main() {

    scanf("%d%d", &n, &k);

    while(__builtin_popcount(n) > k) ans += n & -n, n += n & -n;

    printf("%d", ans);

}

巴特西

P1582倒水

最新文章

热门文章