补题 [CF1840B] Binary Cafe

题目描述

从前，Toma 来到了一家二进制咖啡厅，这是一个非常受欢迎且不同寻常的地方。

咖啡厅提供了$ k$ 种不同的美味甜点，这些甜点从 $0$ 到 $k−1$ 进行编号。第 $i$ 个甜点的成本为 $i^2$ 枚硬币，因为这是一家二进制咖啡厅！Toma 愿意花费不超过 $n$ 枚硬币来品尝甜点。同时，他对于购买任何一种甜点超过一次都不感兴趣，因为品尝一次足以评价口感。

他有多少种不同的方式可以购买多种（可能为零）甜点来品尝？

输入格式

输入的第一行包含一个整数 $t$ $(1≤t≤1000)$——测试用例的数量。

接下来是 $t$ 行，每行描述一个测试用例。

每个测试用例都在单独的一行上给出，由两个整数 $n$ 和 $ k$ $(1≤n,k≤10^9)$ 组成——Toma愿意花费的硬币数量以及二进制咖啡馆中的甜点数。

输出格式

输出 $t$ 个整数，其中第 $i$ 个整数应该等于第 $i$ 个测试用例的答案——购买甜点品尝的方法数。

样例 #1

样例输入 #1

1
2
3
4
5
6
5
1 2
2 1
2 2
10 2
179 100

样例输出 #1

1
2
3
4
5
2
2
3
4
180

提示

第一个样例的变体：{}，{1}

第二个样例的变体：{}，{1}

第三个样例的变体：{}，{1}，{2}

第四个样例的变体：{}，{1}，{2}，{1,2}

题解

题目解析

这道题紧紧的与二进制与十进制相联系,其实这道题也是非常简单的脑筋急转弯.我们很容易考虑到,当 $k>30\quad(2^{30}=1,073,741,824)$ 的时候,也就是 $2^k>10^9$ 时那么无论怎么组合是买不完蛋糕的.

再仔细考虑,二进制与十进制的关系: 每个购买钱数的二进制与它的十进制数是形成同构映射的

1
2
3
4
5
n=3,k>30:
当我花3元钱的时候一一对应:11
当我花2元钱的时候一一对应:10
当我花1元钱的时候一一对应:01
当我花0元钱的时候一一对应:00

所以,只要 $k>30$ 那么购买的种类数即 $n+1$.那么如果 $k<30$ ,我们就要取 $\min(2^k,n+1)$ 了.因为如果 $n$ 不限制 $k$ ,那么我们就通过简单组合数学知识可得有 $2^k$ 种可能,如果 $k$ 被 $n$ 限制,那么我们就要取 $n+1$ 了.

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

#define endl "\n"
#define MAXN(size) const long long MAXN = size + 100
#define var(size) int p[size]{}
#define mem(name,value) memset(name,value,sizeof(name))
#define fa(a,n,p) for(int i=a;i<=n;i+=p)
#define fb(a,n,p) for(int i=a;i>=n;i-=p)
#define cin(length,var) for(int i=1;i<=length;i++) cin >> var[i]
typedef long long ll;


signed main(){
	int T;
	cin >> T;
	while(T--){
		int n,k;
		cin >> n >> k;
		if(k > 30){
			cout << n+1 << endl;
		}else{
			cout << min(n+1,1<<k) << endl;
		}
	}
	return 0;
}