P2022 有趣的数
传送门
题目描述
让我们来考虑1到N的正整数集合。让我们把集合中的元素按照字典序排列，例如当N=11时，其顺序应该为：1,10,11,2,3,4,5,6,7,8,9。
定义K在N个数中的位置为Q(N,K)，例如Q(11,2)=4。现在给出整数K和M，要求找到最小的N，使得Q(N,K)=M。
输入格式
输入文件只有一行，是两个整数K和M。
输出格式
输出文件只有一行，是最小的N，如果不存在这样的N就输出0。
输入输出样例
输入 #1
2 4
输出 #1
11
输入 #2
100000001 1000000000
输出 #2
100000000888888879
说明/提示
数据约定
(40\%)的数据，(1<=K),(M<=10^5)；
(100\%)的数据，(1<=K),(M<=10^9)。
题解
参照此篇题解
(m) 的意义
由于 (m) 是 (k) 的位次, 所以有 (m - 1) 个数排在其之前.
显然这个题主要讨论的就是有多少个数在 (k) 之前, 所以首先将 (m) 变成 (m - 1), 将问题转化.
答案的单调性
对于一个数 (k), 则对于所有 (n ge k), (Q(n, k)) 随 (n) 的增加而增加 (严格地说是不下降), 所以, 这个题的答案是可以二分的 (很显然不能二分, 因为答案区间很大, 二分的复杂度约为 (O(N(log_2N)^2)), 约 (10 ^ 9 * 31^2 approx 10 ^ {12}), 详见这篇题解)
另辟蹊径
既然不能二分, 寻找此题其他性质, 有 (n - 1) 个数排在 (k) 前面, 且相同位数的数字是连续出现的. 即排序后, 位数不同的数会排成几个个公差为 (1) 的数列, 如 (Q(11, 9) = 11的排列)
将 (9) 前面的数字排序后:
可以看到从 (1) 到, (8), 从 (10) 到 (11) 是连续的.
所以可以尝试按位数来枚举排在 (k) 前面的数.
(Min) 的意义
由最开始 (Q(n, k)) 随 (n) 单调递增可得, 对于每一个 (k), 一定存在
用 (Min) 存 (Q(k, k) - 1), 可以判断是否有解, 并且作为求解的第一步.
如何求值, 还是根据本题相同位数连续出现的性质, 按位求.
设 (k) 有 (len) 位.
对于比 (k) 位数少的数, 如果其位数为 (i (i leq len)), 则设 (k) 的前 (i) 位组成的 (i) 位数为 (k_i), 所有 (i) 位数中, 小于等于 (k_i) 的数排在 (k) 前面, 大于 (k_i) 的数排在 (k) 后面.
对于和 (k) 相同位数的数, 比 (k) 小的数都在 (k) 前面, 比 (k) 大的数都在 (k) 后面.
但是对于 (k) 本身也计算进去了, 所以需要再减去 (1).
得到 (Min) 的表达式
其中 (k_i = frac{k}{10^{len - i}})
所以
判断答案存在性
由于(k) 前面的最少有 (Min) 个数, 所以
(k < Min), 则答案不存在;
(k = Min), 则答案就是k;
(k > Min), 则继续枚举更高位数的数.
求出答案
这时, 已经求出 (Min) 且 (Min > m), 从 (len + 1) 位数开始枚举.
其实和位数小于 (len) 的数相似, 但是不同的是, (k_i) 此时排在 (k) 之后, 可以很简单地写出上面表达式中 (i > len) 的情况.
(i) 位数中排在 (k) 前面的数的个数
所以只要枚举位数 (i), 求出 (n) 的位数 (len_n)
(由于最高位数的数大概率取不完, 所以这里先算能取完的位数 (len_n - 1), 之后再算缺少的数)
这时的 (n) 是 (k * 10^{len_n - len - 1}) 也就是 (k) 后面补 '(0)', 直到位数达到 (len_n - 1).
设上式所求的 (k) 前面的数字有 (Q') 个, 距离要求的 (m) 个还差 (m - Q') 个.
还差的这些数无疑位数是 (len_n), 而且一定是从 (10^{len_n - 1}) 开始, 到 (10^{len_n - 1} + m - Q' - 1) 结束, 所以最后的答案是
代码
#include <cstdio>
#include <iostream>
using namespace std;
long long m, k, Ten[20], len(0), Min(0);
void getlen(long long x) { //将 len 赋值为 x 的位数
while (x) {
++len;
x /= 10;
}
return;
}
void getmin(long long x) { //将 Min 赋值为 Q(x, x) - 1
for (register int i(1); i <= len; ++i) {
Min += k / Ten[len - i] - Ten[i - 1] + 1;
}
Min--; //去掉 k 本身
return;
}
int main() {
Ten[0] = 1;
for (int i = 1; i < 19; ++i) { //预处理10^i
Ten[i] = Ten[i - 1] * 10;
}
scanf("%lld%lld", &k, &m);
m--;
getlen(k); //求 len
getmin(k); //求 Min
if (Min > m) {
printf("0
");
return 0;
}
if (Min == m) {
printf("%d
", k);
return 0;
}
register int lenn(len + 1); //因为要枚举 lenn, 所以 lenn 充当循环控制变量
while (Min < m) { //这时的 Min 代表当前枚举到的排在 k 前面的数的个数
if (lenn >= 20) { //防止答案过大
printf("0
");
return 0;
}
Min += k * Ten[lenn - len] - Ten[lenn - 1];
++lenn;
}
--lenn; // lenn 从 lenn + 1 变回 lenn
Min -=
k * Ten[lenn - len] - Ten[lenn - 1]; // Min 回到 lenn = lenn - 1 时的情况
printf("%lld
", Ten[lenn - 1] + m - Min - 1);
// system("pause"); // VSC用户常常忘记删除的一行
return 0;
}