csp-j/s模拟题详细题解

装水 题目详情

题目描述 一天小理买了N个容量可以认为是无限大的瓶子，开始时每个瓶子里有1升水。接着小理发现瓶子实在太多了，于是他决定保留不超过K个瓶子，每次他选择两个当前含水量相同的瓶子合并。（即把一个瓶子的水全部倒进另一个里然后把空瓶丢弃）

（注：不能丢弃有水的瓶子）

显然在某些情况下小理无法达到目标，比如N = 3, K = 1。此时小理会重新购买一些新的瓶子（新瓶子容量无限，开始时有1升水）以达到目标。

现在小理想知道最少需要多少新瓶子才能达到目标呢？

输入格式 一行两个正整数N和K，含义见题。

输出格式 输出文件包含一个非负整数，表示最少需要购买的瓶子数量。

1.4 测试样例 1.4.1 样例输入1(water.in) 3 1 1.4.2 样例输出1(water.out) 1 1.4.3 样例输入2(water.in) 13 2 2 CSP-J 模拟题 执理OI 1.4.4 样例输出2(water.out) 3 1.4.5 样例输入3(water.in) 1000000 5 1.4.6 样例输出3(water.out) 15808 1.5 任务约束 对于50%的数据，保证1 ⩽ n ⩽ 10^7 对于100%的数据，保证1 ⩽ n ⩽ 10^9, 0 ⩽ k ⩽ 1000

AC代码

这道题只需要将瓶子数转化为2进制看看里面包含多少个1即可,例如13的二进制是1101,16的二进制是10000,只有一个1,小于输入的2,所以最终答案就是16-13,所以这道题的难点就在于如何不超时传化二进制

代码1(90分)

可以用到__builtin_popcount(n)来做到快速计算二进制的1的个数 代码如下

#include
#include
#include
#include
using namespace std;
int main(){
	//freopen("water.in","r",stdin);
	//freopen("water.out","w",stdout);
	int n,k;
	cin >> n >> k;
	int ans = 0;
	while(__builtin_popcount(n) > k){
		ans++;
		n++;
	}
	cout  k;
	int ans = 0;
	while(count(n) > k){
		ans++;
		n++;
	}
	cout  k;
	int ans = 0;
	while(count(n) > k){
		ans+=lowbit(n);//直接寻找二进制最后一个1的位置,这样做不会超时
		n+=lowbit(n);
	}
	cout