CSP-J 初赛模拟卷 06

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

1. 以下哪个选项可以让一个 CPP 中的文字消失 (下一次打开为空白) 并原样的变到另一个 CPP 文件中 ( )

{{ select(1) }}

• 先 Ctrl + A 再按 Ctrl + C 再按退格键，再到另一个 CPP 文件中按 Ctrl + V。
• 先 Ctrl + E 再按 Ctrl + C 再按退格键，再到另一个 CPP 文件中按 Ctrl + V。
• 先 Ctrl + A 再按 Ctrl + C 再按退格键，再按 Ctrl + S，再到另一个 CPP 文件中按 Ctrl + V。
• 先 Ctrl + E 再按 Ctrl + C 再按退格键，再按 Ctrl + S，再到另一个 CPP 文件中按 Ctrl + V。

2. 八位的二进制补码 $10000000$，以下哪个选项关于其原码正确的说法 ( )

{{ select(2) }}

• $11111110$
• $10000000$
• $11111111$
• 无法表示。

3. 下图中从顶点 $s$ 开始有多少条最短路径可到达顶点 $t$(两个路径不同，当且仅当有经过的边或点不同) ( )

{{ select(3) }}

• 1
• 2
• 3
• 4

4. 在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的相对先后顺序 ( )

{{ select(4) }}

• 都不相同
• 完全相同
• 先序和中序相同，而与后序不同
• 中序和后序相同，而与先序不同

5. 有一表示算术表达式的二叉树（见下图），它所表示的算术表达式是（ ）

{{ select(5) }}

• $A*B+C/(D*E)+(F-G)$
• $(A*B+C)/(D*E)+(F-G)$
• $(A*B+C)/(D*E+(F-G))$
• $A*B+C/D*E+F-G$

6. 对于双链表，在两个结点之间删除一结点，最少需要修改 _____ 个指针域。

{{ select(6) }}

• 3
• 1
• 4
• 2

7. 一张 $5×5$ 的方格图，现在有个人站在第 1 行第 1 列，要走到第 $5$ 行第 $5$ 列。只能向右或者向下走的方案数是多少？不限制任何方向（不能重复的走到一个格子）方案数是多少？注意，如果行号和列数都是偶数，不能走入这一格中。 ( )

{{ select(7) }}

• 6 12
• 6 8
• 5 6
• 4 6

8. 以下哪种排序在排序过程中需要求得序列中最大或者最小值。( )

{{ select(8) }}

• 插入排序
• 选择排序
• 冒泡排序
• 以上都不需要

9. 以下代码片段空位应该填什么 ( )？

int get( ① ){ //求取输入的所有值
    for(int i = 0; i < n; i++){
        sum += *(a + i);
    }
    return sum;
}
​
int a[100];
​
int main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    cout << get( ② );
}

{{ select(9) }}

• ①处为 int a[] ②处为 a
• ①处为 int *a ②处为 a
• ①处为 int a[] ②处为 a + 1
• ①处为 int a[100] ②处为 a

10. 序列 4 5 6 7 8 9 10，每次可以对序列的某个子串 +1 、-1、+2、-2，请问至少多少次可以使得序列变为全是 0 的序列 ( )。

{{ select(10) }}

• 8
• 7
• 6
• 5

11. 这里有重量为 1g、2g、4g、...、$2^{32}$g 的汤圆，每个汤圆只能吃一次，豪豪哥希望吃尽量多的汤圆，但必须满足吃下的汤圆重量大于等于 $384$，小于等于 $392$ ，请问它能够吃的最多的汤圆数量是 ( )

{{ select(11) }}

• 5
• 6
• 7
• 8

12. 按照序列 5 2 4 3 1 6 的顺序存入栈（但是不保证出栈的顺序），需保证的是栈顶到栈尾自始至终是一个从大到小的序列才是一种合法出入栈方式，请问有多少种合法的出入栈方式 ( )

{{ select(12) }}

• 3
• 5
• 4
• 6

13. 教室中一共有 50 个人，学习语文的同学有 29 人，学习数学的人有 27 人，一边学数学一边学语文的同学有 13 人，一边学语文一边学英语的同学有 12 人，一心二用（同时学习两门及以上）的同学一共有 20 人，一心三用（同时学习三门）的同学一共有 5 人，请问学习英语的一共有多少人 （ ）

{{ select(13) }}

• 19
• 10
• 22
• 23

14. 有三位男生 A、B、C，三位女生 D、E、F 要排成一列。队列要中 A、B 相邻，D、E 相邻，而 B、E 不相邻。请问一共有多少种排列方式 ( )

{{ select(14) }}

• 12
• 32
• 84
• 44

15. 以下哪个选项使用的算法查询区间异或、区间最大公约数的时间复杂度最低 ( )

{{ select(15) }}

• 倍增 前缀和
• 前缀和 倍增
• 倍增 倍增
• 前缀和 前缀和

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

1  #include <bits/stdc++.h>
2  using namespace std;
3  
4  #define int long long
5  int a[5005];
6  int b[5005];
7  
8  signed main() {
9      int n;
10     cin >> n;
11     int cnt = 0, maxn = 0;
12     for (int i = 1; i <= n; ++i) {
13         cin >> a[i];
14         int h = a[i];
15         while(h > 1) {
16             b[i]++;
17             h = sqrt(h / 2 + 1);
18         }
19         maxn = max(maxn, b[i]);
20     }
21     for (int i = maxn; i >= 1; --i) {
22         for (int j = 1; j <= n;) {
23             if(b[j]!= i) {
24                 j++;
25                 continue;
26             }
27             cnt++;
28             int h = a[j];
29             while(h == a[j]) {
30                 b[j]--;
31                 a[j] = sqrt(a[j] / 2 + 1);
32                 j++;
33             }
34         }
35     }
36     cout << cnt;
37     return 0;
38 }

限定程序的数据范围为：$n≤2×10^3,1≤a_i≤10^{18}$。

判断题

16. 若将 15 行改成 while (h > 0) 程序仍然是正确的，但是 maxn 可能会增大 1 ( )

{{ select(16) }}

• 正确
• 错误

17. maxn 最大可能是 7 ( )

{{ select(17) }}

• 正确
• 错误

18. 该程序的第 22 行 ~ 34 行的作用是每次把 b 数组中的最大值减小 1 ( )

{{ select(18) }}

• 正确
• 错误

19. 同样的一组数据，有序的数据得到的 cnt 可能会比无序的数据得到的 cnt 要小 ( )

{{ select(19) }}

• 正确
• 错误

单选题

20. 当题目输入为 10 1 2 3 4 5 6 7 8 9 10 输出为 ( )

{{ select(20) }}

• 7
• 8
• 9
• 10

21. 记 $a_i$ 的最大值为 $a$，以下哪个选项最接近程序的真正的时间复杂度 ( )

{{ select(21) }}

• $O(n^2)$
• $O(n^2 \,\text {log }a)$
• $O(n\sqrt{a})$
• $O(n \,\text{log }\text{log }a)$

22. 当程序的 $n$ 为 1000，序列前 1 ~ 100 的数都为 1，101 ~ 200 的数都为 2，201 ~ 300 的数都为 3，以此类推，901 ~ 1000 的数都为 10。最终得输出为 ( )

{{ select(22) }}

• 9
• 10
• 90
• 100

1  #include<bits/stdc++.h>
2  using namespace std;
3  map<char,int>m;
4  int flag[30];
5  int n;
6  char a[30],b[30],c[30];
7  int S[30];
8  bool canprue(){ // 剪枝
9      if(m[a[0]] + m[b[0]] >= n) return true;
10     for(int i = n - 1; i >= 0; i--){
11         if(m[a[i]] == -1 || m[b[i]] == -1 || m[c[i]] == -1) continue;
12         if((m[a[i]] + m[b[i]]) % n!= m[c[i]] && (m[a[i]] + m[b[i]] + 1) % n!= m[c[i]]) return true;
13     }
14     return false;
15 }
16 bool judge() {
17     for(int i = n - 1,x = 0;i >= 0;i--) {  
18         int A = m[a[i]],B = m[b[i]],C = m[c[i]];
19         if((A + B + x) % n!= C) return false;  // A、B 这一位相加是否与 C 这一位相同
20         x = (A + B + x) / n;  // 是否进位
21     }
22     return true;
23 }
24 int cnt = 0;
25 void f(int x){
26     if(canprue() == true) return;
27     if(x == n){
28         if(judge() == true){
29             for(int i = 0; i < n; i++) cout << m[i + 'A'] << " ";
30             exit(0);
31         }
32         return;
33     }
34     else {
35         for(int i = n - 1; i >= 0; i--){
36             if(flag[i] == 0){
37                 m[S[x] + 'A'] = i;
38                 flag[i] = 1;
39                 f(x + 1);
40                 flag[i] = 0;
41                 m[S[x] + 'A'] = -1;
42             }
43         }       
44     }
45 }
46 void getS(char x){
47     if(flag[x - 'A'] == 0){
48         flag[x - 'A'] = 1;
49         S[cnt++] = x - 'A';
50     }
51 }
52 int main(){
53     scanf("%d",&n);
54     scanf("%s%s%s",a,b,c);
55     for(int i = 0; i <= 25; i++){
56         m[i + 'A'] = -1;
57     }
58     for(int i = n - 1; i >= 0; i--){
59         getS(a[i]);
60         getS(b[i]);
61         getS(c[i]);
62     }
63     for(int i = 0; i < n; i++) flag[i] = 0;
64     f(0);
65     return 0;
66 }

注意 $n≤26$，输入的字符串共三行，每行 $n$ 个字母，只包含大写字母。程序保证有解。

判断题

23. 去掉第 63 行对程序不会有影响，因为 flag 数组在全局变量，默认元素为 0 ( )

{{ select(23) }}

• 正确
• 错误

24. 将第 3 行改成一个大小为 90 的整型数组，既能优化程序时间复杂度，又不会对程序产生影响( )

{{ select(24) }}

• 正确
• 错误

25. （1分）当 $n=5$ 时，canprue() 函数最多被调用 3906 次 ( )

{{ select(25) }}

• 正确
• 错误

26. 这个程序输出了所有在 $n$ 进制下，使得 A + B = C 的解 ( )

{{ select(26) }}

• 正确
• 错误

单选题

27. 当题目输入

5
AAAAA
AACDD
BBEAA

答案输出( )

{{ select(27) }}

• 1 2 3 0 4
• 2 4 1 0 3
• 1 2 3 0 4 \n 2 4 1 0 3
• 以上全部错误

28. （2分）当题目的输出是 4 0 2 5 1 3 时，以下哪个选项是正确的输入 ( )

{{ select(28) }}

• 6
  AAAAAA
  BBBBBB
  CCCCCC
  

• 6
  FEBAED
  CCEEEA
  DFEDCB
  

• 6
  ABCCAA
  EBCBEA
  DBACDC
  

• 6
  FEDCAB
  ECAADC
  AAAEFC
  

1  #include <bits/stdc++.h>
2  using namespace std;
3  const int maxn = 25;
4  int n,m;
5  int ans;
6  int a[maxn],vis[maxn];
7  int book[2005];
8  int solve() {
9      memset(book,0,sizeof(book));
10     for(int i = 1; i <= n; i++) {
11         if(vis[i]) continue;
12         if(!book[a[i]]) book[a[i]] = i;
13         
14         for(int j = 2000; j >= 1; j--) {
15             if(book[j] && book[j]!= i) book[j + a[i]] = i;
16         }
17     }
18     int ret = 0;
19     for(int i = 1; i <= 2000; i++) ret += (book[i] > 0);
20     return ret;
21 }
22 void dfs(int x,int cnt) {
23     if(cnt == m + 1) {
24         ans = max(ans,solve());
25         return;
26     }
27     for(int i = x; i <= n; i++) {
28         if(!vis[i]) {
29             vis[i] = 1;
30             dfs(i + 1,cnt + 1);
31             vis[i] = 0;
32         }
33     }
34     return;
35 }
36 int main() {
37     cin >> n >> m;
38     for(int i = 1; i <= n; i++) cin >> a[i];
39     sort(a + 1,a + n + 1);
40     dfs(1,1);
41     cout << ans;
42     return 0;
43 }

对于 $100\%$ 的数据，$n≤20,m≤4,m<n,1≤a_i≤100$。

判断题

29. 将 39 行去掉不会对结果产生影响( )

{{ select(29) }}

• 正确
• 错误

30. 将 15 行的 && book[j]!= i 去掉不会对结果产生影响。( )

{{ select(30) }}

• 正确
• 错误

31. 相同的一组数据，仅仅是 $m$ 变大了，结果一定会减小。( )

{{ select(31) }}

• 正确
• 错误

32. （1分）如果输入的数据 $a_i$ 超过了 100，一定会导致数组越界 ( )

{{ select(32) }}

• 正确
• 错误

单选题

33. 若程序输入为

10 0 
1 2 4 8 16 32 64 100 100 100

答案输出 ( )

{{ select(33) }}

• 399
• 375
• 427
• 289

34. 该程序的时间复杂度为 ( )

{{ select(34) }}

• $O(2^m×n×2000)$
• $O(2^n×n×2000)$
• $O(n^m×n×2000)$
• $O(m^n×n×2000)$

35. 给定一组数据，最终得到的结果是 ans，如果将 $m$ 增大 1，$\text {ans}$ 最多减少多少 ( )

{{ select(35) }}

• $2^n$
• $2^n-1$
• $2^{n-1}$
• $2^{n-1}-1$

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

第一题：

题目描述：

一共有 $n$ 件食材，每件食材有三个属性，$a_i$，$b_i$ 和 $c_i$ ，如果在 $t$ 时刻开始做第 $i$ 样食材则得到 $a_i −t×b_i$ 的美味指数，用第 $i$ 件食材做饭要花去 $c_i$ 的时间。

众所周知，gw 的厨艺不怎么样，所以他需要你设计烹调方案使得美味指数最大。

输入格式：

第一行是两个正整数 $T$ 和 $n$，表示总共拥有的时间和食材个数。

• 下面一行 $n$ 个整数，$a_i$ ；

• 下面一行 $n$ 个整数，$b_i$ ；

• 下面一行 $n$ 个整数，$c_i$。

输出格式：

输出最大美味指数。

数据范围：$1≤n≤50$

所有数字均小于 $10^5$。

解题思路：先对食物按照可获得的美味指数进行排列，保证无论选择哪些食物，食物只需要按照排列后的相对顺序去烹饪。随后使用 01 背包选择出最优的食物组合。

#include <bits/stdc++.h>
using namespace std;
​
#define int long long
struct Node{
    int a, b, c;
}a[100005];
int dp[55][100005];
bool cmp(Node x, Node y) {
    return  ①
}
​
signed main() {
    int t, n;
    cin >>  t >> n;   
    for (int i = 0; i <= 50; ++i) {
        for (int j = 0; j <= 100000; ++j) dp[i][j] = -1e14;
    }
    for (int i =1; i <= n; ++i) {
        cin >> a[i].a;
    }
    dp[0][0] = 0;
    for (int i = 1; i <= n; ++i) cin >> a[i].b;
    for (int i = 1; i <= n; ++i) cin >> a[i].c;
    sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= t; ++j)  ②
        for (int j = ③ ; j <= t; ++j) { 
            dp[i][j] = max(dp[i][j], dp[④][j - a[i].c] + ⑤); 
        }
    }
    int maxn = 0;
    for (int i = 1; i <= t; ++i) {
        maxn = max(maxn, dp[n][i]);
    }
    cout << maxn;
    return 0;
}

36. ①处应填（）

{{ select(36) }}

• x.b * y.c > y.b * x.c
• x.b * y.c < y.b * x.c
• x.b * x.c > x.b * x.c
• x.b * x.c < x.b * x.c

37. ②处应填（）

{{ select(37) }}

• dp[i][j] = dp[i][j - a[i].c] + a[i].b
• dp[i][j] = dp[i - 1][j - a[i].a] + a[i].b
• dp[i][j] = dp[i - 1][j] + a[i].b
• dp[i][j] = dp[i - 1][j]

38. ③处应填（）

{{ select(38) }}

• 0
• a[i].b
• a[i].c
• a[i - 1].b

39. ④处应填（）

{{ select(39) }}

• i - 1
• i
• i - 2
• i + 1

40. ⑤处应填（）

{{ select(40) }}

• a[i].a
• a[i].a - a[i].b
• a[i].a - j * a[i].b
• a[i].a - (j - a[i].c) * a[i].b

---

第二题：

题目大意：

有一个大小为 $10000×10000$ 的方格区域，这个区域里面有$n$ 个地雷，其中每个 $1×1$ 的方格范围内可能有多个地雷。你有一个可以扫描正方形区域的扫描仪，请问，一个边长多长的扫描仪，可以在这个区域中的某个位置同时扫描到 $e$ 个地雷。

注意，扫描仪必须要与方格区域边框对齐

输入格式：

第一行两个整数，$e$、$n$ 代表需要同时扫描到 $e$ 个地雷，一共有 $n$ 个地雷。

接下来 $n$ 每行两个整数 $x$，$y$ 代表地雷的坐标。

输出格式：

一个整数代表结果。

数据范围：

$1≤e≤n≤500$。

解题思路：

二分扫描半径，排序、双指针优化该半径区域能够扫描到的最多的地雷数。

#include<iostream>
#include<algorithm>
using namespace std;
struct node {
        int x, y;
} a[505],b[505],c[505];
bool cmp(node a,node b) {
    return (a.x == b.x)? a.y < b.y : a.x < b.x;
}
bool cmp1(node a,node b) {
    return  ①
}
int e,n;
int s[505];
int m[505];
int check(int l,int mid) {
    int r = ②
    int p = 0;
    for(int i = 1; i <= n; i++) {
        if(c[i].x <= r && c[i].x >= l) {
            ③
        }
    }
    int p1 = 1,p2 = 1;
    while(m[p2] - m[p1] + 1 <= mid && p2 <= p) ++p2;
    if(p2 > p || m[p2] - m[p1] + 1 > mid) --p2;
    int ans = 0;
    while(p1 <= p2 && p2 <= p) {
        ans = max(ans,p2 - p1 + 1);
        ++p2;
        while(④) ++p1; 
    }
    return ans;
}
int main() {
    cin >> e >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i].x >> a[i].y;
    }
    sort(a + 1,a + n + 1,cmp);
    for(int i = 1; i <= n; i++) {
        b[i].x = a[i].x;
        b[i].y = a[i].y;
    }
    sort(a + 1,a + n + 1,cmp1);
    for(int i = 1; i <= n; i++) {
        c[i].x = a[i].x;
        c[i].y = a[i].y;
    }
    int l = 0, r = ⑤; 
    while(l < r) {
        int mid = (l + r) >> 1;
        bool flag = false;
        for(int i = 1; i <= n; i++) {
            if(check(b[i].x,mid) >= e) {
                flag = true;
                break;
            }
        }
        if(flag == true) r = mid;
        else l = mid + 1;
    }
    cout << r << endl;
    return 0;
}

41. ①处应填（）

{{ select(41) }}

• (a.y == b.y)? a.x < b.x : a.y < b.y;
• (a.y == b.y)? a.y < b.y : a.x < b.x;
• (a.x == b.x)? a.y < b.y : a.x < b.x;
• (a.x == b.x)? a.x < b.x : a.y < b.y;

42. ②处应填（）

{{ select(42) }}

• mid - 1;
• mid;
• l + mid;
• l + mid - 1;

43. ③处应填（）

{{ select(43) }}

• m[p++] = c[i].x;
• m[p++] = c[i].y;
• m[++p] = c[i].y;
• m[++p] = c[i].x;

44. ④处应填（）

{{ select(44) }}

• m[p2] - m[p1] + 1 >= mid
• m[p2] - m[p1] + 1 > mid
• m[p2] - m[p1] > mid
• m[p1] - m[p2] + 1 >= mid

45. ⑤处应填（）

{{ select(45) }}

• a[n].x
• e
• 10000
• n