本文主要是介绍【Code Forces 320A】【二进制拆分】Raising Bacteria 细胞繁殖 每天倍增,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
【传送门】
http://codeforces.com/contest/579/problem/A
【题意】
在培养皿中,每个细胞每天会繁殖,数量*2
我们可以在任意天加入任意数量的细胞入培养皿中。
想要知道最少加入多少个细胞,可以使得有一天,培养皿中细胞的数量会恰好为x
【类型】
二进制拆分
【分析】
看样例就瞬间想到,这题是求二进制中有多少个1
然而倒着思考也很容易解释—
比如当前x二进制表示为——
101011
我们可以在
倒数第1天加入
倒数第2天加入
倒数第4天加入
倒数第6天加入
二进制中的1的个数,在数量上是恰好对应答案的。
而且也不能更优。
【时间复杂度&&优化】
O(log(1e9))
【trick】
【数据】
Input
5
Output
2
Input
8
Output
1
【代码】
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<ctype.h>
#include<math.h>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<functional>
#include<string>
#include<algorithm>
#include<time.h>
#include<bitset>
void fre(){freopen("c://test//input.in","r",stdin);freopen("c://test//output.out","w",stdout);}
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T> inline void gmax(T &a,T b){if(b>a)a=b;}
template <class T> inline void gmin(T &a,T b){if(b<a)a=b;}
using namespace std;
const int N=0,M=0,L=0,Z=1e9+7,maxint=2147483647,ms31=522133279,ms63=1061109567,ms127=2139062143;const double eps=1e-8,PI=acos(-1.0);//.0
map<int,int>mop;
struct A{};
int casenum,casei;
int n;
int main()
{while(~scanf("%d",&n)){int ans=0;while(n){ans+=n&1;n>>=1;}printf("%d\n",ans);}return 0;
}
这篇关于【Code Forces 320A】【二进制拆分】Raising Bacteria 细胞繁殖 每天倍增的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!