leetcode2081. k 镜像数字的和-hard

1 题目：k 镜像数字的和

官方标定难度：难

一个 k 镜像数字指的是一个在十进制和 k 进制下从前往后读和从后往前读都一样的没有前导 0 的正整数。

比方说，9 是一个 2 镜像数字。9 在十进制下为 9 ，二进制下为 1001 ，两者从前往后读和从后往前读都一样。
相反地，4 不是一个 2 镜像数字。4 在二进制下为 100 ，从前往后和从后往前读不相同。
给你进制 k 和一个数字 n ，请你返回 k 镜像数字中最小的 n 个数之和。

示例 1：

输入：k = 2, n = 5
输出：25
解释：
最小的 5 个 2 镜像数字和它们的二进制表示如下：
十进制二进制
1 1
3 11
5 101
7 111
9 1001
它们的和为 1 + 3 + 5 + 7 + 9 = 25 。

示例 2：

输入：k = 3, n = 7
输出：499
解释：
7 个最小的 3 镜像数字和它们的三进制表示如下：
十进制三进制
1 1
2 2
4 11
8 22
121 11111
151 12121
212 21212
它们的和为 1 + 2 + 4 + 8 + 121 + 151 + 212 = 499 。

示例 3：

输入：k = 7, n = 17
输出：20379000
解释：17 个最小的 7 镜像数字分别为：
1, 2, 3, 4, 5, 6, 8, 121, 171, 242, 292, 16561, 65656, 2137312, 4602064, 6597956, 6958596

提示：

2 <= k <= 9
1 <= n <= 30

2 solution

直接枚举，但是为了避免超时，需要优化一下，可以考虑枚举十进制的一半然后通过对称生成另一半，再去验证是否为k进制回文数。

代码

class Solution {
public:long long kMirror(int k, int n) {auto f = [&](long long m) {long long a = 0, q = m;while (m) {a = a * k + m % k;m /= k;}return a == q;};long long sum = 0;queue<long long> arr;for (int l = 1;; l++) {long long y = 0, z = l / 10, w = l;for (int x = l; x; x /= 10) {y = y * 10 + x % 10;z *= 10;w *= 10;}z += y;w += y;if (z && f(z)) {while(!arr.empty() && arr.front() < z){sum += arr.front();n--;if (n == 0) return sum;arr.pop();}sum += z;n--;if (n == 0) {return sum;}}if (f(w)) {arr.push(w);}}}
};