自动搬运

查看原文

来自洛谷，原作者为

	wimg6_ 1+1=？

搬运于2025-08-24 22:35:42，当前版本为作者最后更新于2022-01-26 17:55:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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);
}