CF1840B Binary Cafe 题解

· · 题解

先来解释一下题意：

一个咖啡馆里有 k 种甜点，甜点的编号从 0 到 k-1，第 i 种甜点的价格为 2^{i}，问你在花费不超过 n 的情况下有多少种购买甜点的方式（注意每种甜点最多买一次）。

然后我们进行分析：

我们可以发现，每种买甜点的方式都可以用一个 k 位的二进制数来表示。从右往左编号从 0 到 k-1，对于第 i 位如果是 1 就代表买第 i 种甜点，如果是 0 就代表不买这种甜点，而每种方式所对应的二进制数的十进制值就正好代表了这种方式所花费的价格。

这样原问题就变成了寻找长度为 k 且数值不超过 n 的二进制数的数量。简单分析一下可知，一个长度为 k 位的二进制数的数值能取到的区间为 [0,2^{k}-1]，那么当 n \leq 2^{k}-1 时，从 0 到 n 都是可以表示出来的，答案为 n+1。不然的话最多就只能取最大的区间 [0,2^{k}-1] 一共 2^{k} 个值了。

以下是代码：

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int t,n,k;
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&k);
        if(n<=pow(2,k)-1) printf("%d\n",n+1);
        else{
            int x=pow(2,k);
            printf("%d\n",x);
        }
    }
    return 0;
}

后记

如果对题解的内容有建议或者指正，请在在评论区里说或者私信我.