Problem
题目简述
给你一个 \(K\),求出 \([1 \sim K]\) 区间内有多少个 321-like Number。
321-like Number 的定义:
- 每一位上的数字从左到右严格单调递减。
- 或者说,若它有 \(d\) 位,对于 \(\forall i\in[1,d-1]\),从左到右第 \(i\) 位上的数大于从左到右第 \(i+1\) 位上的数。
思路
预处理出所有的 321-like Number,枚举的时候类似枚举集合的做法。
存到 vector 数组里,排序后输出第 \(K\) 大的。
【注意】 本题需要开 \(\text{long long}\)。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll; // 开long long
ll k;
int main() {
scanf("%lld", &k);
k--;
vector<ll> v; // vector 存放枚举的结果
for (int i = 2; i < (1 << 10); i++) {
ll t = 0;
for (int j = 9; j >= 0; j--) {
if ((i >> j) & 1) { // 这一位为不为0
t *= 10, t += j; // 加到结果里
}
}
v.push_back(t);
}
sort(v.begin(), v.end()); // 排序
printf("%lld", v[k]); // 输出结果
return 0;
}