注：因为刚弄完就发出来了，不保证没有错误。欢迎反馈。

2024 矩阵群非专业级别小潜可爱能力认证第一轮 （SCP-S1）提高级 C++ 语言试题

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

1 使用 \texttt{g++} 编译 \texttt{C++} 程序时，只编译生成目标文件的命令行选项是（）。

A \texttt{-o} B \texttt{-a} C \texttt{-c} D \texttt{-g}

2 以下可以作为 \texttt{C++} 中的变量名的是（）。

A \texttt{0\_yu} B \texttt{Ling-luo} C \texttt{case} D \texttt{constant}

3 如果以下图都是无向简单连通图，（）一定是边双连通的。

A 基环树 B 完全图 C 2-正则图 D 二分图

4 有三维向量 \overrightarrow{OA}=(1,-2,1),\overrightarrow{OB}=(3,0,-1)，则 \overrightarrow{OA}\times\overrightarrow{OB}=（）。

A (2,4,6) B (2,-4,6) C (-2,4,-6) D (-2,-4,-6)

5 \texttt{C++} 中，以下字面量中最大的是（）。

A \texttt{361425ull} B \texttt{01234567} C \texttt{10.0e4} D \texttt{0xEE0000p-5}

6 现在有一个表达式，它的前缀表达式为 \texttt{C B D H F A G I E}，后缀表达式为 \texttt{D F A H B I E G C}，其中 \texttt{A},\texttt{B},\texttt{C},\cdots,\texttt{I} 均为数或二元运算符。下列说法正确的是（）。

A \texttt{B} 是运算符而 \texttt{H} 是数 B 若要计算这个表达式，可以先计算前缀表达式为 \texttt{B D H} 的表达式的结果 C 若 \texttt{B} 的优先级最高，\texttt{G} 的优先级其次，其余运算符优先级相同，则该表达式写成中缀表达式为 \texttt{D B (F H A) C I G E} D 若根节点的深度为 1，则这个表达式的表达式树高为 5

7 从 x=0 开始，每次独立地有 \dfrac12 的概率让 x 减 1，有 \dfrac12 的概率让 x 加 1，直到 x=-3 或 x=9 为止。最终停止且 x=-3 的概率是（）。

A \dfrac89 B \dfrac34 C \dfrac23 D \dfrac12

8 设 T(n)=\begin{cases}T(0.6n)+T(0.8n)+n^2\log_2 n&n>1\\1&n\le 1\end{cases}，T(n)=\Theta(f(n))，则以下可能是 f(n) 的是（）。

A n^2\log_2 n B n^2\log_2^2n C n^{\log_{5/3}2} D n^{\log_{5/4}2}

9 将 5 个元素排序最坏情况下至少需要（）次比较。

A 6 B 7 C 8 D 9

10 从“冷，冻，泠，洛，汶，格，栋，玲，珞，零，雯，霾”共 12 个形声字中无序地选出 3 个，满足它们的形旁和声旁都不同的方案有（）种。例如，“泠、珞、霾”是一种可行的方案，但是“泠、珞、零”不是，因为“泠”和“零”有相同的声旁“令”。

A 66 B 68 C 71 D 72

11 如图所示的有向图中，设经过恰好 L 条边的途径（可以经过重复的点或边）有 w(L) 条，则关于 w 的渐进复杂度，以下说法正确的是（）。

A w(L)=\Theta(1) B w(L)=\Theta(L) C w(L)=\Theta(L^2) D w(L)=\Theta(L^3)

12 字符串 \texttt{mississippi} 有（）个本质不同的非空回文子串。两个子串是本质不同的当且仅当它们的长度不同或者某个位置上的字符不同。

A 8 B 9 C 10 D 11

13 定义 f(n)=\begin{cases}0&n=1\\f\left(\left\lfloor\sqrt n\right\rfloor\right)+1&n>1\end{cases}，设对于 n=1,2,\cdots,10^{18}，f(n) 的和等于 s，s 写为十进制的每一位数之和为 t，则 t 除以 7 的余数为（）。

A 2 B 3 C 4 D 5

14 假设我们有以下的 \texttt{C++} 代码：

01 unsigned short a=361425u,b=1114114u,c=712u;
02 a<<=b;
03 unsigned res=c^a+b<<1;

则 \texttt{res} 的值是（）。

A 3\,456 B 3\,472 C 6\,940 D 7\,236

15 设根节点的深度为 1。有一个 2\,024 个结点的完全 k 叉树（k\ge 2），则 k 与该树的深度之和最小为（）。

A 10 B 11 C 12 D 13

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ×；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

（1）

01 #include <iostream>
02 #include <cstdio>
03 #include <cmath>
04 using namespace std;
05 const double pi = atan(1);
06 double x1, y1, r1, x2, y2, r2, ans, dst, x, y;
07 int main()
08 {
09  cout.flags(ios::fixed);
10  cout.precision(4);
11  cin >> x1 >> y1 >> r1 >> x2 >> y2 >> r2;
12  dst = hypot(x1 - x2, y1 - y2);
13  if(dst >= r1 + r2)
14  {
15      cout << 0;
16  }
17  else if(dst <= fabs(r1 - r2))
18  {
19      cout << pi * 4 * min(r1, r2) * min(r1, r2);
20  }
21  else
22  {
23      x = acos((r1 * r1 + dst * dst - r2 * r2) / 2 / r1 / dst) * 2;
24      y = acos((r2 * r2 + dst * dst - r1 * r1) / 2 / r2 / dst) * 2;
25      cout << (x - sin(x)) * r1 * r1 / 2 + (y - sin(y)) * r2 * r2 / 2; 
26  }
27  cout << endl;
28  return 0;
29 }

假设输入的所有数都是绝对值都不超过 10 的整数，r1 和 r2 为正整数，完成下面的判断题和单选题：

判断题

16 将 \texttt{13} 行的 dst >= r1 + r2 改为 dst > r1 + r2 不会影响程序运行的结果。

17 将 \texttt{19} 行的 pi * 4 改为 acos(-1) 不会影响程序运行的结果。

18（1 分） 将 \texttt{09} 行删去不会影响程序运行的结果。

19 当输入为 \texttt{0 0 1 1 0 1} 时，输出为 \texttt{1.1285}。

选择题

20（2.5 分） 当输入为 \texttt{0 0 1 1 1 1} 时，输出为（）。

A \texttt{0.1416} B \texttt{0.5708} C \texttt{0.7854} D \texttt{1.0000}

21 这段代码的含义为（ ）。

A 求两圆的面积交 B 求两圆的面积并 C 求两圆的周长并 D 求两圆的周长交

（2）

01 #include <iostream>
02 using namespace std;
03 const long long mod = 1000000007;
04 long long f(int n)
05 {
06  long long x = 1, y = 0, z = 0;
07  for (int i = 0; i < n; i++)
08  {
09      long long nx = (x + 5 * y) % mod, ny = (x + y) % mod;
10      if(nx & 1) nx += mod; nx >>= 1;
11      if(ny & 1) ny += mod; ny >>= 1;
12      x = nx;
13      y = ny;
14  }
15  z = x; x = 1; y = 0;
16  for (int i = 0; i < n; i++)
17  {
18      long long nx = (x - 5 * y) % mod, ny = (y - x) % mod;
19      if(nx & 1) nx += mod; nx >>= 1;
20      if(ny & 1) ny += mod; ny >>= 1;
21      x = nx;
22      y = ny;
23  }
24  z += x;
25  return (z + mod) % mod;
26 }
27 int n;
28 int main()
29 {
30  cin >> n;
31  cout << f(n) << endl;
32  return 0;
33 }

假设输入是不超过 40 的正整数，完成下面的判断题和单选题：

判断题

22 将 \texttt{03} 行的 1000000007 替换为 1000000005 不会影响程序运行的结果。

23 将 \texttt{06} 行的 long long 替换为 int 不会影响程序运行的结果。

24 将 \texttt{09} 行的 long long 替换为 int 不会影响程序运行的结果。

25 将 \texttt{10} 行替换为 nx = nx * 500000003 % mod; 不会影响程序运行的结果。

选择题

26（2.5 分）当输入为 \texttt{5} 时，输出为（）。

A \texttt{5} B \texttt{7} C \texttt{8} D \texttt{11}

27 当 n\ge 5 时，f(n) 满足（）的递推式。

A f(n)=f(n-1)+f(n-2) B f(n)=5f(n-1)+f(n-2) C f(n)=f(n-1)+5f(n-2) D f(n)=5f(n-1)+5f(n-2)

28 若将 \texttt{15} 行的 z = x 改成 z -= y，\texttt{24} 行的 z += x 改成 z += y，则当输入为 \texttt{13} 时，输出为（）。

A \texttt{233} B \texttt{377} C \texttt{999999630} D \texttt{999999774}

（3）

01 #include <iostream>
02 using namespace std;
03 int n;
04 int a[2005];
05 int stk[2005],val[2005],cnt;
06 int solve1()
07 {
08  val[cnt] = 361425;
09  for(int i = 1; i <= n; i++)
10  {
11      while(a[i] <= a[stk[cnt]]) --cnt;
12      stk[++cnt] = i;
13      val[cnt] = min(val[cnt-1], a[stk[cnt]] - stk[cnt]) ;
14  }
15  return val[cnt];
16 }
17 int solve2()
18 {
19  int result = -- a[1];
20  for(int i = 2; i <= n; i++) result=min(result, a[i] - i);
21  return result;
22 }
23 int main()
24 {
25  cin >> n;
26  for (int i = 1; i <= n; i++) cin >> a[i];
27  a[0] = -361425 ;
28  cnt = 1;
29  cout << solve1() << endl;
30  cout << solve2() << endl;
31  return 0;
32 }

假设输入的 n 是不超过 2\,000 的正整数，a[i] 是不超过 2\, 000 的非负整数，完成下面的判断题和单选题：

判断题

29 将 \texttt{11} 行的 a[i] <= a[stk[cnt]] 替换为 a[i] < a[stk[cnt]] 不会影响程序运行的结果。

30（1 分） 将 \texttt{15} 行的 val[cnt] 替换为 val[2] 不会影响程序运行的结果。

31 删去 \texttt{27} 行不会影响程序运行的结果。

32 （1 分）交换 \texttt{29} 行和 \texttt{30} 行不会影响程序运行的结果。

33 程序总是输出两个相等的数。

选择题

34 （2.5 分）该程序的最坏时间复杂度是（）。

A \Theta(n) B \Theta(n\log n) C \Theta(n^2) D 程序可能非正常结束或死循环

35 若输入为 8 3 1 7 5 6 5 3 5，则程序运行到 \texttt{15} 行时 cnt 的值为（）。

A 2 B 3 C 4 D 5

36 （2.5 分）删去 \texttt{08} 行后，函数 solve1 的原返回值和现返回值的大小关系是（）。

A 一定小于等于且不一定小于 B 一定大于等于且不一定大于 C 一定大于 D 以上三种情况都不对

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

（1）

（求和问题）给定正整数 N，求 \displaystyle\sum_{i=1}^N i\times(N\bmod i) 对 10^9+7 的值。N\le 10^{12}，要求在 1 秒内求出答案。

提示：将 \left\lfloor\dfrac Ni\right\rfloor 相同的 i 放在一起计算。试补全程序。

01 #include <iostream>
02 using namespace std;
03 const long long mod = 1000000007;
04 long long n, l, r;
05 long long answer;
06 long long s1(long long L, long long R)
07 {
08  return ①;
09 }
10 long long s2(long long L, long long R)
11 {
12  return ②;
13 }
14 int main()
15 {
16  cin >> n;
17  for(l = 1; l <= n; l = r + 1)
18  {
19      r = ③;
20      answer = (answer + (n % mod) * s1(l, r) ④ * s2(l, r) ) % mod; 
21  }
22  ⑤;
23  cout<< answer << endl;
24  return 0;
25 }

37 ①处应填（ ）

A (L + R) * (R - L + 1) / 2 % mod

B (L + R) * (R - L + 1) % mod * (mod + 1) / 2 % mod

C ((L + R) % mod) * ((R - L + 1) % mod) % mod / 2 % mod

D ((L + R) % mod) * ((R - L + 1) % mod) % mod * ((mod + 1)/2) % mod

38 ②处应填（ ）

A ((R - L + 1) % mod) * ((2 * (R % mod ) * ((L + R) % mod) + 2 * (L % mod) * (L % mod) + R - L) % mod ) % mod * ((mod + 1)/6) % mod

B ((R - L + 1) % mod) * ((2 * (R % mod ) * ((L + R) % mod) + 2 * (L % mod) * (L % mod) + R + L) % mod ) % mod * ((mod + 1)/6) % mod

C ((R - L + 1) % mod) * (((R % mod ) * ((L + R) % mod) + (L % mod) * (L % mod) + R - L + 1) % mod ) % mod * ((mod + 1)/3) % mod

D ((R - L + 1) % mod) * (((R % mod ) * ((L + R) % mod) + (L % mod) * (L % mod) + R + L) % mod ) % mod * ((mod + 1)/6) % mod

39 ③处应填（ ）

A l

B n / l

C n / (n / l)

D n / (n / (n / l))

40 ④处应填（ ）

A - l % mod

B + r % mod

C - n / l

D + n / r % mod

41 ⑤处应填（ ）

A if(answer < 0) answer += mod

B if(answer >= mod) answer -= mod

C answer %= mod

D answer += mod

（2）

（最大子段和）：给定 N 和长度为 N 的整数序列 A_1,A_2,\cdots,A_n，给定 Q 和 Q 次操作，每次操作输入正整数 T,L,R，若 T=1，表示对所有 i=L,L+1,\cdots,R 令 A_i\to -A_i。若 T=2，表示询问 A_L,A_{L+1},\cdots,A_R 的最大子段和。子段可以为空，但是下标必须连续。

```cpp 01 #include <iostream> 02 using namespace std; 03 struct Node{ 04 long long s,l,r,m,L,R,M; 05 Node() 06 { 07 s=l=r=m=L=R=M=0; 08 } 09 Node(long long a) 10 { 11 ① 12 } 13 Node(long long a,long long b,long long c,long long d,long long e,long long f,long long g) 14 { 15 s=a;l=b;r=c;m=d;L=e;R=f;M=g; 16 } 17 }; 18 Node operator-(const Node&A) 19 { 20 return ②; 21 } 22 Node operator+(const Node&A,const Node&B) 23 { 24 return ③; 25 } 26 struct segtree{ 27 bool tag[200005<<2]; 28 Node s[200005<<2]; 29 void pushdown(int i) 30 { 31 if(④) 32 { 33 tag[i]=!tag[i]; 34 tag[i<<1]=!tag[i<<1]; 35 tag[i<<1|1]=!tag[i<<1|1]; 36 s[i<<1]=-s[i<<1]; 37 s[i<<1|1]=-s[i<<1|1]; 38 } 39 } 40 void build(int i,int l,int r,long long *a) 41 { 42 tag[i]=true; 43 if(l==r) 44 { 45 s[i]=a[l]; 46 } 47 else 48 { 49 int m=(l+r)>>1; 50 build(i<<1,l,m,a);build(i<<1|1,m+1,r,a); 51 s[i]=s[i<<1]+s[i<<1|1]; 52 } 53 } 54 void update(int i,int il,int ir,int ql,int qr) 55 { 56 if(il>qr||ql>ir) return ; 57 if(ql<=il&&ir<=qr) 58 { 59 ⑤ 60 } 61 int m=(il+ir)>>1;pushdown(i); 62 update(i<<1,il,m,ql,qr);update(i<<1|1,m+1,ir,ql,qr); 63 s[i]=s[i<<1]+s[i<<1|1]; 64 } 65 Node query(int i,int il,int ir,int ql,int qr) 66 { 67 if(il>qr||ql>ir) return Node(); 68 if(ql<=il&&ir<=qr) return s[i]; 69 int m=(il+ir)>>1;pushdown(i); 70 return query(i<<1,il,m,ql,qr)+query(i<<1|1,m+1,ir,ql,qr); 71 } 72 }; 73 segtree seg; 74 int n,q; 75 long long a[200005]; 76 int t,l,r; 77 int main() 78 { 79 ios_base::sync_with_stdio(false); 80 cin>>n; 81 for(int i=1;i<=n;++i) cin>>a[i]; 82 seg.build(1,1,n,a); 83 cin>>q; 84 for(int i=1;i<=q;++i) 85 { 86 cin>>t>>l>>r; 87 if(t==1) seg.update(1,1,n,l,r); 88 else cout<<seg.query(1,1,n,l,r).m<<endl; 89 } 90 return 0; 91 } ``` **42** ①处应填（ ） **A** `s=a;l=r=m=a;L=R=M=-a;` **B** `s=a;l=r=m=max(0,a);L=R=M=max(0,-a);` **C** `s=a;l=r=m=max(0ll,a);L=R=M=max(0ll,-a);` **D** `s=max(0,a);l=r=m=max(0,a);L=R=M=max(0,-a);` **43** ②处应填（ ） **A** `Node(A.s,A.L,A.R,A.M,A.l,A.r,A.m)` **B** `Node(-A.s,A.L,A.R,A.M,A.l,A.r,A.m)` **C** `Node(A.s,-A.l,-A.r,-A.m,-A.L,-A.R,-A.M)` **D** `Node(-A.s,-A.l,-A.r,-A.m,-A.L,-A.R,-A.M)` **44** ③处应填（ ） **A** `Node(A.s+B.s,max(A.l,A.s+B.l),max(A.r+B.s,B.r),max(max(A.m,B.m),A.r+B.l),max(A.L,A.s+B.L),max(A.R+B.s,B.R),max(max(A.M,B.M),A.R+B.L))` **B** `Node(A.s+B.s,max(A.l,A.s+B.l),max(A.r+B.s,B.r),max(max(A.m,B.m),A.r+B.l),min(A.L,A.s+B.L),min(A.R+B.s,B.R),min(mn(A.M,B.M),A.R+B.L))` **C** `Node(A.s+B.s,max(A.l,A.s+B.l),max(A.r+B.s,B.r),max(max(A.m,B.m),A.r+B.l),max(A.L,-A.s+B.L),max(A.R-B.s,B.R),max(max(A.M,B.M),A.R+B.L))` **D** `Node(max(max(A.s,B.s),A.s+B.s),max(A.l,A.s+B.l),max(A.r+B.s,B.r),max(max(A.m,B.m),A.r+B.l),max(A.L,-A.s+B.L),max(A.R-B.s,B.R),max(max(A.M,B.M),A.R+B.L))` **45** ④处应填（ ） **A** `tag[i]` **B** `!tag[i]` **C** `true` **D** `tag[i<<1]||tag[i<<1|1]` **46** ⑤处应填（ ） **A** `tag[i]=!tag[i];pushdown(i);` **B** `tag[i]=!tag[i];pushdown(i);return ;` **C** `s[i]=-s[i];tag[i]=!tag[i];` **D** `s[i]=-s[i];tag[i]=!tag[i];return ;`