前言

考完蓝桥杯了以后一直在咕咕咕, 所以题解直到现在才写出来（）

欢迎访问我的个人博客！

第一题

题目描述

小蓝在黑板上连续写下从 1 到 2023 之间所有的整数，得到了一个数字序列：

S = 12345678910111213 . . . 20222023。

小蓝想知道 S 中有多少种子序列恰好等于 2023？

提示，以下是 3 种满足条件的子序列（用中括号标识出的数字是子序列包含的数字）：

1[2]34567891[0]111[2]1[3]14151617181920212223...
1[2]34567891[0]111[2]131415161718192021222[3]...
1[2]34567891[0]111213141516171819[2]021222[3]...

注意以下是不满足条件的子序列，虽然包含了 2、0、2、3 四个数字，但是顺序不对：

1[2]345678910111[2]131415161718192[0]21222[3]...

题目思路

这个题目问的是一个字符串的字串有多少个。首先我们要先开一个可以装下这一整个序列的数组。假设我们这个串的长度是 $S$。

由于这个串由 $1,2,...,2023$ 组成所以一共有 2023 个数字。每个数字最多占用 4 个字符，所以 $S<2023\ast 4<100000$。由此，我们只需要开 100000 即可将下整个字符串。

到了这一步，就已经可以写出来一个暴力算法了，不过我们在实际的运行中可以看到，这个时间复杂度太高了，我们没法承担，所以我们接下来应该开始优化这个代码。

我们来看这个字符串：

2025343

里面一共有两个子串：

[2][0][2]5[3]43
[2][0][2]534[3]

我们可以发现一个特点：这两个字符串的前缀是一样的，同时，子串的数量恰好等于以第二个 2 开始，到结尾中，3 的个数！

因此我们就有了以下的优化思路：我们可以开一个数组 cnt，这个数组记录以第 i 个字符开始，到结尾的 3 的个数。这样我们在深度优化遍历的时候，只需要遍历前 3 个字符，不需要遍历第 4 个字符。这样，时间复杂度就显著的降低了。

代码

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 1e5 + 10;string a;
// 第i个字符开始，往后3的个数
int cnt[N];
// 一定要开long long，会爆int。我当时考试的时候忘记开了，后悔死了。
long long res = 0;// 应该遍历的字符，当前应该查找的字符的编号
void dfs(int u, int t) {if (t == 4) {// 以u个字符为前缀，符合目标串的个数res += cnt[u];return ;}for (int i = u; i < a.size(); i ++) {if (t == 1) {if (a[i] == '2') {dfs(i + 1, t + 1);}} else if (t == 2) {if (a[i] == '0') {dfs(i + 1, t + 1);}} else if (t == 3) {if (a[i] == '2') {dfs(i + 1, t + 1);}}}
}int main () {// 我们以下标1为开始，所以先用0填一下a.push_back('0');for (int i = 1; i <= 2023; i ++) {// 构造子串a += to_string(i);}// 构造cnt数组 for (int i = a.size() - 1; i; i --) {if (a[i] == '3') {cnt[i] += 1;}cnt[i] += cnt[i + 1];}dfs(1, 1);cout << res << endl;return 0;
}

答案

5484660609

第二题

这题不确定，没有找到和我同一个答案的人。

题目描述

若一个正整数 $x$ 可以被表示为 $p^2\times q^2$，其中 $p$、$q$ 为质数且 $p$ , $q$，则 $x$ 是一个 “双子数”。请计算区间 $[2333,23333333333333]$ 内有多少个 “双子数”？

题目分析

这里要用到质数，那么我们首先需要求出所以的质数。这里使用线性筛法来求质数。那么应该开到多大呢？可以知道 $p$ 和 $q$ 是两个不相同的质数，那么可以假设 $p>q$，则 $p^2\ast q^2<p^4$。因此，我们只需要求到 $\sqrt[4]{23333333333333}$ 的下一个质数即可。

我们可以先用算法求出从 $2$ 开始到 $sqrt(23333333333333)$ 内所以的质数，然后输出其个数，可以得到：337413。然后，由于是填空题，所以两重 for 循环就可以求出所以的对数。同时，时间复杂度也在可以接受的范围内。

这里还有两个注意的点：1. p 和 q 不相等。2. p 和 q 的顺序无关，即 (2, 3)和 (3, 2)是同一对。

代码

#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>using namespace std;const int N = 1e7 + 10;typedef long long LL;LL primes[N];
bool st[N];
int cnt;double minv = 2333;
double maxv = 23333333333333;long long ans = 0;void get_primes(LL n) {for (int i = 2; i <= n; i++){if (!st[i]) primes[cnt++] = i;for (int j = 0; primes[j] <= n / i; j++){st[primes[j] * i] = true;if (i % primes[j] == 0) break;}}
}int main() {get_primes(sqrt(23333333333333));// pfor (int i = 0; (double)primes[i] <= maxv / primes[i] && i < cnt; i++) {// q^2的值double res = maxv / primes[i] / primes[i];// qfor (int j = 0; j < i; j++) {// 判断相乘要小于最大值if (double(primes[j]) <= res / primes[j]) {// 这样就可以确保在最大值的范围内，接下来要判断最小值。if ((double)primes[i] * primes[i] * primes[j] * primes[j] - minv > 1e-6) {// double类型的判断相等时，应该使用相减// a >= b  ===> a - b >= 0 == 1e-6ans++;}}else {break;}}}cout << ans << endl;return 0;
}

答案

947293