2022年第20届NOC大赛_C++软件创意编程赛项_选拔赛_初中组真题（忽略分值）参考答案

一、单选题

1、一个C++的源程序中，有关主函数的说法正确的是（）

A 可以有多个主函数

B 必须有一个主函数

C 必须有主函数和其他函数

D 可以没有主函数

2、下列四个不同进制的数中，与其他三项数值上不相等的是（）

A、

(42.8)₁₆

B、

(66.5)₁₀

C、

(102.4)₈

D、

(1000011.1)₂

3、在上面的条件语句中（其中s1和s2代表C++语言的语句），只有一个在功能上与其他三个语句不等价，它是（）

A、

if (n) s1; else s2;

B、

if (n == 0) s1; else s2;

C、

if (n == 0) s2; else sl;

D、

if (n != 0) s1; else s2;

4、从1到2022这2022个数中，共有____个包含数字2的数。()

A、

565

B、

629

C、

630

D、

566

5、若定义int a=2，b=2，下列表达式中值不为4的是（）。

A a*(++b)

B a*(b++)

C a+b

D a*b

6、若有如下程序段，其中s、n、i均为已定义的长整型变量。

s=0;

for(i=1;i<=n;i++)

{

s=s*2+1;

}

当n=50时，s的值为

A、

2⁴⁹-1

B、

2⁵⁰-1

C、

2⁵¹-1

D、

以上答案都不对

7、对于入栈顺序为 a，b，c，d，e，f的序列，下列（）是不合法的出栈序列。

A a,b,c,d,e,f

B a,c,e,b,d,f

C e,d,c,f,b,a

D b,a,d,c,f,e

8、（   ）的平均时间复杂度为 O(n log n)，其中 n是待排序的元素个数。

A、

插入排序

B、

冒泡排序

C、

快速排序

D、

基数排序

9、若二维数组a有n列，则a[i][j]前的元素个数为（）

A、

i*n+j

B、

i*n+j-1

C、

i*n+j+1

D、

j*n+i

10、设某算法的时间复杂度函数的递推方程是T(n)=T(n-1)＋n²（n为正整数）及T(1)=1，则该算法的时间复杂度为（）。

A O(2ⁿ)

B O(n²logn)

C O(n²)

D O(n³)

11、阅读以下程序，执行以下程序后，下列选项中说法错误的是（）

A cnta的值为字符串str中大小写字母的个数

B、

cntn的值为字符串str中'0'~'9'数字的个数

C、

cnta + cntn的值一定等于字符串str的字符个数

D、

字符串str中可能存在空格

12、阅读以下程序，执行以下程序后，下列选项中说法正确的是（）

A 该程序会输出字符串s中所有仅出现了一次的字符的出现次数

B 如果字符串s中存在多个仅出现一次的字符，则会输出"no"

C 该程序会输出字符串s中所有仅出现了一次的字符

D 如果字符串s中所有字符的出现次数都多于1次，则会输出"no"

13、

运行以上程序，输出结果为（）

A 633

B 631023

C 623013

D 632103

14、阅读以下程序，执行以下程序后，

第一行输入n,m;(m<=n)第二行输入n个数。

如果输入的n个数data[i]都相同，则程序输出的值为（）

A m+1

B m

C 1

D 0

15、阅读以下程序，执行以下程序后，

第一行输入n,m;(m<=n)第二行输入n个数。

如果输入的n个数data[i]为升序且互不相同，则程序输出的值为（）

A n-m+1

B n-m-1

C n-m

D m+1

二、实操题

16、密码翻译

【题目描述】

我们得到了由如下加密规则加密而成的一段密文，请你解密出原文。

加密规则：把所有原文中的英文字母以之后的第k个字母代替，如果超出字母表，则转回第一个字母。

例如，规定k=4，则字母'A'以'E'代替（A->B->C->D->E），字母'X'以字母'B'代替（X->Y->Z->A->B）。因此单词“AXE”加密后为“EBI”；如果密文是“EAEC”则可以推出明文是"AWAY"。

给出一段仅有大小写英文字母和数字组成的密文和密钥k，请你解密出原文。

注意，原文和密文对应位置的字母的大小写应保持一致。

【输入格式】

第一行，一个正整数k；

第二行，一个仅有大小写英文字母和数字组成的密文字符串。

【输出格式】

共一行，为解密后的原文字符串。

【输入样例1】

3

QRF

【输出样例1】

NOC

【输入样例2】

53 Dqq11

【输出样例2】

Cpp11

【数据范围】

对于40%的数据，1≤k≤26，1≤字符串长度<100，字符串仅有大小写字母组成。

对于100%的数据，1≤k≤100，1≤字符串长度≤1000

参考答案：根据给定的加密规则，首先根据输入中的k值，建立对应的映射关系。然后根据这个映射关系，对输入的密文字符串进行解密。最后，将解密后的结果输出。

17、体操训练

【题目描述】

为了提高健康水平，同学开始进行体操训练了！

共安排了K次训练课，每次课体委都会根据N个同学的表现给他们进行排名。之后，他想知道，有多少种一个同学会“完胜”另外一个同学的情况。（如果某同学A在每次训练课中都表现得都比另一个同学B要好，那么称A"完胜"B。）

请编程计算有多少种一个同学会“完胜”另外一个同学的情况。

【输入格式】

输入的第一行包含两个正整数K和N。

以下K行每行包含整数1...N的某种排列，表示同学们的排名（同学们用编号1....N进行区分）。如果在某一行中A出现在B之前，表示同学A表现得比同学B要好。

【输出格式】

输出一行，一个整数表示有多少种一个同学会"完胜"另外一个同学的情况。

【输入样例1】

3 4

4 1 2 3

4 1 3 2

4 2 1 3

【输出样例1】

4

【样例1说明】

共有4种情况：

4号同学完胜1号同学

4号同学完胜2号同学

4号同学完胜3号同学

1号同学完胜3号同学

【输入样例2】

3 10

10 1 4 2 3 9 5 7 8 6

8 4 9 10 7 6 3 1 2 5

1 6 7 2 4 3 8 9 10 5

【输出样例2】

9 

【数据范围】

对于60%的数据，1≤k≤20，1≤n≤100

对于100%的数据，1≤k≤1000，1≤n≤100

参考答案：```#includeusing namespace std;int main()int K, N;cin >> K >> N;int a[K][N+1];for(int i=0; i> a[i][j];}}int res = 0;for(int i=1; i<=N; i++){for(int j=1; j<=N; j++){if(i != j){bool ok = true;for(int k=1; k<=K; k++){if(a[k-1][i] > a[k-1][j]){ok = false;break;}}if(ok) res++;}}}cout << res << endl;return 0;```

18、飞跃摩天楼

【题目描述】

东东是一位穿梭在暗夜的城市里惩恶扬善的超级英雄，但是在一次侦查的过程中，他被一群坏蛋发现了。为了逃脱恶人的追捕，东东需要在摩天楼的屋顶之间飞跃，最终到达安全的位置。逃跑路线—共有N座摩天大楼，从1到N进行编号，东东从1号大楼出发，通过特制的跳跃装置跳到2号大楼，然后再通过2号大楼跳到3号大楼……最终跳到N号大楼，就是目标的安全位置。由于跳跃距离越远，跳跃装置的安全性就越差，所以东东希望他跳跃的最大距离尽可能小。为了安全，东东已经提前准备好两个强力热气球，热气球可以代替大楼作为东东一次跳跃的终点和下一次跳跃的起点，他可以把热气球安排在合适的位置，来帮助他更安全的逃脱。

为了确定自己能顺利逃脱，东东需要他的技术顾问，也就是你，替他算出在最安全的情况下，他最大的跳跃距离。

【输入格式】

输入有两行，第一行为两个正整数N，表示摩天大楼的数量。

第二行有N-1个整数，表示第i座摩天大楼与第i＋1座摩天大楼之间的距离。

【输出格式】

输出一个整数，表示东东最大的跳跃距离，如果结果是小数，请向上取整。

【输入样例1】

6

3 5 4 11 8 

【输出样例1】

6 

【样例1说明】

在第4和第5座摩天大楼中间、第5和第6座摩天大楼中间各放一个热气球，东东可以进行次跳跃，距离分别是：3、5、4、5.5、5.5、4、4。其中最远距离向上取整为6。

【输入样例2】

10

19 99 26 32 9 3 7 10 21 

【输出样例2】

33

【数据范围】

对于20%的数据：1≤N≤10，相邻的摩天楼距离不超过100；

对于60%的数据：1≤N≤10000；

对于100%的数据：1≤N≤10⁵，相邻的摩天楼距离不超过10⁹。

参考答案：对于给定的摩天大楼数量N和相邻摩天大楼之间的距离，我们需要找到一种放置热气球的方式，使得东东的跳跃距离尽可能小。为了找到最大的跳跃距离，我们可以使用贪心算法。首先，我们将相邻摩天大楼之间的距离按升序排序。然后，我们遍历排序后的距离数组，每次选择当前距离和下一个距离中的较小值作为当前跳跃距离，并将当前距离和下一个距离从数组中移除。最后，我们将所有跳跃距离中的最大值作为结果输出。具体实现步骤如下：1. 读取输入数据，得到摩天大楼的数量N和相邻摩天大楼之间的距离数组dist。2. 对距离数组进行升序排序。3. 初始化最大跳跃距离max_jump为0。4. 遍历排序后的距离数组，对于每个距离d，计算当前跳跃距离curr_jump = min(d, dist[i+1])，其中i为当前遍历到的距离的下标。5. 更新最大跳跃距离max_jump = max(max_jump, curr_jump)。6. 将d和dist[i+1]从距离数组中移除。7. 输出最大跳跃距离max_jump，如果结果是小数，向上取整。

19、比k大的数

【题目描述】

一个不含0的n位数，其中值等于i的数码有c_i个（1≤i≤9）。

在这个n位数的所有可能的值中，比k大的值最小是多少？

【输入格式】

第1行，2个正整数n，k。

第2行，9个非负整数c₁，c₂，…，c₉，分别表示1～9的个数。

【输出格式】

输出所有可能的值中，比k大的值的最小值。

如果没有比k大的值，输出-1。

【输入样例1】

3 213

1 1 1 0 0 0 0 0 0

【输出样例1】

231

【输入样例2】

4 4000

1 0 2 1 0 0 0 0 0

【输出样例2】

4133 

【输入样例3】

3 9999

1 1 1 0 0 0 0 0 0

【输出样例3】

-1

【输入样例4】

21 791823456795285473500

1 2 2 3 2 3 2 3 3

【输出样例4】

791823456795286344689 

【样例1说明】

有1个1、1个2、1个3，可能的值有123，132，213，231，312，321，共6个。其中，比k=213 大的最小值是231。

【样例2说明】

有1个1、2个3、1个4，可能的值有

1334，1343，1433，3134，3143，3314，3341，3413，3431，4133，4313，4331共12个。其中，比k=4000 大的最小数是4133。

【样例3说明】

有1个1、1个2、1个3，可以得到的最大值321都比k=9999小，所以无法得到比k大的值。

【样例4说明】

输入输出可能超过64位整数类型范围。

【数据范围】

对于25%的数据，n≤9；k≤10⁹。

对于50%的数据，n≤200；k≤10²⁰⁰。

对于100%的数据，1≤n≤500000；1≤k≤10⁵⁰⁰⁰⁰¹；

C_i ≥0,C₁＋C₂＋C₃＋C₄＋C₅＋C₆＋C₇＋C₈＋C₉=n。

参考答案：对于每个样例，我们需要根据给定的数码个数和顺序，构造出所有可能的n位数，并找出比k大的最小值。对于每个样例，我们可以按照以下步骤进行：1. 根据给定的数码个数和顺序，构造出所有可能的n位数。2. 将这些数按照从小到大的顺序排序。3. 从排序后的数列中，找到比k大的最小值。对于样例1，构造出的所有可能的3位数有：123，132，213，231，312，321。其中，比k=213大的最小值是231。对于样例2，构造出的所有可能的4位数有：1334，1343，1433，3134，3143，3314，3341，3413，3431，4133，4313，4331。其中，比k=4000大的最小数是4133。对于样例3，构造出的所有可能的3位数有：123，132，213，231，312，321。这些数都比k=9999小，所以无法得到比k大的值，输出-1。对于样例4，由于输入输出可能超过64位整数类型范围，需要使用高精度算法进行计算。

喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！