题解 P1582 【倒水】

TARMO · 2019-01-02 18:42:28 · 题解

（一个不会二进制的蒟蒻在dalao中瑟瑟发抖）

一开始的思路当然是模拟啦，然后就是愉快地爆内存，超时间...（我还非常天真地提交了好几次）

后来终于意识到这道题需要一点数学思想，然后测评结果就变得五颜六色起来（爽）

思路和大多数dalao都不一样，就发一篇题解吧

解释都在代码里

//你没看错，代码改到了如此之短
//正经点啊，开始一场头脑风暴啦
//既然只剩下不到k个瓶子，那我们不妨看成剩下k个瓶子（无视特殊情况）
//剩下的k个瓶子每个里肯定都有2^n升水，而所有水的总和就是n+sum（sum为输出结果）
//然后最后一个瓶子肯定大于sum
//给自己一点时间思考一下
//这样思路就明确了，开始码代码
#include<bits/stdc++.h>//妙甚的万能头
using namespace std;//妙甚的命名空间
unsigned long long n,k,sum;//妙甚的变量定义
int main()
{
    cin>>n>>k;//妙甚的输入
    if(k>32) k=32;//本句可以无视
    //敲黑板！！！
    while（k>1&&n>0)//n>0不加的话程序会卡死于此
    for(int i=63;i>=0;i--)
    if(pow(2,i)<=n){n-=pow(2,i);k--;break;}//任何一个自然数都可以拆分成若干个2的幂的和
    //敲黑板的手停下
    if(n==0){cout<<"0";return 0;}//特判
    for(int i=0;;i++)
    {
        if(pow（2,i)>=n)
        {
            cout<<(unsigned long long)pow(2,i)-n;//妙甚的输出
            break;//看看for循环后边的括号里
        }
    }
    return 0;
}

本蒟蒻的第一篇题解（防抄袭）