T1：果果趣
首先观察每 \(15\) 个连续正整数组成序列中不包含特殊词汇对应的原始数字有 \(8\) 个：1、2、4、7、8、11、13、14。所以可以将 \(n\) 除以 \(8\) 取商 \(d\) 和余 \(r\)，然后根据 \(d\) 和 \(r\) 计算结果。
如果 \(r \neq 0\)，则结果为 \(d \times 15\) 加上数组 \(a[r]\) 中对应元素
如果 \(r = 0\)，则结果为 \(d \times 15-1\)。
这样就可以在 \(O(1)\) 时间内找出第 \(n\) 个非特殊词汇对应的原始数字。
代码实现
#include <bits/stdc++.h>
using namespace std;
int a[] = {14, 1, 2, 4, 7, 8, 11, 13};
int main() {
int n;
cin >> n;
int d = n/8, r = n%8;
int ans = d*15;
if (r != 0) ans += a[r];
else ans--;
cout << ans << '\n';
return 0;
}
T2：阿兹特克
求前 \(k\) 小的在 \(10\) 进制和 \(p\) 进制下都是回文的数之和。
参考难度：黄题
分析
70分做法：
从小到大枚举数，然后分别按照十进制和 \(p\) 进制做数位拆分。对拆分之后得到的两个数组，分别判断是否为回文。
然而，这一做法需要从小到大枚举数字，对于本题而言，最坏情况为 \(k = 30\)， \(p = 7\) 时，第 \(30\) 个满足条件的数为 \(64454545446\)，从 \(1\) 开始枚举显然超时，期望得分 \(70\) 分。
100分做法：
实际上，除了个位数的回文数，其他回文数都可以通过翻转得到，即，先确定左半部分的数位，右半部分的数位通过翻转得到。
这一做法只需枚举左半部分的数位，对于上文提到的最坏情况，仅需枚举到 \(64454\)。但是我们需要确保所有满足条件的数是从小到大枚举到的，所以我们可以按照如下方式枚举：
- 先枚举 \(1 \sim 9\) 中的数，相当于 \(10\) 进制下的个位回文数，判断是否为 \(p\) 进制回文数
- 从小到大循环枚举左半部分的位数
bit- 先枚举偶数位的回文数，，其为
2bit位 - 再枚举奇数位的回文数，其为
2bit+1位
- 先枚举偶数位的回文数，，其为
这个方法枚举的数字最多 \(10^5\) 个，期望得分 \(100\) 分。