洛谷 P1582 倒水 (二进制)

xiaoxiao2021-03-01  1

这道题实际上是考二进制

很容易看出杯子水量一定是2的i次方

所以n杯水最后剩下的水一定是n用二进制表示中1的个数

所以就枚举n来求什么时候1的个数小于k

那么这里有个优化,不然会超时

因为每次加的目的是要让1的个数变少,也就是要进位 所以每次加上的是lowbit(n)

#include<cstdio> #define REP(i, a, b) for(int i = (a); i < (b); i++) #define _for(i, a, b) for(int i = (a); i <= (b); i++) using namespace std; int lowbit(int x) { return x & (-x); } int num(int x) { return !x ? 0 : 1 + num(x & (x - 1)); } int main() { int n, k, ans = 0; scanf("%d%d", &n, &k); while(num(n) > k) { ans += lowbit(n); n += lowbit(n); } printf("%d\n", ans); return 0; }

 

转载请注明原文地址: https://www.6miu.com/read-3850140.html

最新回复(0)