宝塔服务器面板，一键全能部署及管理，送你10850元礼包，点我领取

Codeforces-579A   

Raising Bacteria

Codeforces Round #320 (Div. 2) [Bayan Thanks-Round]

Time Limit:1000ms Memory Limit:262144 kB

问题描述你是一个细菌爱好者。你想在一个盒子里培养一些细菌。起初，这个盒子是空的。每天早上，你可以在盒子里放任意数量的细菌；每天晚上，细菌将会繁殖，一分为二。你在某些时候，希望看到正好$x$个细菌。这些天内，你需要放至少多少个细菌呢？输入一个正整数$x$（$1≤x≤10^9$）输出唯一的正整数：答案。样例Example 1：

Input

5

Output

2

Example 2
Input

8

Output

1

这题本身不难，主要是要看懂题目的意思。题目比较巧合的地方是，细菌只能一分二繁殖。$k$天内，一个细菌就可能变成$2^k$个，因此，最后要得到$x$个细菌，只要$x=sum_{n=1}^{N}t_i·2^{k_i}$成立；若初始细菌数量最少，则系数 $t_i$ 都为1。这与无符号整数的表示非常神似，因此可以使用位操作的方法来解。当然直接进行求解也是可以的。

 1 #include<iostream>
 2 int main()
 3 {
 4     using namespace std;
 5     int n;
 6     cin >> n;
 7     int count = 0;
 8     int sn = 536870912;
 9     for (;;)
10     {
11         if (n == 0)
12             break;
13         if (n / sn != 0)
14             count++;
15         n = n % sn;
16         sn /= 2;
17     }
18     cout << count;
19     return 0;
20 }