前言
考完蓝桥杯了以后一直在咕咕咕, 所以题解直到现在才写出来（）
欢迎访问我的个人博客！
第一题
题目描述
小蓝在黑板上连续写下从 1 到 2023 之间所有的整数，得到了一个数字序列：
1
| S = 12345678910111213 . . . 20222023。
|
小蓝想知道 S 中有多少种子序列恰好等于 2023？
提示，以下是 3 种满足条件的子序列（用中括号标识出的数字是子序列包含的数字）：
1
2
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
| 1[2]345678910111[2]131415161718192[0]21222[3]...
|
题目思路
这个题目问的是一个字符串的字串有多少个。首先我们要先开一个可以装下这一整个序列的数组。假设我们这个串的长度是 $S$。
由于这个串由 $1,2, … ,2023$ 组成所以一共有 2023 个数字。每个数字最多占用 4 个字符，所以 $S < 2023*4 < 100000$。由此，我们只需要开 100000 即可将下整个字符串。
到了这一步，就已经可以写出来一个暴力算法了，不过我们在实际的运行中可以看到，这个时间复杂度太高了，我们没法承担，所以我们接下来应该开始优化这个代码。
我们来看这个字符串：
里面一共有两个子串：
1
2
| [2][0][2]5[3]43
[2][0][2]534[3]
|
我们可以发现一个特点：这两个字符串的前缀是一样的，同时，子串的数量恰好等于以第二个 2 开始，到结尾中，3 的个数！
因此我们就有了以下的优化思路：我们可以开一个数组 cnt，这个数组记录以第 i 个字符开始，到结尾的 3 的个数。这样我们在深度优化遍历的时候，只需要遍历前 3 个字符，不需要遍历第 4 个字符。这样，时间复杂度就显著的降低了。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| #include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
string a;
int cnt[N];
long long res = 0;
void dfs(int u, int t) {
if (t == 4) {
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 () {
a.push_back('0');
for (int i = 1; i <= 2023; i ++) {
a += to_string(i);
}
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;
}
|
答案
第二题
这题不确定，没有找到和我同一个答案的人。
题目描述
若一个正整数 $x$ 可以被表示为 $p^{2} × q^{2}$，其中 $p$、$q$ 为质数且 $p$ , $q$，则 $x$ 是一个 “双子数”。请计算区间 $[2333, 23333333333333]$ 内有多少个 “双子数”？
题目分析
这里要用到质数，那么我们首先需要求出所以的质数。这里使用线性筛法来求质数。那么应该开到多大呢？可以知道 $p$ 和 $q$ 是两个不相同的质数，那么可以假设 $p > q$，则 $p^{2} * q^{2} < p^{4}$。因此，我们只需要求到 $\sqrt[4]{23333333333333}$ 的下一个质数即可。
我们可以先用算法求出从 $2$ 开始到 $sqrt(23333333333333)$ 内所以的质数，然后输出其个数，可以得到：337413。然后，由于是填空题，所以两重 for 循环就可以求出所以的对数。同时，时间复杂度也在可以接受的范围内。
这里还有两个注意的点：1. p 和 q 不相等。2. p 和 q 的顺序无关，即 (2, 3)和 (3, 2)是同一对。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| #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));
for (int i = 0; (double)primes[i] <= maxv / primes[i] && i < cnt; i++) {
double res = maxv / primes[i] / primes[i];
for (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) {
ans++;
}
}
else {
break;
}
}
}
cout << ans << endl;
return 0;
}
|
答案