#2709. CSP-S 2022 第一轮（初赛）模拟

CSP-S 2022 第一轮（初赛）模拟

一、单项选择题（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）

1.(1047)8(1047)_8=（ ）。 {{ select(1) }}

  • (1011011101)2(1011011101)_2
  • (11010)5(11010)_5
  • (20213)4(20213)_4
  • (308)16(308)_{16}
  1. 若逻辑变量 A、C 为真，B、D 为假，以下逻辑表达式的值为假的是（ ） 。 {{ select(2) }}
  • (B∨C∨D)∨D∧A
  • ((﹁A∧B)∨C)∧﹁B
  • (A∧B)∨﹁(C∧D∨﹁A)
  • A∧(D∨﹁C)∧B
  1. 小恺编写了如下函数，希望计算斐波那契数列 f(n)第 n 项对 10000 取余数的值：
int f(int x) {
if(x <= 2)
  return 1;
int ans = f(x - 1) + f(x - 2);
ans %= 10000;
return ans;
}

在运行空间限制 128MB、栈空间不超过空间限制、运行时限 1 秒的情况下，在主函数中运行函数 f(12345)，则最有可能首先发生什么问题？ {{ select(3) }}

  • 运行时间超时
  • 栈溢出
  • 访问无效内存
  • 返回错误的答案
  1. 表达式 a+b*(c-d)/e-f 的后缀表达式为（ ）。

{{ select(4) }}

  • -+a/*b-c-cdef
  • abcd-*e/+f-
  • +ab*-cd/e-f
  • f-e/d-d*b+a

5.某个 MV 是一段时长 4 分整的视频文件。它每秒播放 10 帧图像，每帧图像是一幅分辨率为 2048×1152 像素（长宽比 16:9）的 32 位真彩色图像，其画面没有被压缩。其音频的比特率是 128kbps。这个视频文件大约需要占用多大的存储空间？（ ）。

{{ select(5) }}

  • 21 GiB
  • 27 GiB
  • 168 GiB
  • 2 GiB
  1. 下图是一棵二叉树，它的后序遍历是 （ ）。

{{ select(6) }}

  • ABDEFC
  • DBEFAC
  • DFEBCA
  • ABCDEF
  1. 五个本质不同的点在没有重边或者自环的情况下，组成不同的无向图的个数是 （ ）？ {{ select(7) }}
  • 10
  • 1024
  • 15
  • 120
  1. 设元素 a,b,c,d,e,f 依次入栈，则下列不合法的出栈序列为（ ）? {{ select(8) }}
  • d,c,b,e,f,a
  • f,e,d,c,b,a
  • c,d,f,e,b,a
  • e,d,b,a,f,c
  1. 同时扔出 𝑘 枚完全相同的六面骰子，每个骰子上有 1 到 6 的数字。将得到的点数排序后，有（ ）种不同的结果？ {{ select(9) }}
  • 6k6^k-2k2^k
  • AK+2K−1A_{K+2}^{K-1}
  • 6k6^k
  • CK+6−1KC_{K+6-1}^{K}
  1. 箱中有 6 个球，编号分别为 1 到 6。从中拿 3 次球，每次拿一个，拿了后放回和不放回时，取出的数字之和的期望分别是（）:

{{ select(10) }}

  • 10.5，10.5
  • 9，9
  • 9，10.5
  • 10.5，9

11.定义 mod 为取模运算，𝑛! = 1 ⋅ 2 ⋅ 3 ⋯ 𝑛，则下式的值为（

{{ select(11) }}

  • 10081
  • 10085
  • 0
  • 10083
  1. 当 x=10 时，以下代码中 ans 的值为（）。
int ans=0;
void dfs(int x){
  ++ans; 
  if(x<=1)return;
  dfs(x/3);
  if(x/3+1<x) dfs(x/3+1);
  if(x/3+2<x) dfs(x/3+2);
}

{{ select(12) }}

  • 24
  • 25
  • 26
  • 27

13.最大子段和问题，即给出一个长度为 𝑛 的序列 𝑎，选出其中连续且非空的一段使得这段和最大。当我们采用分治算法去计算这道题的结果时（不可直接动态规划且采用最优的分治方式），最优平均复杂度为（ ）。 {{ select(13) }}

  • Θ(n log2 n)
  • Θ(n log n)
  • Θ(n)
  • Θ(1)

14.若某算法的时间计算表示为递推关系式：

T(n)=9T(n/3)+n
T(1)=

则该算法的时间复杂度是（） {{ select(14) }}

  • Θ(n)
  • Θ(2n2^n)
  • Θ(n2n^2)
  • Θ(nlogn)

15.中国计算机协会成立于（ ）年。 {{ select(15) }}

  • 1961
  • 1962
  • 1971
  • 1972

二、阅读程序

(1)、

1 #include <cstdio>
2 #include <cstring>
3 
4 const int maxn = 1003;
5 
6 int type, n, m;
7 char s[maxn], t[maxn];
8 
9 int main() {
10 scanf("%d %s %s", &type, t, s);
11 n = strlen(s); m = strlen(t);
12 if (type < 2) {
13 for (int i = 0; i < m; ++i) s[i] = t[i];
14 } else if (type == 2) {
15 strcpy(s, t);
16 // 提示：如果此时调用 printf("%s\n", s)，则本次输出结果为整个 t 字符串和换行，没有其他字符。
17    } else {
18 for (int i = 0; i < m; i += 4) {
19 unsigned int code = 0, pos = i;
20 for (int j = 1; pos < i+4; j*=100, ++pos) {
21 if (pos == m) break;
22 code += t[pos] * j;
23         }
24 pos = i;
25 while (code != 0) {
26 s[pos++] = code % 100;
27 code /= 100;
28         }
29      }
30 }
31 for (int i = 0; i < n; ++i) printf("%c", s[i]);
32 printf("\n");
33 }

输入保证 t 的长度不大于 s 的长度，且两字符串均只含有大小写字母，不是空串，type = 1,2,3，完成下面的判断题和单选题：

●判断题

  1. 将程序中所有的小于号 (<) 改为不等于号 (!=)，则程序对所有符合要求的输入的输出结果不变。 {{ select(16) }}
  • 对
  • 错
  1. 当输入为 1 xyz abcd 时，程序的输出为 xyzd。 {{ select(17) }}
  • 对
  • 错
  1. 程序在输入为 1 xyz abcd 时的输出与输入为 2 xyz abcd 的输出相同。 （ ） {{ select(18) }}
  • 对
  • 错
  1. 将程序第 25~28 行的 while 循环替换为 do-while 循环（判断条件和循环体不变），则程序对同一合法输入的输出结果一定不变。（ ）

{{ select(19) }}

  • 对
  • 错

●单选题

  1. 若将程序第 13 行改为 for (int i = 0; i < strlen(t); ++i) s[i] = t[i];，且已知输入的 type 一定为 1 的情况下，用 𝑛 表示𝑠 的长度，𝑚 表示 𝑡 的长度，则程序的时间复杂度为（ ）。 {{ select(20) }}
  • Θ(𝑛 + 𝑚)
  • Θ(𝑛 + 𝑚2𝑚^2)
  • Θ(𝑛2𝑛^2 + 𝑚)
  • Θ(𝑛2𝑛^2+ 𝑚2𝑚^2)
  1. 给程序分别输入选项 ( ) 的两组输入数据，得到的输出不同。 {{ select(21) }}
  • 1 ab abc 和 3 ab abc
  • 1 AB ABC 和 3 AB ABC
  • 1 de fgh 和 3 de fgh
  • 1 DE FGH 和 3 DE FGH

（2）、

1 #include <iostream>
2 using namespace std;
3 
4 const int INF = 1000000000;
5 #define Front 0
6 #define Back 1
7 #define Left 2
8 #define Right 3
9 #define Up 4
10 #define Down 5
11 int w[6], a[1003][1003];
12 const int way1[] = {Up, Right, Down, Left};
13 const int way2[] = {Up, Front, Down, Back};
14 const int way3[] = {Left, Front, Right, Back};
15 int get_max(int &a, int b) {
16 return a = max(a, b);
17 }
18 int right_rotate(int &u) {
19 for (int i = 0; i < 4; ++ i)
20 if (u == way1[i])
21 return u = way1[(i + 1) % 4];
22 return u;
23 }
24 int front_rotate(int &u) {
25 for (int i = 0; i < 4; ++ i)
26 if (u == way2[i])
27 return u = way2[(i + 1) % 4];
28 return u;
29 }
30 const int anchorX = Up;
31 const int anchorY = Front;
32 const int anchorZ = Right;
33 int find_down(int u, int v) {
34 if (u == Down || u == Up) return anchorX^(u == Up);
35 if (v == Down || v == Up) return anchorY^(v == Up);
36 for (int i = 0; i < 4; ++ i)
37 if (u == way3[i])
38 return anchorZ ^ (v == way3[(i + 1) % 4]);
39 return -1;
40 }
41 int n, m, dp[1003][1003][6][6];
42 int main() {
43 cin >> n >> m;
44 for (int i = 0; i < n; ++ i)
45 for (int j = 0; j < m; ++ j)
46 cin >> a[i][j];
47 for (int i = 0; i < 6; ++ i)
48 cin >> w[i];
49 for (int i = 0; i < n; ++ i)
50 for (int j = 0; j < m; ++ j)
51 for (int a = 0; a < 6; ++ a)
52 for (int b = 0; b < 6; ++ b)
53 dp[i][j][a][b] = -INF;
54 dp[0][0][anchorX][anchorY] = a[0][0] * w[Down];
55 for (int i = 0; i < n; ++ i)
56 for (int j = 0; j < m; ++ j)
57 for (int p = 0; p < 6; ++ p)
58 for (int q = 0; q < 6; ++ q)
59 if (dp[i][j][p][q] != -INF) {
60 int x = dp[i][j][p][q];
61 int u1 = p, v1 = q;
62 right_rotate(u1);
63 right_rotate(v1);
64 get_max(dp[i][j + 1][u1][v1],
65 x + w[find_down(u1, v1)] * a[i][j + 1]);
66 int u2 = p, v2 = q;
67 front_rotate(u2);
68 front_rotate(v2);
69 get_max(dp[i + 1][j][u2][v2],
70 x + w[find_down(u2, v2)] * a[i + 1][j]);
71 }
72 int ans = -INF;
73 for (int p = 0; p < 6; ++ p)
74 for (int q = 0; q < 6; ++ q)
75 ans = max(ans, dp[n - 1][m - 1][p][q]);
76 printf("%d\n", ans);
77 return 0;
78 }

以下程序的输入数据的绝对值均不超过10310^3。完成下面的判断题和单选题：

●判断题

  1. 存在一种合法的输入数据，使得运行程序时，某次 find_down 函数的返回值是 −1。( )

{{ select(22) }}

  • 对
  • 错

23.该程序的时间复杂度为 Θ(𝑛2𝑛^2𝑚2𝑚^2)。

{{ select(23) }}

  • 对
  • 错

24.对于任意 𝑢 ∈ [0,6)，「先执行 front_rotate(u)，再执行right_rotate(u)」，与「先执行 right_rotate(u)，再执行front_rotate(u)」，最终 𝑢 的值相同。( ) {{ select(24) }}

  • 对
  • 错

●单选题

25.将 anchorX、anchorY、anchorZ 依次更换为（ ）时，对于全部合法数据，与改变之前的输出结果无异。 {{ select(25) }}

  • Left、Front、Down
  • Left、Up、Front
  • Left、Down、Back
  • Down、Right、Front

26.（2 分）对于以下的输入数据，输出结果为 （ ）。

5 5
2 8 15 1 10
5 19 19 3 5
6 6 2 8 2
12 16 3 8 17
12 5 3 14 13
1 1 1 1 1 1

{{ select(26) }}

  • 95
  • 97
  • 94
  • 103

27.（2 分）对于以下的输入数据，输出结果为 （ ）。

2 5
2 8 15 3 10
5 19 19 3 5
1 2 3 4 5 6

{{ select(27) }}

  • 194
  • 157
  • 193
  • 201

（3）、

1 #include <bits/stdc++.h>
2 using namespace std;
3 const int MAXN = 309;
4 const int MAXM = 109;
5 const int MAXP = 100000;
6 typedef long long ll;
7 int n, m, seed,rt,btm,s[MAXM],Len,dfncnt,full_dist,P,t;
8 int lg[MAXN],dfn[MAXN],fa[MAXN],dep[MAXN], lson[MAXN];
9 vector <int> e[MAXN];
10 vector <int> L[MAXM],leaves;
11 int F[MAXM];
12 namespace LCA {
13 int st[24][MAXN];
14 int minNode(int x, int y){return dep[x]<dep[y] ? x:y;}
15 void init() {
16 for (int i = 1; i <= n; ++i) st[0][dfn[i]]=fa[i];
17 for (int i = 1; i <= lg[n]; ++i)
18 for (int j = 1; j + (1 << i) - 1 <= n; ++j)
19 st[i][j] = minNode(st[i - 1][j], st[i - 1][j + (1 
<< (i - 1))]);
20 }
21 int lca(int u, int v) {
22 if (u == v) return u;
23 if ((u = dfn[u]) > (v = dfn[v])) swap(u, v);
24 int d = lg[v - u++];
25 return minNode(st[d][u], st[d][v - (1 << d) + 1]);
26 }
27 }
28 namespace Gen {
29 mt19937 rnd;
30 int pos[MAXN], deg[MAXN];
31 vector <pair<int, int>> edges;
32 void calc() {
33 for (int i = 1; i <= n - 2; ++i)
34 ++deg[pos[i]];
35 set <int> ret; ret.clear();
36 for (int i = 1; i <= n; ++i)
37 if (deg[i] == 1) ret.insert(i);
38 for (int i = 1; i <= n - 2; ++i) {
39 int npos = *ret.begin();
40 edges.push_back(make_pair(npos, pos[i]));
41 ret.erase(ret.begin());
42 --deg[pos[i]];
43 if (deg[pos[i]] == 1)
44 ret.insert(pos[i]);
45 }
46 edges.push_back(make_pair(*ret.begin(), n));
47 }
48 void build() {
49 for (auto i : edges) {
50 int u = i.first, v = i.second;
51 e[u].push_back(v); e[v].push_back(u);
52 }
53 }
54 void generate(int seed) {
55 rnd.seed(seed);
56 edges.clear();

57 for (int i = 1; i <= n; ++i) deg[i] = 1;
58 for (int i = 1; i <= n - 2; ++i)
59 pos[i] = rnd() % n + 1;
60 calc();
61 build();
62 }
63 }
64 int dfs(int u, int _fa, int &bottom) {
65 dfn[u] = ++dfncnt;
66 if (e[u].size() == 1) leaves.push_back(u);
67 lson[u] = -1; fa[u] = _fa; dep[u] = dep[_fa] + 1;
68 int maxlen = 0, dson = u, temp;
69 for (int v: e[u])
70 if (v != _fa) {
71 int p = dfs(v,u,temp);
72 if (p > maxlen) maxlen = p, lson[u]=v, dson=temp;
73 }
74 bottom = dson;
75 return maxlen + 1;
76 }
77 #define dist(u, v) (dep[u]+dep[v]-2*dep[LCA::lca(u, v)])
78 int v[MAXP+9], prime[MAXP + 9], prime_cnt, vis[MAXP+9];
79 void prime_init(int n) {
80 prime_cnt = 0;
81 for (int i = 2; i <= n; ++i) {
82 if (!v[i]) prime[++prime_cnt] = v[i] = i;
83 for(int j=1; j <= prime_cnt && i*prime[j]<=n; ++j) {
84 if (v[i] < prime[j]) break;
85 v[i * prime[j]] = prime[j];
86 }
87 }
88 }
89 vector<int> answer, gline;
90 void solve() {
91 cin >> n >> m >> seed >> t;
92 lg[0] = lg[1] = 0;
93 for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
94 for (int i = 1; i <= n; ++i) e[i].clear();
95 leaves.clear();
96 if (!t) Gen::generate(seed);
97 else {
98 for (int i = 1, u, v; i < n; ++i) {
99 cin >> u >> v;
100 e[u].push_back(v); e[v].push_back(u);
101 }
102 }
103 dep[0] = 0; dfs(1, 0, rt);
104 dfncnt=0; leaves.clear();
105 Len = dfs(rt, 0, btm); LCA::init();
106 for (int k = rt; ~k; k = lson[k]) gline.push_back(k);
107 for (int i = 1, tmp; i <= m; ++i) { {
108 cin >> s[i];
109 L[i].clear();
110 for(int j = 1; j <= s[i]; ++j) {
111 cin >> tmp; L[i].push_back(tmp);
112 }
113 F[i] = dist(L[i].front(), L[i].back());
114 for (unsigned j = 0; j < L[i].size() - 1; ++j)
115 F[i] += dist(L[i][j], L[i][j + 1]);
116 int tmp = F[i] >> 1;
117 while (tmp > 1) vis[v[tmp]] = 1, tmp /= v[tmp];
118 }
119 full_dist = dist(leaves.front(), leaves.back());
120 for (unsigned i = 0; i < leaves.size() - 1; ++i)
121 full_dist += dist(leaves[i], leaves[i + 1]);
122 P = -100000;
123 for (int i = 2; i <= prime_cnt; ++i)
124 if (full_dist+2*Len<prime[i] * 2 && !vis[prime[i]]){
125 P = prime[i] * 2; break;
126 }
127 for (int i = 1; i <= m; ++i) {
128 F[i] >>= 1;
129 while (F[i]>1) vis[v[F[i]]] = 0, F[i] /= v[F[i]];
130 }
131 int left=P-full_dist;
132 int fcnt = left / (2 * (Len - 1)); answer = leaves;
133 while (fcnt--) answer.push_back(rt), 
answer.push_back(btm), left -= 2 * (Len - 1);
134 if (left>>=1) answer.push_back(rt), 
answer.push_back(gline[left]);
135 for (int qwq: answer) cout << qwq << " ";
136 cout << endl;
137 }
138 int main() {
139 prime_init(MAXP);
140 int T; cin >> T;
141 while (T--) solve();
142 }

数据保证，输入的 3≤n≤300，1≤m≤100，1≤s[i]≤n，0≤t≤1，seed 在int 范围内。当seed=623532 时，Gen::pos 数组中的数值（从 1 开始）的前 23 项分别是 22, 25, 12, 23, 7, 11, 20, 4, 3, 13, 10, 2, 7, 18, 1, 9, 23, 13, 10, 5, 23, 18, 6。数据保证 seed 随机生成。

调用 rnd()返回一个[0,2^32)的随机整数。完成下列判断题和单选题：

●判断题

28.调用 LCA::lca() 函数，单次操作的时间复杂度是 𝑂(log 𝑛)。（ ） {{ select(28) }}

  • 对
  • 错

29.在 t=0 的情况下，len 的大小在期望下与 n\sqrt{n} 同阶。（ ） {{ select(29) }}

  • 对
  • 错

30.full_dist 最大不会超过 2𝑛。（ ） {{ select(30) }}

  • 对
  • 错

●单选题

31.（2 分）对于给定的如下数据后，输出的结果为（）？

1
5 2 123456 1
1 2
2 3
3 4
4 5
2 1 4
2 3 5

{{ select(31) }}

  • 2 5 1 5 1 5
  • 4 3 4 3 4 1
  • 5 1 5 1 5 2
  • 4 1 4 1 4 5

32.（2 分）对于给定的如下数据后，输出的结果为（）？

1
25 4 623532 0
3 11 3 5
5 24 17 15 19 17
6 14 21 16 8 18 21
8 21 18 17 19 24 21 24 17

{{ select(32) }}

  • 19 24 17 5 17 19 24 4 3 20 11
  • 19 24 17 15 8 16 21 14 19 8 19 13
  • 14 18 21 8 9 21 14 8 15 24 17 19
  • 14 18 21 8 9 21 14 8 22 16 14

33.答案序列长度的理论上界（）？ {{ select(33) }}

  • Θ(𝑛0.5𝑛^{0.5})
  • Θ(𝑛 log 𝑛)
  • Θ(log 𝑛)
  • Θ(𝑛)

三、完善程序（单选题，每小题 3 分，共计 30 分）

（1）

（凑出 17）给定 𝑛(1 ≤ 𝑛 ≤ 20) 个互不相同的正整数𝑎1,𝑎2,…𝑎𝑛(1≤𝑎𝑖≤109) 𝑎_1, 𝑎_2, … 𝑎_𝑛 (1 ≤ 𝑎_𝑖 ≤109)，将之排成一行。你需要在每个 𝑎𝑖𝑎_𝑖 前加上一个加号(+)或减号(-)，使这 𝑛 个数字组成一个算式。请问是否存在一种添加符号的方案，使该算式 的值为 17？如果存在，请输出 Yes，否则输出 No。

例如，给定 $𝑛 = 5, 𝑎_1 = 1, 𝑎_2 = 4, 𝑎_3 = 5, 𝑎_4 = 9, 𝑎_5 = 8$，则 −𝑎1−𝑎2+𝑎3+𝑎4+𝑎5−𝑎_1 − 𝑎_2 +𝑎_3 + 𝑎_4 + 𝑎_5 = 17。 提示：使用穷举法解决这个问题。 试补全程序。

1 #include <cstdio>
2 
3 using namespace std;
4 
5 const int maxn = 25;
6 const int aim = 17;
7 
8 int n;
9 int a[maxn];
10 bool ans;
11 
12 int getBit(const int s, int p) {
13 return ①;
14 }
15 
16 int main() {
17 scanf("%d", &n);
18 for (②) scanf("%d", a + i);
19 for (int s=0, upperBound = ③; s <= upperBound; ++s){
20 ④;
21 for (int j = 0; j < n; ++j) if (getBit(s, j) == 1){
22 sum += a[j];
23 } else {
24 ⑤;
25 }
26 if (int(sum) == aim) {
27 ans = true;
28 break;
29 }
30 }
31 printf("%s\n", ans ? "Yes" : "No");
32 }

34.①处应填（ ） {{ select(34) }}

  • (s >> p) & 1
  • (s << p) & 1
  • s & (1 << p) & 1
  • s & (1 >> p) & 1

35.② 处应填（ ）。 {{ select(35) }}

  • int i = 0; i <= n; ++i
  • int i = 1; i <= n; ++i
  • int i = 0; i < n; ++i
  • int i = 1; i < n; ++i

36.③处应填（ ） {{ select(36) }}

  • 1 << n
  • (1 << n) | 1
  • (1 << n) + 1
  • (1 << n) -1

37.④处应填（ ） {{ select(37) }}

  • int sum = 0
  • unsigned long long sum = 0
  • unsigned short sum = 0
  • unsigned int sum = 0

38.⑤处应填（ ） {{ select(38) }}

  • sum = a[j] + sum
  • sum = a[j] - sum
  • sum = -a[j] + sum
  • sum = -a[j] - sum

2）、 (树同构问题) 对于两棵有𝑛 𝑛 个结点的有根树 𝑇1𝑇_1 和𝑇2 𝑇_2，如果存在一个长 度为𝑛 𝑛 的排列 𝑎𝑖𝑎_𝑖，使得对于 𝑇1𝑇_1 中的任意结点对 (𝑖,𝑗)，𝑇1(𝑖,𝑗)，𝑇_1 中存在边 𝑖→𝑗𝑖 → 𝑗当且仅当𝑇2 𝑇_2 中存在边𝑎𝑖→𝑎𝑗 𝑎_𝑖 → 𝑎_𝑗，则称 𝑇1𝑇_1 与𝑇2 𝑇_2 同构。现在给出两棵树，求出它们是否同构。

为了解决该问题，有一个算法叫 AHU 算法，其时间复杂度为 𝑶(𝒏𝐥𝐨𝐠 𝒏)，步 骤如下：

⚫ 考虑将有根树转化为括号序列的递归算法，我们在回溯时会将子树的括号序列依次拼接起来。

⚫ 如果保证拼接子树括号序列得到的结果与遍历子树的顺序无关，则可保证同构的有根树可以转换为完全一致的括号序列。

⚫ 考虑回溯时将子树括号序列按字典序排序，将以此方式得到的两棵树的括号序列进行比较即可得知两树是否同构。

于是我们得到了一个 𝑂(𝑛2) 时间复杂度的朴素算法，考虑下述优化：

⚫ 考虑朴素算法的复杂度瓶颈，在于括号序列的长度与子树大小相关。

⚫ 递归时深度为 𝑘 的结点对应的括号序列，可以仅由深度为 𝑘 + 1 的子结点的括号序列得出。

⚫ 我们考虑对于每个深度 𝑘，将两树中深度为 𝑘 的结点对应的括号序列作为值域进行离散化。

⚫ 将原先的子结点括号序列的拼接（字符串），用子结点离散化后结果的拼接（整数序列）替代。

这样我们就将与子树大小挂钩的括号序列替换成了与结点度数挂钩的序列，复杂度大大降低。试补全程序。

1 #include <iostream>
2 #include <vector>
3 #include <algorithm>
4 
5 typedef std::vector<int> Nodes;
6 
7 struct RootedTree {
8 int size, root;
9 std::vector<Nodes> edges;
10 };
11 
12 RootedTree read() {
13 RootedTree res;
14 std::cin >> res.size >> res.root;
15 res.edges.resize(res.size + 1);
16 
17 for (int i = 1; i < res.size; ++ i) {
18 int u, v;
19 std::cin >> u >> v;
20 res.edges[u].push_back(v);
21 res.edges[v].push_back(u);
22 }
23 
24 return res;
25 }
26 
27 std::vector<Nodes> D; // 某个深度下的所有结点
28 std::vector<int> fa;
29 
30 int dfs_depth(const RootedTree &tree, int now, int f, int 
depth, int nodesDiff) {
31 if (①) // 1
32 D.push_back(Nodes());
33 
34 int nowId = now + nodesDiff;
35 D[depth].push_back(nowId);
36 if (f != -1)
37 fa[nowId] = f + nodesDiff;
38 
39 int maxDepth = 0;
40 for (int i = 0; i < tree.edges[now].size(); ++ i) {
41 int child = tree.edges[now][i];
42 if (②) { // 2
43 maxDepth = std::max(maxDepth,
44 dfs_depth(tree,child,now,depth+1,nodesDiff));
45 }
46 }
47 return maxDepth + 1;
48 }
49 
50 typedef std::vector<int> Hash;
51 
52 std::vector<Hash> hash;
53 
54 bool cmp(const int x, const int y) {
55 return ③; // 3
56 }
57 
58 bool check(const RootedTree &t1, const RootedTree &t2) {
59 if (t1.size != t2.size)
60 return false;
61 int size = t1.size;
62 
63 D.clear();
64 fa.clear();
65 fa.resize(size * 2 + 1);
66 
67 int dep1 = dfs_depth(t1, t1.root, -1, 0, 0);
68 int dep2 = dfs_depth(t2, t2.root, -1, 0, size);
69 if (dep1 != dep2)
70 return false;
71 
72 hash.clear();
73 hash.resize(size * 2 + 1);
74 std::vector<int> rank(size * 2 + 1);
75 
76 for (④) { // 4
77 for (int i = 0; i < D[h + 1].size(); ++ i) {
78 int node = D[h + 1][i];
79 hash[fa[node]].push_back(rank[node]);
80 }
81 std::sort(D[h].begin(), D[h].end(), cmp);
82 rank[D[h][0]] = 0;
83 for (int i = 1, cnt = 0; i < D[h].size(); ++ i) {
84 if (⑤) // 5
85 ++ cnt;
86 rank[D[h][i]] = cnt;
87 }
88 }
89 
90 return hash[t1.root] == hash[t2.root + size];
91 }
92 
93 int main() {
94 RootedTree treeA, treeB;
95 
96 treeA = read();
97 treeB = read();
98 
99 bool isomorphism = check(treeA, treeB);
100 
101 std::cout
102 << (isomorphism ? "wow!" : "emm...")
103 << std::endl;
104 return 0;
105 }

提示：std::vector::operator< 的判定方法为：对两个 vector a,b，找到最小的满足 a[i]!=b[i] 的 i，返回 a[i]<b[i] 的判定结果。若这样的i 不存在，返回 false。

39.①处应填（ ） {{ select(39) }}

  • D.size() < depth
  • D.size() > depth
  • D.size() != depth
  • D.size() == depth

40.②处应填（ ） {{ select(40) }}

  • child != f + nodesDiff
  • child != f
  • child + nodesDiff == f + nodesDiff
  • child + nodesDiff != f

41.③处应填（ ） {{ select(41) }}

  • rank[fa[x]] < rank[fa[y]]
  • hash[x].size() < hash[y].size()
  • rank[x] < rank[y]
  • hash[x] < hash[y]

42.④处应填（ ） {{ select(42) }}

  • int h = dep1-1; ~h; --h
  • int h = dep1-1; h; --h
  • int h = dep1-2; ~h; --h
  • int h = dep1-2; h; --h

43.⑤ 处应填（ ）。 {{ select(43) }}

  • hash[D[h][i]] != hash[D[h][i - 1]]
  • rank[D[h][i]] != rank[D[h][i - 1]]
  • hash[D[h][i]] < hash[D[h][i - 1]]
  • rank[D[h][i]] < rank[D[h][i - 1]]
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  7. 兼容模式
  8. 主题
  6. Worker 0, 26ms
  7. Powered by Hydro v4.15.0 Community