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);}}}
};

結果