CSP-S 2024 提高级 第一轮（初赛） 阅读程序（3）

【题目】

CSP-S 2024 提高级 第一轮（初赛） 阅读程序（3）

1 #include <iostream>
2 #include <cstring>
3 #include <algorithm>
4 using namespace std;
5
6 const int maxn = 1000000 + 5;
7 const int P1 = 998244353, P2 = 1000000007;
8 const int B1 = 2, B2 = 31;
9 const int K1 = 0, K2 = 13;
10
11 typedef long long ll;
12
13 int n;
14 bool p[maxn];
15 int p1[maxn], p2[maxn];
16
17 struct H {
18     int h1, h2, l;
19     H(bool b = false) {
20         h1 = b + K1;
21         h2 = b + K2;
22         l = 1;
23     }
24     H operator + (const H &h) const {
25         H hh;
26         hh.l = l + h.l;
27         hh.h1 = (1ll * h1 * p1[h.l] + h.h1) % P1;
28         hh.h2 = (1ll * h2 * p2[h.l] + h.h2) % P2;
29         return hh;
30     }
31     bool operator == (const H &h)const {
32         return l == h.l && h1 == h.h1 && h2 == h.h2;
33     }
34     bool operator < (const H &h)const {
35         if (l != h.l)return l < h.l;
36         else if (h1 != h.h1)return h1 < h.h1;
37         else return h2 < h.h2;
38     }
39 } h[maxn];
40
41 void init() {
42     memset(p, 1, sizeof(p));
43     p[0] = p[1] = false;
44     p1[0] = p2[0] = 1;
45     for (int i = 1; i <= n; i++) {
46         p1[i] = (1ll * B1 * p1[i - 1]) % P1;
47         p2[i] = (1ll * B2 * p2[i - 1]) % P2;
48         if (!p[i])continue;
49         for (int j = 2 * i; j <= n; j += i) {
50             p[j] = false;
51         }
52     }
53 }
54
55 int solve() {
56     for (int i = n; i; i--) {
57         h[i] = H(p[i]);
58         if (2 * i + 1 <= n) {
59             h[i] = h[2 * i] + h[i] + h[2 * i + 1];
60         } else if (2 * i <= n) {
61             h[i] = h[2 * i] + h[i];
62         }
63     }
64     cout << h[1].h1 << endl;
65     sort(h + 1, h + n + 1);
66     int m = unique(h + 1, h + n + 1) - (h + 1);
67     return m;
68 }
69
70 int main() {
71     cin >> n;
72     init();
73     cout << solve() << endl;
74 }

判断题
1. 假设程序运行前能自动将 maxn改为 n+1，所实现的算法的时间复杂度是 O(nlogn)。
2. 时间开销的瓶颈是 init()函数
3. 若修改常数 B1 或 K1 的值，该程序可能会输出不同的结果
单选题
4. 在 solve()函数中，h[]的合并顺序可以看作是：（ ）
A. 二叉树的 BFS 序
B. 二叉树的先序遍历
C. 二叉树的中序遍历
D. 二叉树的后序遍历
5. 输入“10”，输出的第一行是？（ ）
A.83
B.424
C.54
D.110101000
6. (4 分)输入“16”，输出的第二行是？（ ）
A.7
B.9
C.10
D.12

【题目考点】

1. 字符串哈希

设一个串为$s=c_0{c}_1...c_{n-1}$，设基数为B，该串的哈希值为：
$H(s)=c_0{B}^{n-1}+c_1{B}^{n-2}+...+c_{n-1}{B}^0$

2. 二叉树：顺序存储结构

使用数组保存完全二叉树，下标i位置表示的结点的左孩子在$2i$位置，右孩子在$2i+1$位置，双亲在$\lfloor \frac{i}{2}\rfloor$位置

3. 埃拉托色尼筛法

4. C++ STL

1. sort函数
   sort(lb, ub, cmp)
   lb为序列的下界，ub为序列的上界，下界与上界的类型为指针或迭代器，表示左闭右开区间[lb, ub)。
   cmp为比较规则，可以传入函数，指定元素的排序规则。如不传cmp参数，则默认的比较函数为less仿函数，其实现大体为：

<template class T>
struct less
{bool operator () (const T &a, const T &b){return a < b;}
}

其意义为：如果a<b为真，那么a应该排在b的前面。
因此只要该T类型元素重载了小于号运算符，即可使用less仿函数，也就是可以直接使用sort进行排序且不需要传入比较函数。
2. unique函数
rb = unique(lb, ub)
lb为序列的下界，ub为序列的上界，下界与上界的类型为指针或迭代器，表示左闭右开区间[lb, ub)。
unique的作用是将序列的左闭右开区间[lb, ub)中的相邻的重复元素只保留一个。如果[lb, ub)区间中的元素是有序的，那么该函数可以完成去重。
函数返回值为rb，表示去重后剩下的元素在区间[lb, rb)中，去重后剩下元素的个数为rb-lb。

【解题思路】

41 void init() {
42     memset(p, 1, sizeof(p));
43     p[0] = p[1] = false;
44     p1[0] = p2[0] = 1;
45     for (int i = 1; i <= n; i++) {
46         p1[i] = (1ll * B1 * p1[i - 1]) % P1;
47         p2[i] = (1ll * B2 * p2[i - 1]) % P2;
48         if (!p[i])continue;
49         for (int j = 2 * i; j <= n; j += i) {
50             p[j] = false;
51         }
52     }
53 }

看init函数，如果只看p数组相关操作，可以看出这是在进行埃筛，结果是p数组，p[i]表示数值i是否是质数。
对于p1、p2，是预处理幂，根据递推式可知：
p1[i]表示$B_1^i\%P_1$，p2[i]表示$B_2^i\%P_2$

17 struct H {
18     int h1, h2, l;
19     H(bool b = false) {
20         h1 = b + K1;
21         h2 = b + K2;
22         l = 1;
23     }
24     H operator + (const H &h) const {
25         H hh;
26         hh.l = l + h.l;
27         hh.h1 = (1ll * h1 * p1[h.l] + h.h1) % P1;
28         hh.h2 = (1ll * h2 * p2[h.l] + h.h2) % P2;
29         return hh;
30     }
31     bool operator == (const H &h)const {
32         return l == h.l && h1 == h.h1 && h2 == h.h2;
33     }
34     bool operator < (const H &h)const {
35         if (l != h.l)return l < h.l;
36         else if (h1 != h.h1)return h1 < h.h1;
37         else return h2 < h.h2;
38     }
39 } h[maxn];

看H类，大体上是用到了双哈希的算法。H表示一个串，l是这个串的长度，h1、h2是该串在不同基数下的哈希值。

19     H(bool b = false) {
20         h1 = b + K1;
21         h2 = b + K2;
22         l = 1;
23     }

设一个串为$s=c_0{c}_1...c_{n-1}$，设基数为B，该串的哈希值为：
$H(s)=(c_0{B}^{n-1}+c_1{B}^{n-2}+...+c_{n-1}{B}^0)\mathrm{mod}P$（为方便表示，以下叙述中省略$\mathrm{mod}P$）
根据构造函数可以看出，该问题的串是由bool类型组成的，也可以视为一个01串。
构造函数中，l为1，串中只有一个元素。
当b为true，也就是串s="1"时，哈希值$h_1=1+K_1=1$，$h_2=1+K_2=14$
当b为false，也就是串s="0"时，哈希值$h_1=K_1=0$，$h_2=K_2=13$
当串长度l为1时，$H(s)=c_0{B}^{1-1}=c_0$，该哈希值就是这一位0或1所代表的值$c_i$
因此在基数为$B1=2$时，01串中每位0对应的值$c_i$为0，每位1对应的值$c_i$为1。
在基数为$B2=31$时，01串中每位0对应的值$c_i$为13，每位1对应的值$c_i$为14。

24     H operator + (const H &h) const {
25         H hh;
26         hh.l = l + h.l;
27         hh.h1 = (1ll * h1 * p1[h.l] + h.h1) % P1;
28         hh.h2 = (1ll * h2 * p2[h.l] + h.h2) % P2;
29         return hh;
30     }

重载+运算符，其作用是将两个串连接为一个新串，返回新串的长度及哈希值。
设x、y都是H类型的对象，存在表达式z = x+y。
那么在该成员函数中，x对象是*this，x的属性是h1, h2, l，在以下解释中记为$x{h}_{1}x{h}_{2}xl$。
y是传入的参数h，属性为h.h1, h.h2, h.l，在以下解释中记为$y{h}_{1}y{h}_{2}yl$。
结果z为hh，其属性为$z{h}_{1}z{h}_{2}zl$。
设x表示的串为$c_0{c}_1...c_{xl-1}$，y表示的串为$c_0^{\prime }{c}_1^{\prime }...c_{yl-1}^{\prime }$
z表示的串为$c_0{c}_1...c_{xl-1}{c}_0^{\prime }{c}_1^{\prime }...c_{yl-1}^{\prime }$
首先二者连接后的串z的长度为x、y两个串的长度加和$zl=xl+yl$。
而后求串z在基数为B1时的哈希值。
$x{h}_1=c_0{B}_1^{xl-1}+c_1{B}_1^{xl-2}+...+c_{xl-1}{B}_1^0$
$y{h}_1=c_0^{\prime }{B}_1^{yl-1}+c_1^{\prime }{B}_1^{yl-2}+...+c_{yl-1}^{\prime }{B}_1^0$

$z{h}_1=c_0{B}_1^{xl+yl-1}+c_1{B}_1^{xl+yl-2}+...+c_{xl-1}{B}_1^{yl}+c_0^{\prime }{B}_1^{yl-1}+c_1^{\prime }{B}_1^{yl-2}+...+c_{yl-1}^{\prime }{B}_1^0$
$=B_1^{xl}(c_0{B}_1^{xl-1}+c_1{B}_1^{xl-2}+...+c_{xl-1}{B}_1^0)+(c_0^{\prime }{B}_1^{yl-1}+c_1^{\prime }{B}_1^{yl-2}+...+c_{yl-1}^{\prime }{B}_1^0)$
$=B_1^{xl}x{h}_1+y{h}_1$
这就是代码hh.h1 = (1ll * h1 * p1[h.l] + h.h1) % P1的原理，其中p1[h.l]就是$B_1^{xl}$。
同理有：$z{h}_2=B_2^{xl}x{h}_2+y{h}_2$

31     bool operator == (const H &h)const {
32         return l == h.l && h1 == h.h1 && h2 == h.h2;
33     }
34     bool operator < (const H &h)const {
35         if (l != h.l)return l < h.l;
36         else if (h1 != h.h1)return h1 < h.h1;
37         else return h2 < h.h2;
38     }

重载==运算符，判断规则为：两个H类对象表示的串的长度以及两种哈希值都对应相等时，认定两个H类对象相等。注意，如果两个元素表示的01串不同，但它们的两种哈希值都分别相同，即发生哈希冲突，此时也认为二者相等。
重载<运算符，先比较串的长度，再比哈希值h1，再比哈希值h2。如果某一项不相等，直接返回比较结果。

55 int solve() {
56     for (int i = n; i; i--) {
57         h[i] = H(p[i]);
58         if (2 * i + 1 <= n) {
59             h[i] = h[2 * i] + h[i] + h[2 * i + 1];
60         } else if (2 * i <= n) {
61             h[i] = h[2 * i] + h[i];
62         }
63     }
64     cout << h[1].h1 << endl;
65     sort(h + 1, h + n + 1);
66     int m = unique(h + 1, h + n + 1) - (h + 1);
67     return m;
68 }

solve函数中，i从n到1循环，将h[i]的哈希值设为H(p[i])，可以理解为生成一个长为1的串，如果p[i]为true，串就是"1"；如果p[i]为false，串就是"0"。h[i]中保存的就是该串的长度，以及在两种基数下的哈希值。
将h数组视为顺序存储结构的二叉树，h[i]的左孩子是h[2*i]，右孩子是h[2*i+1]，如果第i位置表示的结点存在孩子，其孩子的下标不能超过n。
因此判断if(2*i+1 <= n)就是判断“如果i有右孩子”，h[i] = h[2 * i] + h[i] + h[2 * i + 1]就是将第i结点左孩子h[2*i]表示的串接上h[i]表示的串再接上h[2*i+1]表示的串，将拼接起来的新的字符串的长度以及两种哈希值保存在h[i]。
else if (2*i <= n)就是判断如果i没有右孩子，只有左孩子，那么h[i] = h[2 * i] + h[i]将第i结点的左孩子h[2*i]表示的串和h[i]表示的串前后连接作为新的串。新的串的长度和哈希值保存在h[i]。
最后输出根结点h[1]基数为B1时的哈希值
将h[1]~h[n]按照重载<指定的比较规则进行升序排序。
而后将h[1]~h[n]去重，调用unique函数进行去重时，函数内部使用了H类的==运算符，来判断两个H类对象是否相等。unique的返回值减去上界h+1即为去重后的元素个数，返回该值。（见【题目考点】4）
主函数中就是调用solve，输出其返回值。

【试题答案及解析】

判断题
1. 假设程序运行前能自动将 maxn改为 n+1，所实现的算法的时间复杂度是 O(nlogn)。
答：T
如果使用动态内存申请的方法，就可以使数组长度始终为n+1。

55 int solve() {
56     for (int i = n; i; i--) {
57         h[i] = H(p[i]);
58         if (2 * i + 1 <= n) {
59             h[i] = h[2 * i] + h[i] + h[2 * i + 1];
60         } else if (2 * i <= n) {
61             h[i] = h[2 * i] + h[i];
62         }
63     }
64     cout << h[1].h1 << endl;
65     sort(h + 1, h + n + 1);
66     int m = unique(h + 1, h + n + 1) - (h + 1);
67     return m;
68 }

观察solve函数，i从n循环到1，循环内无论是H类对象的构造函数，还是H类对象的+运算，都是O(1)复杂度。因此该循环的复杂度是$O(n)$
unique的复杂度是$O(n)$，sort函数的复杂度是$O(nlogn)$，因此solve函数的时间复杂度为$O(nlogn)$
init函数就是埃筛的过程，复杂度是$O(nloglogn)$
因此该算法整体的时间复杂度是$O(nlogn+nloglogn)=O(nlogn)$，该叙述正确。
2. 时间开销的瓶颈是 init()函数
答：F
根据第1题的分析，可知solve函数的复杂度比init函数更高，因此时间开销的瓶颈是solve函数，更准确地说是sort函数。
3. 若修改常数 B1 或 K1 的值，该程序可能会输出不同的结果
答：T
根结点的01串是固定的，但B1及K1决定了该串的h1哈希值。该题最后要输出根结点表示的串的h1哈希值，因此改变B1或K1的值后，可能会使结果不同。

单选题
4. 在 solve()函数中，h[]的合并顺序可以看作是：（ ）
A. 二叉树的 BFS 序
B. 二叉树的先序遍历
C. 二叉树的中序遍历
D. 二叉树的后序遍历
答：C
如果i有右孩子，执行h[i] = h[2 * i] + h[i] + h[2 * i + 1]是左孩子表示的串 连接 根结点表示的串 连接右孩子表示的串。
如果i没有右孩子，只有左孩子，执行h[i] = h[2 * i] + h[i]是左孩子表示的串 连接 根结点表示的串。
都满足左、根、右的顺序，这是二叉树的中序遍历顺序。

5. 输入“10”，输出的第一行是？（ ）
A.83
B.424
C.54
D.110101000
答：A
n=10，只考虑i从1~10这10个数字是否为质数。

i	1	2	3	4	5	6	7	8	9	10
p[i]	0	1	1	0	1	0	1	0	0	0

根据该题的规则建树
结点中x:s 表示x号结点表示的串为s

根结点的串为0001010011，串中元素为0时$c_i=K_1=0$，串中元素为1时$c_i=K_1+1=1$。
哈希值计算公式为$H(s)=(c_0{B}^{n-1}+c_1{B}^{n-2}+...+c_{n-1}{B}^0)\mathrm{mod}P$
n为串s的长度，该题中为10。B为$B_1=2$，P为$P_1=998244353$
$H(s)=0\ast 2^9+0\ast 2^8+0\ast 2^7+1\ast 2^6+0\ast 2^5+1\ast 2^4+0\ast 2^3+0\ast 2^2+1\ast 2^1+1\ast 2^0=2^6+2^4+2^1+2^0=83$，选A。
6. (4 分)输入“16”，输出的第二行是？（ ）
A.7
B.9
C.10
D.12
答：C
根据要求建树

基数为B1和基数为B2的哈希过程对于0、1对应的值$c_i$的认定是不同的，两个基数也不同，不同串经过两种哈希过程得到相同哈希值都相等的概率很小，我们可以认为不会出现哈希冲突。在这样的认识下，只要两个串不同，二者的哈希值就是不同的。那么经过去重操作后得到的结果m是：h[1]~h[16]中也就是树中所有结点所表示的不同的串的数量。
有：
0, 1, 00, 001, 010, 011, 0000, 00001011, 0011010, 0000101100011010。共10种串，选C。