P8072 题解

· · 题解

P8072 题解

题目指标 [COCI2009-2010#7] COKOLADA.

该文章同步发表于 我的博客 内。

审核一经通过，他人不得盗用博客。若为通过，引用时需注明出处，并私信作者。

正解

直接求出距离 k 的数值最近的大于等于 k 的 2 的非负整数幂的数值 q 并输出。

对于这题，我们同样需要简单地进行分类讨论。

  1. 当 q=k 的时候，我们可以直接输出。

  2. 当 q\ne k 的时候，我们需要求出最少需用到多少个 2 的非负整数幂的数值，记其为 s.

细节处理

这一部分对初学者非常重要，如果稍有不慎就可能导致爆零，但是对于编程老手而言，这都是基础内容。

  1. 不论你的 q 是在栈内还是在栈外定义的，都要记住要将 q 的初值赋为 1，因为在栈内：我们不保证 q=1，而在站外， q 的初值是 0.

  2. 切记第一个 while 循环内的判断条件要是 q<k 而不是 q\leq k，最简单的 hack 数据就是 k=2 时，期望得到的结果是 2\ 0 而不是 4\ 1.

  3. 最容易因粗心导致此问题，漏掉空格：即打印第二种情况时，更容易漏掉空格，而相比于 C++，C 语言使用者在使用时应当更加小心。

代码

正解代码如下：

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int k,q=1,s;//切记 q=1
int main()
{
    scanf("%d",&k);
    while(q<k)
        q*=2;// 2 的非负整数次幂的数值
    if(q==k)
        return !printf("%d 0",q);//第一种情况
    else printf("%d ",q);//第二种情况（注意不要打漏空格）
    while(k>0)
        q/=2,k%=q,s++;
    return !printf("%d",s);
}