Codeforces Round 878 (Div. 3) - B. Binary Cafe

Solost

2023 年 07 月 06 日

132 次浏览

暂无评论

401字数

题目题解

## 题目链接

[链接](https://codeforces.com/contest/1840/problem/B)

## 题目大意

有 **k** 种商品，编号为 **0** 至 **k**−**1**，编号为 **i** 的商品的价格为2^i，问你在花的钱数不超过 **n** 且每种商品最多买一个（可以不买所有商品）的前提下，有多少种购买商品的方式。

某个商品只有两种情况，买还是不买，这就像二进制，从右往左，第i个位0代表不买，否则买，问K位以内，能有多少个二进制转换为10进制小于等于n。如果有k位，那么可以表示[0, 2^k - 1]的数字都可以表示出来，因为2进制表示是唯一的，例如8 = 2^3,再没有其他的表示办法， 所以不能被其他替代，所以，[0, 2^k - 1]的数字都有唯一的二进制表示方法，如果n <= 2^k -1,那么最多表示[0, n]一共n+1个数字，如果小于的话可以表示[0, 2^k - 1]范围内的数，一共2^k个。又因为1<<30就会爆int,超过1e9，特判即可

```cpp
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

#define x first
#define y second
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;

void solve()
{
    int n, k;
    cin >> n >> k;
    if(k >= 30 || n <= pow(2, k) - 1){
        cout << (n + 1) << endl;
    }
    else{
        cout << (1 << k) << endl;
    }
}
int main()
{
    IOS;
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
```

最后修改：2023 年 07 月 06 日